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

【运筹优化】带时间窗约束的车辆路径规划问题（VRPTW）详解 + Python 调用 Gurobi 建模求解 文章目录一、概述1.1 VRP 问题1.2 CVRP 问题1.3 VRPTW 问题二、VRPTW 的一般模型三、Python 调用 Gurobi 建模求解3.1 Solomn 数据集3.2 完整代码3.3 运行结果展示3.3.1 测试案例：c101.txt3.3.2 测试案例：r101.txt一、概述1.1 VRP 问题

推荐整理分享【运筹优化】带时间窗约束的车辆路径规划问题（VRPTW）详解 + Python 调用 Gurobi 建模求解(运筹最优化方法有哪些)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:运筹优化前景,运筹优化常用模型、算法及案例实战,运筹优化与决策方法,运筹优化方法,运筹优化软件有哪些,运筹优化是什么意思,运筹优化是什么意思,运筹优化问题实例,内容如对您有帮助，希望把文章链接给更多的朋友！

车辆路径规划问题(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的所有约束，还需要考虑时间窗约束，也就是每个顾客对应一个时间窗[ei,li][e_i,l_i][ei​,li​]，其中 eie_iei​ 和 lil_ili​ 分别代表该点的最早到达时间和最晚到达时间。顾客点 i∈Vi \in Vi∈V 的需求必须要在其时间窗内被送达

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

二、VRPTW 的一般模型

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

xij={1，如果在最优解中，弧(i,j)被车辆k选中，其他sik=车辆k到达i的时间模型中涉及的其他参数为:tij表示车辆在弧(i,j)上的行驶时间M为一个足够大的正数{x_i}_j=\begin{cases} 1\text{，如果在最优解中，弧}\left( i,j \right) \text{被车辆}k\text{选中}\\ 0\text{，其他}\\ \end{cases} \\ {s_i}_k=\text{车辆}k\text{到达}i\text{的时间} \\ \text{模型中涉及的其他参数为}: \\ {t_i}_j\text{表示车辆在弧}\left( i,j \right) \text{上的行驶时间} \\ M\text{为一个足够大的正数}xi​j​={1，如果在最优解中，弧(i,j)被车辆k选中0，其他​si​k​=车辆k到达i的时间模型中涉及的其他参数为:ti​j​表示车辆在弧(i,j)上的行驶时间M为一个足够大的正数

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

M=max{bi+tij−aj},∀(i,j)∈AM=max\{b_i+t_{ij}-a_j\} , \forall (i,j)\in AM=max{bi​+tij​−aj​},∀(i,j)∈A

综合上面引出的决策变量，并参考文献（Desaulniers et al.，2006），给出的 VRPTW 的标准模型如下：

min⁡∑k∈K∑i∈V∑i∈Vcijxijks.t.∑k∈K∑j∈Vxijk=1,∀i∈C  ∑j∈Vxjk=1,∀k∈K  ∑i∈Vxihk−∑j∈Vxhjk=,∀h∈C,∀k∈K  ∑i∈Vxi,n+1,k=1,∀k∈K  ∑i∈Cqi∑j∈Vxijk=1,∀k∈K  sik+tij−M(1−xijk)⩽sjk  ,∀(i,j)∈A,∀k∈K  ei⩽sik⩽li  ,∀i∈V,∀k∈K  xijk∈{,1}  ,∀(i,j)∈A,∀k∈K\min \sum_{k\in K}{\sum_{i\in V}{\sum_{i\in V}{{c_i}_j{x_i}_{j_k}}}} \\ s.t. \sum_{k\in K}{\sum_{j\in V}{{x_i}_{j_k}=1 , \forall i\in C}} \\ \,\, \sum_{j\in V}{{x_0}_{j_k}=1 , \forall k\in K} \\ \,\, \sum_{i\in V}{{x_i}_{h_k}-\sum_{j\in V}{{x_h}_{j_k}=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_i}_{j_k}=1 , \forall k\in K}} \\ \,\, {s_i}_k+{t_i}_j-M\left( 1-{x_i}_{j_k} \right) \leqslant {s_j}_k\,\,, \forall \left( i,j \right) \in A,\forall k\in K \\ \,\, e_i\leqslant {s_i}_k\leqslant l_i\,\,, \forall i\in V,\forall k\in K \\ \,\, {x_i}_{j_k}\in \left\{ 0,1 \right\} \,\,, \forall \left( i,j \right) \in A,\forall k\in Kmink∈K∑​i∈V∑​i∈V∑​ci​j​xi​jk​​s.t.k∈K∑​j∈V∑​xi​jk​​=1,∀i∈Cj∈V∑​x0​jk​​=1,∀k∈Ki∈V∑​xi​hk​​−j∈V∑​xh​jk​​=0,∀h∈C,∀k∈Ki∈V∑​xi,n+1,k​=1,∀k∈Ki∈C∑​qi​j∈V∑​xi​jk​​=1,∀k∈Ksi​k​+ti​j​−M(1−xi​jk​​)⩽sj​k​,∀(i,j)∈A,∀k∈Kei​⩽si​k​⩽li​,∀i∈V,∀k∈Kxi​jk​​∈{0,1},∀(i,j)∈A,∀k∈K

其中：

目标函数是为了最小化所有车辆的总行驶成本（距离）约束1~4保证了每辆车必须从仓库出发，经过一个点就离开那个点，最终返回仓库约束5为车辆的容量约束约束6~7是时间窗约束，保证了车辆到达每个顾客点的时间均在时间窗内，点n+1是点o的一个备份，是为了方便实现。三、Python 调用 Gurobi 建模求解3.1 Solomn 数据集

Solomn 数据集下载地址

3.2 完整代码

注意，在下面代码中，将弧 iii 到弧 jjj 所需的时间 tijt_{ij}tij​ 和 成本 cijc_{ij}cij​ 都当作了弧 iii 到弧 jjj 所需的距离来看待

# -*- coding: utf-8 -*-## Author: WSKH# Blog: wskh0929.blog.csdn.net# Time: 2023/2/8 11:14# Description: Python 调用 Gurobi 建模求解 VRPTW 问题import timeimport matplotlib.pyplot as pltimport numpy as npfrom 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 dataclass 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 solutiondef 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): #