LINGO运输问题求解

Question

送货点为24个点分别有8种类型货物须在30天内利用10台车运送完毕。8种类型货物长和宽和高和重量皆不同，每辆车皆相同，长为435cm，宽为190cm，高为220cm，最大载送重量为1440g。以最短路径，最小剩余空间，实现最小的载送成本。如何使用LNGO解决问题?

货物 1 2 3 4 5 6 7 8
长(cm) 107 152 183 183 107 76 91 91
高(cm) 190 190 190 213 190 190 190 213
厚度(cm) 35 35 35 35 20 20 20 20
重量(g) 30 30 30 30 25 25 25 25

送货点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
距离(公里) 42.7 43.4 29.6 33.7 52.5 18.3 14 44.6 134 134 45.5 39.3 44.8 46.2 38.1 130 219 278 40.3 41.9 5.9 48.1 131 321
时间(分钟) 84 96 76 80 96 62 52 88 204 214 98 92 102 100 84 200 308 398 98 86 32 106 210 436
需求1(数量) 20 20 20 30 30 20 30 20 30 30 30 30 60 20 30 30 40 20 20 30 30 30 40 40
需求2(数量) 30 20 20 40 40 30 40 30 40 40 40 40 30 30 30 40 50 50 30 30 40 40 40 20
需求3(数量) 40 20 30 40 30 30 30 30 40 30 40 30 30 30 30 30 40 30 30 30 50 20 20 30
需求4(数量) 30 30 30 30 30 30 40 30 30 30 30 30 30 30 40 30 30 30 30 30 30 20 30 20
需求5(数量) 30 30 30 40 30 30 30 30 40 30 30 30 30 30 30 30 30 30 30 30 30 30 40 20
需求6(数量) 30 30 40 30 20 40 40 40 30 30 30 30 30 30 30 30 30 30 30 30 30 50 40 30
需求7(数量) 50 40 30 30 40 30 30 30 30 30 30 30 30 30 30 30 210 20 50 30 30 30 20 50
需求8(数量) 50 30 30 30 30 30 30 20 20 20 20 40 40 40 40 210 210 30 40 40 50 40 30 60
车辆 1 2 3 4 5 6 7 8 9 10
每公里成本(元) 50 50 50 50 50 50 50 50 50 50
每日总载送时间(分钟) 480 480 480 480 480 480 480 480 480 480

货车
最大长(cm) 435
最大高(cm) 190
最大宽(cm) 220
最大载送重量(g) 1440

Answer 1

对于这个问题，你可以使用LNGO（Large Neighborhood Search）算法来求解。LNGO是一种局部搜索算法，用于求解组合优化问题。在这个问题中，你的目标是找到一种合理的方案，使得货车以最短路径、最小剩余空间、最小载送成本的方式完成送货任务。

以下是一种可能的LNGO算法的实现步骤：

1. 初始化解决方案： 随机生成一个初始的送货方案，确保满足每个送货点的需求，并且考虑货车的容量和时间限制。

2. 定义目标函数： 设计一个目标函数，该函数综合考虑了路径长度、剩余空间和成本。这个函数需要被最小化。

3. 迭代搜索： 在每一次迭代中，通过调整送货方案中的某些部分，尝试改进目标函数的值。这可能涉及到交换货物的送货顺序、更改路径、调整货车分配等。

4. 约束处理： 在迭代过程中，确保任何新生成的方案都满足问题的所有约束，包括货车容量、时间限制等。

5. 停止准则： 设定停止算法的准则，例如达到一定的迭代次数、目标函数值的变化小于阈值等。

6. 输出最优解： 在算法运行完成后，输出找到的最优解，即送货方案，以及相应的路径、剩余空间、成本等信息。

由于这是一个组合优化问题，LNGO算法可以在搜索空间中不断调整，寻找更优的解决方案。在实际应用中，你可能需要根据问题的具体特点对算法进行调整和优化。

在 Python 中，你可以使用优化库如 PuLP、Gurobi、或者 Google OR-Tools 来建立和求解这样的组合优化问题。由于你的问题涉及到多个约束条件和目标函数，下面是一个简单的示例使用 PuLP 来解决这个问题。请注意，你可能需要根据具体的约束和目标函数形式进行调整。

