您现在的位置是:首页 > 技术教程 正文

【运筹优化】带时间窗约束的车辆路径规划问题(VRPTW)详解 + Python 调用 Gurobi 建模求解

admin 阅读: 2024-03-26
后台-插件-广告管理-内容页头部广告(手机)

文章目录

  • 一、概述
    • 1.1 VRP 问题
    • 1.2 CVRP 问题
    • 1.3 VRPTW 问题
  • 二、VRPTW 的一般模型
  • 三、Python 调用 Gurobi 建模求解
    • 3.1 Solomn 数据集
    • 3.2 完整代码
    • 3.3 运行结果展示
      • 3.3.1 测试案例:c101.txt
      • 3.3.2 测试案例:r101.txt


一、概述

1.1 VRP 问题

车辆路径规划问题(Vehicle Routing Problem,VRP)一般指的是:对一系列发货点和收货点,组织调用一定的车辆,安排适当的行车路线,使车辆有序地通过它们,在满足指定的约束条件下(例如:货物的需求量与发货量,交发货时间,车辆容量限制,行驶里程限制,行驶时间限制等),力争实现一定的目标(如车辆空驶总里程最短,运输总费用最低,车辆按一定时间到达,使用的车辆数最小等)。

下图给出了一个简单的VRP的例子

在这里插入图片描述

1.2 CVRP 问题

最基本的VRP问题叫做带容量约束的车辆路径规划问题(Capacitated Vehicle Routing Problem,CVRP)。在CVRP中,需要考虑每辆车的容量约束、车辆的路径约束和装载量约束

1.3 VRPTW 问题

为了考虑配送时间要求,带时间窗的车辆路径规划问题(Vehicle Routing Problem with Time Window,VRPTW)应运而生。

VRPTW 不仅考虑CVRP的所有约束,还需要考虑时间窗约束,也就是每个顾客对应一个时间窗 [ e i , l i ] [e_i,l_i] [ei,li],其中 e i e_i ei l i l_i li 分别代表该点的最早到达时间和最晚到达时间。顾客点 i ∈ V i \in V iV 的需求必须要在其时间窗内被送达

VRPTW 已经被证明是 NP-hard 问题,其求解复杂度随着问题规模的增加而急剧增加,求解较为困难。到目前为止,求解 VRPTW 的比较高效的精确算法是分支定价算法和分支定价切割算法。


二、VRPTW 的一般模型

VRPTW 可以建模为一个混合整数规划问题,在给出完整数学模型之前,先引入下面的决策变量:

