时间窗约束车辆路径算法 怎么考虑时间窗（【运筹优化】带时间窗约束的车辆路径规划问题（VRPTW）详解 + Python 调用 Gurobi 建模求解）
一 、概述
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
i∈V 的需求必须要在其时间窗内被送达VRPTW 已经被证明是 NP-hard 问题 ，其求解复杂度随着问题规模的增加而急剧增加 ，求解较为困难 。到目前为止 ，求解 VRPTW 的比较高效的精确算法是分支定价算法和分支定价切割算法 。
二 、VRPTW 的一般模型
VRPTW 可以建模为一个混合整数规划问题 ，在给出完整数学模型之前 ，先引入下面的决策变量：
x
i
j
=
{
1
，如果在最优解中 ，弧
(
i
,
j
)
被车辆
k
选中
，其他
s
i
k
=
车辆
k
到达
i
的时间
模型中涉及的其他参数为
:
t
i
j
表示车辆在弧
(
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{为一个足够大的正数}
xij={1 ，如果在最优解中 ，弧(i,j)被车辆k选中0 ，其他sik=车辆k到达i的时间模型中涉及的其他参数为:tij表示车辆在弧(i,j)上的行驶时间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+tij−aj},∀(i,j)∈A综合上面引出的决策变量 ，并参考文献（Desaulniers et al. ，2006） ，给出的 VRPTW 的标准模型如下：
min
∑
k
∈
K
∑
i
∈
V
∑
i
∈
V
c
i
j
x
i
j
k
s
.
t
.
∑
k
∈
K
∑
j
∈
V
x
i
j
k
=
1
,
∀
i
∈
C
∑
j
∈
V
x
j
k
=
1
,
∀
k
∈
K
∑
i
∈
V
x
i
h
k
−
∑
j
∈
V
x
h
j
k
=
,
∀
h
∈
C
,
∀
k
∈
K
∑
i
∈
V
x
i
,
n
+
1
,
k
=
1
,
∀
k
∈
K
∑
i
∈
C
q
i
∑
j
∈
V
x
i
j
k
=
1
,
∀
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
∈
{
,
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 K
mink∈K∑i∈V∑i∈V∑cijxijks.t.k∈K∑j∈V∑xijk=1,∀i∈Cj∈V∑x0jk=1,∀k∈Ki∈V∑xihk−j∈V∑xhjk=0,∀h∈C,∀k∈Ki∈V∑xi,n+1,k=1,∀k∈Ki∈C∑qij∈V∑xijk=1,∀k∈Ksik+tij−M(1−xijk)⩽sjk,∀(i,j)∈A,∀k∈Kei⩽sik⩽li,∀i∈V,∀k∈Kxijk∈{0,1},∀(i,j)∈A,∀k∈K其中：
目标函数是为了最小化所有车辆的总行驶成本（距离） 约束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=fS_{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(fData Type: {data_type}) print(fNode Num: {data.nodeNum}) print(fCustomer Num: {data.customerNum}) print(fVehicle Num: {data.vehicleNum}) print(fVehicle Capacity: {data.capacity}) # 建模求解 solve(data)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,创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！