首先，确保你已经安装了 PuLP 库：

pip install pulp

然后，你可以使用以下代码：

from pulp import LpProblem, LpVariable, lpSum, LpMinimize

# 货物和送货点的数据
goods_data = {
    'length': [107, 152, 183, 183, 107, 76, 91, 91],
    'height': [190, 190, 190, 213, 190, 190, 190, 213],
    'thickness': [35, 35, 35, 35, 20, 20, 20, 20],
    'weight': [30, 30, 30, 30, 25, 25, 25, 25],
}

delivery_data = {
    'distance': [42.7, 43.4, 29.6, 33.7, 52.5, 18.3, 14, 44.6, 134, 134, 45.5, 39.3, 44.8, 46.2, 38.1, 130, 219, 278, 40.3, 41.9, 5.9, 48.1, 131, 321],
    'time': [84, 96, 76, 80, 96, 62, 52, 88, 204, 214, 98, 92, 102, 100, 84, 200, 308, 398, 98, 86, 32, 106, 210, 436],
    'demand1': [20, 20, 20, 30, 30, 20, 30, 20, 30, 30, 30, 30, 60, 20, 30, 30, 40, 20, 20, 30, 30, 30, 40, 40],
    'demand2': [30, 20, 20, 40, 40, 30, 40, 30, 40, 40, 40, 40, 30, 30, 30, 40, 50, 50, 30, 30, 40, 40, 40, 20],
    'demand3': [40, 20, 30, 40, 30, 30, 30, 30, 40, 30, 40, 30, 30, 30, 30, 30, 40, 30, 30, 30, 50, 20, 20, 30],
    'demand4': [30, 30, 30, 30, 30, 30, 40, 30, 30, 30, 30, 30, 30, 30, 40, 30, 30, 30, 30, 30, 30, 20, 30, 20],
    'demand5': [30, 30, 30, 40, 30, 30, 30, 30, 40, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 40, 20],
    'demand6': [30, 30, 40, 30, 20, 40, 40, 40, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 50, 40, 30],
    'demand7': [50, 40, 30, 30, 40, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 210, 20, 50, 30, 30, 30, 20, 50],
    'demand8': [50, 30, 30, 30, 30, 30, 30, 20, 20, 20, 20, 40, 40, 40, 40, 210, 210, 30, 40, 40, 50, 40, 30, 60],
}

# 车辆和货车的数据
vehicle_data = {
    'length': 435,
    'height': 190,
    'width': 220,
    'max_weight': 1440,
}

# 创建PuLP问题
problem = LpProblem("Delivery_Optimization", LpMinimize)

# 创建变量
# x[i, j, k]: 送货点j上的货物i是否由车辆k运送
x = LpVariable.dicts("delivery", ((i, j, k) for i in range(1, 9) for j in range(1, 25) for k in range(1, 11)), cat='Binary')

# 目标函数
problem += lpSum(delivery_data['distance'][j - 1] * x[i, j, k] for i in range(1, 9) for j in range(1, 25) for k in range(1, 11))

# 约束条件
# 每个货物只能由一个车辆运送
for i in range(1, 9):
    problem += lpSum(x[i, j, k] for j in range(1, 25) for k in

 range(1, 11)) == 1

# 每个送货点的需求必须满足
for j in range(1, 25):
    problem += lpSum(x[i, j, k] for i in range(1, 9) for k in range(1, 11)) == 1

# 每辆车的载重量不能超过最大载重量
for k in range(1, 11):
    problem += lpSum(goods_data['weight'][i - 1] * x[i, j, k] for i in range(1, 9) for j in range(1, 25)) <= vehicle_data['max_weight']

# 解决问题
problem.solve()

# 输出结果
print("Optimal Objective Value:", problem.objective.value())

# 打印每个变量的值
for var in problem.variables():
    if var.varValue > 0:
        print(f"{var.name}: {var.varValue}")

请注意，这只是一个简化的示例，实际问题可能需要更复杂的约束和目标函数。你可能需要根据具体情况调整这个模型。此外，这个模型也没有考虑到时间限制等其他约束条件，你可能需要根据实际需求进行相应的调整。