x i j k = { 1 ,在最优解中,弧 ( i , j ) 被车辆 k 选中 0 ,其他 s i k = 车辆 k 到达 i 的时间 模型中涉及的其他参数为 : t i j 表示车辆在弧 ( i , j ) 上的行驶时间 M 为一个足够大的正数 {x_{ijk}}=\begin{cases} 1\text{,在最优解中,弧}\left( i,j \right) \text{被车辆}k\text{选中}\\ 0\text{,其他}\\ \end{cases} \\ {s_{ik}}=\text{车辆}k\text{到达}i\text{的时间} \\ \text{模型中涉及的其他参数为}: \\ {t_{ij}}\text{表示车辆在弧}\left( i,j \right) \text{上的行驶时间} \\ M\text{为一个足够大的正数} xijk={1,在最优解中,弧(i,j)被车辆k选中0,其他sik=车辆k到达i的时间模型中涉及的其他参数为:tij表示车辆在弧(i,j)上的行驶时间M为一个足够大的正数

关于 M M M 的取值,实际上可以直接取非常大的正数,但是为了提高求解效率,拉紧约束。我们可以采用下面的取值方法:

M = m a x { b i + t i j − a j } , ∀ ( i , j ) ∈ A M=max\{b_i+t_{ij}-a_j\} , \forall (i,j)\in A M=max{bi+tijaj},(i,j)A

综合上面引出的决策变量,并参考文献(Desaulniers et al.,2006),给出的 VRPTW 的标准模型如下:

min ⁡ ∑ k ∈ K ∑ i ∈ V ∑ j ∈ V c i j x i j k s . t . ∑ k ∈ K ∑ j ∈ V x i j k = 1 , ∀ i ∈ C    ∑ j ∈ V x 0 j k = 1 , ∀ k ∈ K    ∑ i ∈ V x i h k − ∑ j ∈ V x h j k = 0 , ∀ h ∈ C , ∀ k ∈ K    ∑ i ∈ V x i , n + 1 , k = 1 , ∀ k ∈ K    ∑ i ∈ C q i ∑ j ∈ V x i j k ⩽ Q , ∀ k ∈ K    s i k + t i j − M ( 1 − x i j k ) ⩽ s j k    , ∀ ( i , j ) ∈ A , ∀ k ∈ K    e i ⩽ s i k ⩽ l i    , ∀ i ∈ V , ∀ k ∈ K    x i j k ∈ { 0 , 1 }    , ∀ ( i , j ) ∈ A , ∀ k ∈ K \min \sum_{k\in K}{\sum_{i\in V}{\sum_{j\in V}{{c_{ij}}{x_{ijk}}}}} \\ s.t. \sum_{k\in K}{\sum_{j\in V}{{x_{ijk}}=1 , \forall i\in C}} \\ \,\, \sum_{j\in V}{{x_{0jk}}=1 , \forall k\in K} \\ \,\, \sum_{i\in V}{{x_{ihk}}-\sum_{j\in V}{{x_{hjk}}=0 , \forall h\in C,\forall k\in K}} \\ \,\, \sum_{i\in V}{x_{i,n+1,k}=1 , \forall k\in K} \\ \,\, \sum_{i\in C}{q_i\sum_{j\in V}{{x_{ijk}} \leqslant Q , \forall k\in K}} \\ \,\, {s_{ik}}+{t_{ij}}-M\left( 1-{x_{ijk}} \right) \leqslant {s_{jk}}\,\,, \forall \left( i,j \right) \in A,\forall k\in K \\ \,\, e_i\leqslant {s_{ik}}\leqslant l_i\,\,, \forall i\in V,\forall k\in K \\ \,\, {x_{ijk}}\in \left\{ 0,1 \right\} \,\,, \forall \left( i,j \right) \in A,\forall k\in K minkKiVjVcijxijks.t.kKjVxijk=1,iCjVx0jk=1,kKiVxihkjVxhjk=0,hC,kKiVxi,n+1,k=1,kKiCqijVxijkQ,kKsik+tijM(1xijk)sjk,(i,j)A,kKeisikli,iV,kKxijk{0,1},(i,j)A,kK

其中, Q Q Q 为车容量, q i q_i qi 为第 i i i 个顾客的需求:

  • 目标函数是为了最小化所有车辆的总行驶成本(距离)
  • 约束1~4保证了每辆车必须从仓库出发,经过一个点就离开那个点,最终返回仓库
  • 约束5为车辆的容量约束
  • 约束6~7是时间窗约束,保证了车辆到达每个顾客点的时间均在时间窗内,点n+1是点o的一个备份,是为了方便实现。

三、Python 调用 Gurobi 建模求解

3.1 Solomn 数据集

Solomn 数据集下载地址

3.2 完整代码

注意,在下面代码中,将弧 i i i 到弧 j j j 所需的时间 t i j t_{ij} tij 和 成本 c i j c_{ij} cij 都当作了弧 i i i 到弧 j j j 所需的距离来看待

# -*- coding: utf-8 -*-# # Author: WSKH # Blog: wskh0929.blog.csdn.net # Time: 2023/2/8 11:14 # Description: Python 调用 Gurobi 建模求解 VRPTW 问题 import time import matplotlib.pyplot as plt import numpy as np from gurobipy import * class Data: customerNum = 0 nodeNum = 0 vehicleNum = 0 capacity = 0 corX = [] corY = [] demand = [] serviceTime = [] readyTime = [] dueTime = [] distanceMatrix = [[]] def readData(path, customerNum): data = Data() data.customerNum = customerNum if customerNum is not None: data.nodeNum = customerNum + 2 with open(path, 'r') as f: lines = f.readlines() count = 0 for line in lines: count += 1 if count == 5: line = line[:-1] s = re.split(r" +", line) data.vehicleNum = int(s[1]) data.capacity = float(s[2]) elif count >= 10 and (customerNum is None or count <= 10 + customerNum): line = line[:-1] s = re.split(r" +", line) data.corX.append(float(s[2])) data.corY.append(float(s[3])) data.demand.append(float(s[4])) data.readyTime.append(float(s[5])) data.dueTime.append(float(s[6])) data.serviceTime.append(float(s[7])) data.nodeNum = len(data.corX) + 1 data.customerNum = data.nodeNum - 2 # 回路 data.corX.append(data.corX[0]) data.corY.append(data.corY[0]) data.demand.append(data.demand[0]) data.readyTime.append(data.readyTime[0]) data.dueTime.append(data.dueTime[0]) data.serviceTime.append(data.serviceTime[0]) # 计算距离矩阵 data.distanceMatrix = np.zeros((data.nodeNum, data.nodeNum)) for i in range(data.nodeNum): for j in range(i + 1, data.nodeNum): distance = math.sqrt((data.corX[i] - data.corX[j]) ** 2 + (data.corY[i] - data.corY[j]) ** 2) data.distanceMatrix[i][j] = data.distanceMatrix[j][i] = distance return data class Solution: ObjVal = 0 X = [[]] S = [[]] routes = [[]] routeNum = 0 def __init__(self, data, model): self.ObjVal = model.ObjVal # X_ijk self.X = [[([0] * data.vehicleNum) for _ in range(data.nodeNum)] for _ in range(data.nodeNum)] # S_ik self.S = [([0] * data.vehicleNum) for _ in range(data.nodeNum)] # routes self.routes = [] def getSolution(data, model): solution = Solution(data, model) for m in model.getVars(): split_arr = re.split(r"_", m.VarName) if split_arr[0] == 'X' and m.x > 0.5: solution.X[int(split_arr[1])][int(split_arr[2])][int(split_arr[3])] = m.x elif split_arr[0] == 'S' and m.x > 0.5: solution.S[int(split_arr[1])][int(split_arr[2])] = m.x for k in range(data.vehicleNum): i = 0 subRoute = [] subRoute.append(i) finish = False while not finish: for j in range(data.nodeNum): if solution.X[i][j][k] > 0.5: subRoute.append(j) i = j if j == data.nodeNum - 1: finish = True if len(subRoute) >= 3: subRoute[-1] = 0 solution.routes.append(subRoute) solution.routeNum += 1 return solution def plot_solution(solution, customer_num): plt.xlabel("x") plt.ylabel("y") plt.title(f"{data_type} : {customer_num} Customers") plt.scatter(data.corX[0], data.corY[0], c='blue', alpha=1, marker=',', linewidths=3, label='depot') # 起点 plt.scatter(data.corX[1:-1], data.corY[1:-1], c='black', alpha=1, marker='o', linewidths=3, label='customer') # 普通站点 for k in range(solution.routeNum): for i in range(len(solution.routes[k]) - 1): a = solution.routes[k][i] b = solution.routes[k][i + 1] x = [data.corX[a], data.corX[b]] y = [data.corY[a], data.corY[b]] plt.plot(x, y, 'k', linewidth=1) plt.grid(False) plt.legend(loc='best') plt.show() def print_solution(solution, data): for index, subRoute in enumerate(solution.routes): distance = 0 load = 0 for i in range(len(subRoute) - 1): distance += data.distanceMatrix[subRoute[i]][subRoute[i + 1]] load += data.demand[subRoute[i]] print(f"Route-{index + 1} : {subRoute} , distance: {distance} , load: {load}") def solve(data): # 声明模型 model = Model("VRPTW") # 模型设置 # 关闭输出 model.setParam('OutputFlag', 0) # 定义变量 X = [[[[] for _ in range(data.vehicleNum)] for _ in range(data.nodeNum)] for _ in range(data.nodeNum)] S = [[[] for _ in range(data.vehicleNum)] for _ in range(data.nodeNum)] for i in range(data.nodeNum): for k in range(data.vehicleNum): S[i][k] = model.addVar(data.readyTime[i], data.dueTime[i], vtype=GRB.CONTINUOUS, name=f'S_{i}_{k}') for j in range(data.nodeNum): X[i][j][k] = model.addVar(vtype=GRB.BINARY, name=f"X_{i}_{j}_{k}") # 目标函数 obj = LinExpr(0) for i in range(data.nodeNum): for j in range(data.nodeNum): if i != j: for k in range(data.vehicleNum): obj.addTerms(data.distanceMatrix[i][j], X[i][j][k]) model.setObjective(obj, GRB.MINIMIZE) # 约束1:车辆只能从一个点到另一个点 for i in range(1, data.nodeNum - 1): expr = LinExpr(0) for j in range(data.nodeNum): if i != j: for k in range(data.vehicleNum): if i != 0 and i != data.nodeNum - 1: expr.addTerms(1, X[i][j][k]) model.addConstr(expr == 1) # 约束2:车辆必须从仓库出发 for k in range(data.vehicleNum): expr = LinExpr(0) for j in range(1, data.nodeNum): expr.addTerms(1, X[0][j][k]) model.addConstr(expr == 1) # 约束3:车辆经过一个点就必须离开一个点 for k in range(data.vehicleNum): for h in range(1, data.nodeNum - 1): expr1 = LinExpr(0) expr2 = LinExpr(0) for i in range(data.nodeNum): if h != i: expr1.addTerms(1, X[i][h][k]) for j in range(data.nodeNum): if h != j: expr2.addTerms(1, X[h][j][k]) model.addConstr(expr1 == expr2) # 约束4:车辆最终返回仓库 for k in range(data.vehicleNum): expr = LinExpr(0) for i in range(data.nodeNum - 1): expr.addTerms(1, X[i][data.nodeNum - 1][k]) model.addConstr(expr == 1) # 约束5:车辆容量约束 for k in range(data.vehicleNum): expr = LinExpr(0) for i in range(1, data.nodeNum - 1): for j in range(data.nodeNum): if i != 0 and i != data.nodeNum - 1 and i != j: expr.addTerms(data.demand[i], X[i][j][k]) model.addConstr(expr <= data.capacity) # 约束6:时间窗约束 for k in range(data.vehicleNum): for i in range(data.nodeNum): for j in range(data.nodeNum): if i != j: model.addConstr(S[i][k] + data.distanceMatrix[i][j] - S[j][k] <= M - M * X[i][j][k]) # 记录求解开始时间 start_time = time.time() # 求解 model.optimize() if model.status == GRB.OPTIMAL: print("-" * 20, "Solved Successfully", '-' * 20) # 输出求解总用时 print(f"Solve Time: {time.time() - start_time} s") print(f"Total Travel Distance: {model.ObjVal}") solution = getSolution(data, model) plot_solution(solution, data.customerNum) print_solution(solution, data) else: print("此题无解") if __name__ == '__main__': # 哪个数据集 data_type = "c101" # 数据集路径 data_path = f'../../data/solomn_data/{data_type}.txt' # 顾客个数设置(从上往下读取完 customerNum 个顾客为止,例如c101文件中有100个顾客点, # 但是跑100个顾客点太耗时了,设置这个数是为了只选取一部分顾客点进行计算,用来快速测试算法) # 如果想用完整的顾客点进行计算,设置为None即可 customerNum = 50 # 一个很大的正数 M = 10000000 # 读取数据 data = readData(data_path, customerNum) # 输出相关数据 print("-" * 20, "Problem Information", '-' * 20) print(f'Data Type: {data_type}') print(f'Node Num: {data.nodeNum}') print(f'Customer Num: {data.customerNum}') print(f'Vehicle Num: {data.vehicleNum}') print(f'Vehicle Capacity: {data.capacity}') # 建模求解 solve(data)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248

3.3 运行结果展示

3.3.1 测试案例:c101.txt

设置 customerNum = 20

-------------------- Problem Information -------------------- Data Type: c101 Node Num: 22 Customer Num: 20 Vehicle Num: 25 Vehicle Capacity: 200.0 -------------------- Solved Successfully -------------------- Solve Time: 0.2966279983520508 s Total Travel Distance: 160.81590595966603 Route-1 : [0, 20, 13, 17, 18, 19, 15, 16, 14, 12, 0] , distance: 101.32767502613292 , load: 200.0 Route-2 : [0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 0] , distance: 59.48823093353308 , load: 160.0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

在这里插入图片描述

设置 customerNum = 50

Data Type: c101 Node Num: 52 Customer Num: 50 Vehicle Num: 25 Vehicle Capacity: 200.0 -------------------- Solved Successfully -------------------- Solve Time: 4.383494138717651 s Total Travel Distance: 363.2468004115909 Route-1 : [0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 0] , distance: 59.48823093353308 , load: 160.0 Route-2 : [0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0] , distance: 97.2271627850669 , load: 200.0 Route-3 : [0, 43, 42, 41, 40, 44, 46, 45, 48, 50, 49, 47, 0] , distance: 59.843107259523165 , load: 140.0 Route-4 : [0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21, 0] , distance: 50.80359030264955 , load: 170.0 Route-5 : [0, 13, 17, 18, 19, 15, 16, 14, 12, 0] , distance: 95.88470913081827 , load: 190.0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

在这里插入图片描述

设置 customerNum = None

-------------------- Problem Information -------------------- Data Type: c101 Node Num: 102 Customer Num: 100 Vehicle Num: 25 Vehicle Capacity: 200.0 -------------------- Solved Successfully -------------------- Solve Time: 272.5895857810974 s Total Travel Distance: 828.9368669428341 Route-1 : [0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21, 0] , distance: 50.80359030264955 , load: 170.0 Route-2 : [0, 57, 55, 54, 53, 56, 58, 60, 59, 0] , distance: 101.88256760196126 , load: 200.0 Route-3 : [0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0] , distance: 59.618077542105574 , load: 180.0 Route-4 : [0, 98, 96, 95, 94, 92, 93, 97, 100, 99, 0] , distance: 95.94313062205805 , load: 190.0 Route-5 : [0, 81, 78, 76, 71, 70, 73, 77, 79, 80, 0] , distance: 127.29748041459519 , load: 150.0 Route-6 : [0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0] , distance: 97.2271627850669 , load: 200.0 Route-7 : [0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0] , distance: 64.80747449698114 , load: 160.0 Route-8 : [0, 90, 87, 86, 83, 82, 84, 85, 88, 89, 91, 0] , distance: 76.06956532288787 , load: 170.0 Route-9 : [0, 13, 17, 18, 19, 15, 16, 14, 12, 0] , distance: 95.88470913081827 , load: 190.0 Route-10 : [0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0] , distance: 59.403108723710105 , load: 200.0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

在这里插入图片描述

3.3.2 测试案例:r101.txt

设置 customerNum = 20

-------------------- Problem Information -------------------- Data Type: r101 Node Num: 22 Customer Num: 20 Vehicle Num: 25 Vehicle Capacity: 200.0 -------------------- Solved Successfully -------------------- Solve Time: 0.9535932540893555 s Total Travel Distance: 463.69270291007086 Route-1 : [0, 9, 20, 1, 0] , distance: 74.91992978886165 , load: 35.0 Route-2 : [0, 12, 3, 4, 0] , distance: 76.18033988749895 , load: 51.0 Route-3 : [0, 2, 15, 13, 0] , distance: 62.180339887498945 , load: 38.0 Route-4 : [0, 5, 18, 8, 17, 0] , distance: 86.57837545317302 , load: 49.0 Route-5 : [0, 14, 16, 6, 0] , distance: 72.40405733948208 , load: 42.0 Route-6 : [0, 11, 19, 7, 10, 0] , distance: 91.42966055355615 , load: 50.0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

在这里插入图片描述

设置 customerNum = 50

-------------------- Problem Information -------------------- Data Type: r101 Node Num: 52 Customer Num: 50 Vehicle Num: 25 Vehicle Capacity: 200.0 -------------------- Solved Successfully -------------------- Solve Time: 4.6791017055511475 s Total Travel Distance: 946.6603871872358 Route-1 : [0, 21, 40, 26, 0] , distance: 43.35023188854984 , load: 37.0 Route-2 : [0, 33, 29, 9, 34, 24, 25, 0] , distance: 139.4708769010923 , load: 59.0 Route-3 : [0, 39, 23, 41, 22, 4, 0] , distance: 99.11062351878482 , load: 102.0 Route-4 : [0, 28, 12, 3, 50, 0] , distance: 51.94121366484106 , load: 61.0 Route-5 : [0, 36, 47, 11, 19, 49, 10, 32, 1, 0] , distance: 154.4302586824376 , load: 140.0 Route-6 : [0, 42, 14, 44, 16, 38, 37, 17, 0] , distance: 131.9204195702968 , load: 88.0 Route-7 : [0, 2, 15, 43, 13, 0] , distance: 72.54724253800985 , load: 45.0 Route-8 : [0, 45, 8, 46, 48, 0] , distance: 84.49944230335126 , load: 62.0 Route-9 : [0, 5, 7, 18, 6, 0] , distance: 73.5917360311745 , load: 46.0 Route-10 : [0, 27, 31, 30, 20, 35, 0] , distance: 95.79834208869767 , load: 81.0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

在这里插入图片描述

设置 customerNum = 70

-------------------- Problem Information -------------------- Data Type: r101 Node Num: 72 Customer Num: 70 Vehicle Num: 25 Vehicle Capacity: 200.0 -------------------- Solved Successfully -------------------- Solve Time: 189.01783299446106 s Total Travel Distance: 1182.9787814963945 Route-1 : [0, 63, 62, 11, 64, 49, 48, 0] , distance: 125.38755919928242 , load: 116.0 Route-2 : [0, 65, 66, 20, 32, 70, 0] , distance: 117.49399251197822 , load: 82.0 Route-3 : [0, 28, 12, 26, 0] , distance: 33.795507476994075 , load: 52.0 Route-4 : [0, 33, 29, 3, 50, 68, 0] , distance: 90.77710269056311 , load: 82.0 Route-5 : [0, 2, 15, 41, 22, 56, 4, 0] , distance: 88.90058825018636 , load: 63.0 Route-6 : [0, 27, 69, 31, 30, 51, 9, 34, 35, 1, 0] , distance: 111.48892006549234 , load: 128.0 Route-7 : [0, 45, 8, 46, 17, 60, 0] , distance: 93.91701945260407 , load: 31.0 Route-8 : [0, 59, 42, 14, 44, 38, 57, 43, 58, 0] , distance: 131.96251141349887 , load: 119.0 Route-9 : [0, 39, 23, 67, 55, 54, 24, 25, 0] , distance: 140.03829072128988 , load: 114.0 Route-10 : [0, 52, 18, 6, 0] , distance: 41.290161379846566 , load: 24.0 Route-11 : [0, 36, 47, 19, 7, 10, 0] , distance: 107.49141646738926 , load: 70.0 Route-12 : [0, 21, 40, 53, 0] , distance: 36.27916407668437 , load: 34.0 Route-13 : [0, 5, 61, 16, 37, 13, 0] , distance: 64.15654779058515 , load: 89.0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

在这里插入图片描述

标签:
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

在线投稿:投稿 站长QQ:1888636

后台-插件-广告管理-内容页尾部广告(手机)
关注我们

扫一扫关注我们,了解最新精彩内容

搜索
排行榜