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

我有一个运输成本流问题，目的是最大程度地减少5个运输商和3000多个运输通道（从NY到MIA）的总体运输成本
我将从我的数据集中模拟一些样本数据，以帮助您更好地理解问题。请在这里查看我的数据图像



我已经尝试过Lonprog，但它仅适用于逐条通道，不适用于矩阵决策变量

请提供在没有商业求解器的情况下解决问题的正确方法（标准excel求解器有200个变量限制）

谢谢

最佳答案

您的问题是一个结构合理的运输问题。它可以通过多种方式解决。

如果要通过线性编程求解，可以使用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变量，这些变量可以用一维数组表示。表示用载波l在通道c上运输了多少的变量的索引为l*LANES + c。在此假设下，可以添加约束。
由于完整的问题矩阵包含LANES*CARRIERS*(LANES+CARRIERS)个元素，因此linprog函数可能不适合问题大小。您可以增加maxiter参数，但是您可能会遇到其他问题，例如数值问题，尽管我没有阅读源代码。

更快，更强大的免费求解器与PuLP捆绑在一起。您可以使用PuLP安装easy_install 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.")

关于python - 使用Python Scipy Minimize优化运输成本流，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48895750/