python - 使用 Python Scipy Minimize 优化运输成本流

Question

我有一个运输成本流问题，目的是最大限度地减少 5 家承运商和 3000 多个运输 channel (例如纽约到迈阿密国际机场)的总体运输成本我将从我的数据集中模拟一些示例数据，以帮助您更好地理解问题。请在此处查看我的数据图像

我尝试过 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_installpulp 安装 PuLP。这个问题也可以用更自然的方式表达，因为 PuLP 具有声明变量字典的便利函数。虽然商业求解器比与 PuLP 捆绑的求解器更快，但您的问题是一个纯线性程序，即使有 3000 个 channel 和 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.")