基于Python Scipy最小化的运输费用流优化

Question

我有一个运输成本流问题，其目的是最小化来自5个承运商和3000多条运输车道的总体运输成本(例如：NY to MIA)我将模拟我的数据集中的一些样本数据，以帮助您更好地了解问题。请在此处查看我的数据图像

​

​

我尝试过Lonprog，但它只适用于逐条车道，而不适用于矩阵决策变量

请建议在没有商业求解器的情况下解决问题的正确方法(标准excel求解器有200个变量限制)

谢谢

Answer 1

你的问题是一个结构良好的运输问题。它可以通过各种方式来解决。

如果你想用线性规划来解决这个问题，你可以使用scipy.optimize.linprog。对于多维决策变量，对变量进行编码会稍微困难一些。

使用scipy.optimize.linprog，你可以这样建模和解决你的问题：

import random
import numpy as np
import scipy.optimize

LANES = 30
CARRIERS = 6

cost = np.random.rand(LANES, CARRIERS) # c
demand = np.random.rand(LANES) # b_eq
capacity = [250, 300, 500, 750, 100, 200] # b_ub

A_eq = np.zeros(LANES*CARRIERS*LANES).reshape(LANES, LANES*CARRIERS)
# Constraint for each lane, sum over the available carriers
for l in range(LANES):
    for var in range(l*CARRIERS, l*CARRIERS+CARRIERS):
        A_eq[l, var] = 1

A_ub = np.zeros(CARRIERS*LANES*CARRIERS).reshape(CARRIERS, LANES*CARRIERS)
# Constraint for each carrier, sum over the lanes
for c in range(CARRIERS):
    for var in range(c, LANES*CARRIERS, CARRIERS):
        A_ub[c, var] = 1

print(scipy.optimize.linprog(cost.flatten(), A_eq=A_eq, b_eq=demand, 
    A_ub=A_ub, b_ub=capacity, options={"maxiter": 10000}))

我们总共需要LANES*CARRIERS变量，它们可以用一个一维数组来表示。表示在具有载波c的通道l上传输的量的变量具有索引l*LANES + c。在此假设下，可以添加约束。由于完整的问题矩阵具有LANES*CARRIERS*(LANES+CARRIERS)元素，因此linprog函数可能不适合问题大小。您可以增加maxiter参数，但您可能会遇到其他问题，如数值问题，尽管我没有阅读源代码。

PuLP捆绑了一个更快、更健壮的自由求解器。您可以使用easy_install pulp安装PuLP。这个问题也可以用一种更自然的方式来表达，因为PuLP具有声明变量字典的方便函数。虽然商业求解器比与PuLP捆绑在一起的求解器更快，但您的问题是一个纯粹的线性程序，即使有3000个通道和6个运营商，也相对“容易”。

在PuLP中，它可以以一种更自然的方式实现：

from pulp import *
import numpy as np
from itertools import product

LANES = 30
CARRIERS = 6

cost = 100 * np.random.rand(LANES, CARRIERS) # c
demand = 10 * np.random.rand(LANES) # b_eq
capacity = [250, 300, 500, 750, 100, 200] # b_ub

prob = LpProblem("Transportation",LpMinimize)
x = LpVariable.dicts("Route", product(range(LANES), range(CARRIERS)), 0, None)

prob += lpSum(cost[l, c] * x[l, c] for l in range(LANES) for c in range(CARRIERS))

for l in range(LANES):
    prob += lpSum(cost[l, c] * x[l, c] for c in range(CARRIERS)) == demand[l]

for c in range(CARRIERS):
    prob += lpSum(cost[l, c] * x[l, c] for l in range(LANES)) <= capacity[c]

prob.solve()

# Get optimal solution
if LpStatus[prob.status] == "Optimal":
    x = {(l, c): value(x[l, c]) for l in range(LANES) for c in range(CARRIERS)}
else:
    print("Optimization failed.")