代码之家  ›  专栏  ›  技术社区  ›  pisk1

谷歌最小成本流解决交通流问题

  •  0
  • pisk1  · 技术社区  · 6 年前

    假设我们有以下数据来解决运输问题:

              A1      A2      A3      Supply
    T1        0       600     100     700
    T2        500     0       300     800
    Demand    500     600     400
    

    我想用谷歌优化工具最小成本流来解决运输问题。我正试图用以下代码来解决这个问题:

        private static void SolveMinCostFlow()
        {
            // Define four parallel arrays: sources, destinations, capacities, and unit costs
            // between each pair. For instance, the arc from node 0 to node 1 has a
            // capacity of 15.
            // Problem taken From Taha's 'Introduction to Operations Research',
            // example 6.4-2.
    
            int numNodes = 5;
            int numArcs = 6;
            int[] startNodes = { 0, 0, 0, 1, 1, 1 };
            int[] endNodes = { 2, 3, 4, 2, 3, 4};
            int[] capacities = { 500, 600, 400, 500, 600, 400 };
            int[] unitCosts = { 0, 600, 100, 500, 0, 300 };
    
            // Define an array of supplies at each node.
    
            int[] supplies = { 700, 700, 800, 800, 800 };
    
    
    
            // Instantiate a SimpleMinCostFlow solver.
            MinCostFlow minCostFlow = new MinCostFlow();
    
            // Add each arc.
            for (int i = 0; i < numArcs; ++i)
            {
                int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                                     capacities[i], unitCosts[i]);
                if (arc != i) throw new Exception("Internal error");
            }
    
            // Add node supplies.
            for (int i = 0; i < numNodes; ++i)
            {
                minCostFlow.SetNodeSupply(i, supplies[i]);
            }
    
    
            //Console.WriteLine("Solving min cost flow with " + numNodes + " nodes, and " +
            //                  numArcs + " arcs, source=" + source + ", sink=" + sink);
    
            // Find the min cost flow.
            int solveStatus = minCostFlow.Solve();
            if (solveStatus == MinCostFlow.OPTIMAL)
            {
                long optimalCost = minCostFlow.OptimalCost();
                Console.WriteLine("Minimum cost: " + optimalCost);
                Console.WriteLine("");
                Console.WriteLine(" Edge   Flow / Capacity  Cost");
                for (int i = 0; i < numArcs; ++i)
                {
                    long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
                    Console.WriteLine(minCostFlow.Tail(i) + " -> " +
                                      minCostFlow.Head(i) + "  " +
                                      string.Format("{0,3}", minCostFlow.Flow(i)) + "  / " +
                                      string.Format("{0,3}", minCostFlow.Capacity(i)) + "       " +
                                      string.Format("{0,3}", cost));
                }
            }
            else
            {
                Console.WriteLine("Solving the min cost flow problem failed. Solver status: " +
                                  solveStatus);
            }
        }
    
        static void Main(string[] args)
        {
            SolveMinCostFlow();
            Console.Read();
        }
    

    但我得到了一个错误:解决最小成本流问题失败了。解算器状态:4 我做错了什么?我想在SolveMinCostFlow的开头应该有一些定义参数的东西,但无法理解。

    2 回复  |  直到 6 年前
        1
  •  3
  •   Erwin Kalvelagen    6 年前

    总结:平衡的n x m运输问题可以使用或工具转化为最大流量问题,如下所示:

    • 有供需的n+m节点(需求建模为负供给)
    • 无限容量和成本为c(i,j)的n*m弧

    一些python代码可以验证这一点:

    from ortools.graph import pywrapgraph
    
    #           A1      A2      A3      Supply
    # T1        0       600     100     700
    # T2        500     0       300     800
    # Demand    500     600     400
    
    numNodes = 5
    numArcs = 6;
    startNodes = [ 0, 0, 0, 1, 1, 1 ]
    endNodes = [ 2, 3, 4, 2, 3, 4 ]
    capacities =  [9999] * numArcs
    unitCosts =  [0, 600, 100, 500, 0, 300 ]
    supplies = [700,800,-500,-600,-400]
    
    # Instantiate a SimpleMinCostFlow solver.
    min_cost_flow = pywrapgraph.SimpleMinCostFlow()
    
    # Add each arc.
    for i in range(0, len(startNodes)):
        min_cost_flow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                                    capacities[i], unitCosts[i])
    
    # Add node supplies.
    for i in range(0, len(supplies)):
        min_cost_flow.SetNodeSupply(i, supplies[i])
    
    
    # Find the minimum cost flow 
    if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
        print('Minimum cost:', min_cost_flow.OptimalCost())
        print('')
        print('  Arc    Flow / Capacity  Cost')
        for i in range(min_cost_flow.NumArcs()):
          cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
          print('%1s -> %1s   %3s  / %3s       %3s' % (
              min_cost_flow.Tail(i),
              min_cost_flow.Head(i),
              min_cost_flow.Flow(i),
              min_cost_flow.Capacity(i),
              cost))
    else:
        print('There was an issue with the min cost flow input.')
    

    此打印:

    Minimum cost: 80000
    
      Arc    Flow / Capacity  Cost
    0 -> 2   500  / 9999         0
    0 -> 3     0  / 9999         0
    0 -> 4   200  / 9999       20000
    1 -> 2     0  / 9999         0
    1 -> 3   600  / 9999         0
    1 -> 4   200  / 9999       60000
    

    更有趣的是一个总供给大于的非平衡运输问题;总需求。或者工具最小成本流算法也可以处理该问题(通过 min_cost_flow.SolveMaxFlowWithMinCost() ).

        2
  •  1
  •   Andres Ordorica    5 年前

    抱歉,但我认为最好添加一个接收器并修改主网的容量。此修改将允许您优化当前数据并满足特定要求。

    #           A1      A2      A3      Supply
    # T1        0       600     100     700  
    # T2        500     0       300     800  
    # Demand    500     600     400
    
    numNodes = 6
    numArcs = 9;
    startNodes = [ 0, 0, 0, 1, 1, 1] + [2,3,4]
    endNodes = [ 2, 3, 4, 2, 3, 4 ]+ [5,5,5 ]
    capacities =  [0,1000,1000,1000,0,1000]+[500,600,400]
    unitCosts =  [0, 600, 100, 500, 0, 300 ]+[0,0,0]
    supplies = [700,800,0,0,0,-1500]
    

    因此,通过添加额外的节点(接收器),您可以确保满足您的需求,通过更改容量,您可以确保不会向成本单位为0的节点发送单位(我假设cero意味着该特定来源不会向该节点发送任何信息)。希望有帮助! 输出: 最低成本:710000

      Ruta    Flujo / Capacidad  Costo
    0 -> 2     0  /   0         0
    0 -> 3   600  / 1000       360000
    0 -> 4   100  / 1000       10000
    1 -> 2   500  / 1000       250000
    1 -> 3     0  /   0         0
    1 -> 4   300  / 1000       90000
    2 -> 5   500  / 500         0
    3 -> 5   600  / 600         0
    4 -> 5   400  / 400         0
    
    
    Where costo minimo = minimum cost