车辆路径优化问题（VRP）变体及数学模型_vrp问题模型

车辆路径优化问题（Vehicle Routing Problem，VRP）是一种非常常见的优化问题，在给定一组客户点、车辆容量、车辆数量、起始点和终点，目标是找到使得所有客户点都被访问一次的最短路径方案。VRP有很多变体：

• 旅行商问题（Travelling salesman problem，TSP） the classic routing problem in which there is just one vehicle.
• 车辆路径问题（Vehicle Routing Problem，VRP）， a generalisation of the TSP with multiple vehicles.
• VRP with capacity constraints, in which vehicles have maximum capacities for the items they can carry.
• 带时间窗的车辆路径规划问题（VRP with time windows，VRPTW），where the vehicles must visit the locations in specified time intervals.
• VRP with resource constraints, such as space or personnel to load and unload vehicles at the depot (the starting point for the routes).
• VRP with dropped visits, where the vehicles aren’t required to visit all locations, but must pay a penalty for each visit that is dropped.

一、旅行商问题（Travelling salesman problem，TSP）

最经典的的车辆路径优化问题是旅行商问题（Travelling salesman problem，TSP），给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

TSP问题数学模型

刘兴禄 -《运筹优化常用模型、算法及案例实战：Python+Java实现》总结了TSP问题共有3种数学模型：

1. Dantzig-Fulkerson-Johnson model，DFJ模型（本文采用）
2. Miller-Tucker-Zemlin model，MTZ模型
3. 1-tree模型

DFJ模型，也是最常见的模型如下：

min ⁡ ∑ i ∈ V ∑ j ∈ V d i j x i j subject to ∑ j ∈ V x i j = 1 , ∀ i ∈ V , i ≠ j ∑ i ∈ V x i j = 1 , ∀ j ∈ V , i ≠ j ∑ i , j ∈ S x i j ≤ ∣ S ∣ − 1 , 2 ≤ ∣ S ∣ ≤ N − 1 , S ⊂ V x i j ∈ { 0 , 1 } , ∀ i , j ∈ V

$$\begin{align} \min \quad & \sum_{i \in V}{}\sum_{j \in V} d_{ij}x_{ij}\\ \text{subject to} \quad &\sum_{j \in V} x_{ij} = 1, \quad \forall i \in V,i \neq j \\ &\sum_{i \in V}{x_{ij}} =1,\quad \forall j \in V ,i \neq j\\ & \textcolor{red}{\sum_{i,j \in S}{x_{ij}} \leq |S|-1,\quad 2\leq |S| \leq N-1, S \subset V}\\ &x_{ij} \in \{0,1\}, \quad \forall i,j \in V \end{align}$$ minsubject to​i∈V∑​j∈V∑​dij​xij​j∈V∑​xij​=1,∀i∈V,i=ji∈V∑​xij​=1,∀j∈V,i=ji,j∈S∑​xij​≤∣S∣−1,2≤∣S∣≤N−1,S⊂Vxij​∈{0,1},∀i,j∈V​​

这个subtour-elimination的约束，是一个枚举的约束，我们不能在建模的时候就直接全枚举，这样的话有复杂度的情况。等到把这些约束枚举完，黄花菜都凉了。 啰嗦几句，subtour-elimination的思路就是相当于cutting plane。在原来前两个约束的基础上，加上这个约束。但是如果你要在求解步骤model.optimize()之前就想全枚举，把subtour-elimination所有可能的
个约束全加上去，其他的不论，就只是加约束所耗费的时间，别人TSP早都解完去写Paper了，你这边约束还没加完。得不偿失，因此不能硬钢去枚举。

那怎么办呢？业内一般采用Gurobi或者CPLEX求解器中提供的callback(回调函数)的方法来动态的添加subtour-elimination约束。总的来讲，就是在branch and bound tree迭代的过程中，根据当前结点的松弛后的线性规划模型(relaxed LP)的解，来检查该解是否有存在子环路 subtour，如果有，我们就把执行subtour-elimination时候产生的破圈约束加到正在求解的模型中去; 如果没有，我们就直接接着迭代算法。

TSP问题求解

• TSP中两种不同消除子环路的方法及callback实现
• 基于蚁群算法的TSP问题建模求解（Python）
• 基于模拟退火算法的TSP问题建模求解（Python）
• 基于自适应遗传算法的TSP问题建模求解（Java）
• 基于禁忌搜索的TSP问题建模求解（Java）

二、车辆路径问题（Vehicle Routing Problem，VRP）

基本车辆路径问题（Vehicle Routing Problem，VRP）的数学模型可以使用整数线性规划（Integer Linear Programming，ILP）来表示。

min ⁡ ∑ k ∈ V ∑ i ∈ N ∑ j ∈ N c i j x i j k subject to ∑ k ∈ V ∑ j ∈ N x i j k = 1 , ∀ i ∈ C ∑ j ∈ N x 0 j k = 1 , ∀ k ∈ V , ∑ i ∈ N x i h k − ∑ j ∈ N x h j k = 0 , ∀ h ∈ C , ∀ k ∈ V , ∑ i ∈ N x i , n + 1 , k = 1 ∀ k ∈ V , s i k + t i j − M i j ( 1 − x i j k ) ⩽ s j k , ∀ i , j ∈ N , ∀ k ∈ V , a i ⩽ s i k ⩽ b i , ∀ i ∈ N , ∀ k ∈ V ,  x i j k ∈ { 0 , 1 } , ∀ i , j ∈ N , ∀ k ∈ V s i k ≥ 0 , ∀ i ∈ N , ∀ k ∈ V

$$\begin{align} \min \quad &\sum_{k \in \mathcal{V}} \sum_{i \in \mathcal{N}} \sum_{j \in \mathcal{N}} c_{i j} x_{i j k} \\ \text {subject to} \quad &\sum_{k \in \mathcal{V}} \sum_{j \in \mathcal{N}} x_{i j k}=1, \quad \forall i \in \mathcal{C} \\ &\sum_{j \in \mathcal{N}} x_{0 j k}=1, \quad \forall k \in \mathcal{V}, \\ &\sum_{i \in \mathcal{N}} x_{i h k}-\sum_{j \in \mathcal{N}} x_{h j k}=0 , \quad \forall h \in \mathcal{C}, \forall k \in \mathcal{V}, \\ &\sum_{i \in \mathcal{N}} x_{i, n+1, k}=1 \quad \forall k \in \mathcal{V}, \\ &s_{i k}+t_{i j}-M_{i j}\left(1-x_{i j k}\right) \leqslant s_{j k}, \quad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{V}, \\ &a_{i} \leqslant s_{i k} \leqslant b_{i} , \quad \forall i \in \mathcal{N}, \forall k \in \mathcal{V} \text {, } \\ &x_{i j k} \in\{0,1\}, \quad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{V} \\ &s_{i k} \geq 0, \quad \forall i \in \mathcal{N}, \forall k \in \mathcal{V} \\ \end{align}$$ minsubject to​k∈V∑​i∈N∑​j∈N∑​cij​xijk​k∈V∑​j∈N∑​xijk​=1,∀i∈Cj∈N∑​x0jk​=1,∀k∈V,i∈N∑​xihk​−j∈N∑​xhjk​=0,∀h∈C,∀k∈V,i∈N∑​xi,n+1,k​=1∀k∈V,sik​+tij​−Mij​(1−xijk​)⩽sjk​,∀i,j∈N,∀k∈V,ai​⩽sik​⩽bi​,∀i∈N,∀k∈V, xijk​∈{0,1},∀i,j∈N,∀k∈Vsik​≥0,∀i∈N,∀k∈V​​

三、带容量约束的车辆路径优化问题（Capacitated Vehicle Routing Problem，CVRP）

带容量约束的车辆路径优化问题，CVRP，对一系列装卸货点进行适当的路径规划，在满足约束条件（客户需求、车辆载重和容积、车型、车辆行驶里程、配送中心数量等限制）和目标最优化（路程最短、成本最低、使用车辆数最少、配送时间最快等）下，将客户的配送需求从配送中心送达客户点，或从客户点送回配送中心。

场景：
单向：纯取货 / 纯送货；
单配送中心：只有一个配送中心/车场；
单车型：只考虑一种车型，
需求不可拆分：客户需求只能有一辆车满足；
车辆封闭：完成配送任务的车辆需回到配送中心；
车辆充足：不限制车辆数量，即配送车辆需求均能满足；
非满载：任意客户点的需求量小于车辆最大载重；

要求：
优化目标：最小化车辆启动成本和车辆行驶成本之和；
约束条件：车辆行驶距离约束，重量约束；
算法输入：配送中心位置、客户点位置、客户点需求、车辆最大载重、车辆最大行驶距离、车辆启动成本、车辆单位距离行驶成本；
算法输出：每辆车的行驶路径，经过的客户点，以及总成本。

CVRP问题求解

基于遗传算法的CVRP建模求解（Python）

四、带时间窗车辆路径优化问题（Vehicle Routing Problem with Time Window，VRPTW）

问题描述
VRPTW问题定义在一队车辆$\mathcal{V}$、一组客户$\mathcal{C}$和一个有向图$\mathcal{G}$上。图由$|\mathcal{C}|+2$个点组成，其中客户由$1,2,\cdots ,n$表示，车站由$0$（始发站）和$n+1$（终点站）表示。所有节点的集合可表示为 N = { 0 , 1 , 2 , ⋯   , n , n + 1 } \mathcal{N}=\{0,1,2,\cdots,n,n+1\} N={0,1,2,⋯,n,n+1}。所有边的集合$\mathcal{A}$表示了车站与客户之间，以及客户之间的有向连接。其中没有边从$0$点终止或者从$n+1$点开始。每一条弧$(i,j),i\ne j$都对应一个成本$c_{ij}$和时间$t_{ij}$，时间可以包括在弧上$(i,j)$的行驶时间和在$i$点的服务时间。所有车辆通常是同质化的，每辆车都存在容量上限$Q$，每一个客户点$i$都有需要被满足的需求$d_i$，并且需要在时间窗$[a_i,b_i]$之内被服务[1]。待优化的问题即为，如何决策车辆访问客户的路径，使得在满足一定约束的条件下，实现最小化总成本的目标。

模型构建
参数

• $\mathcal{V}$：车辆集合， V = { 0 , 1 , ⋯   , V } \mathcal{V}=\{0,1,\cdots, V\} V={0,1,⋯,V}；
• $\mathcal{C}$：客户集合， C = { 0 , 1 , ⋯   , n } \mathcal{C}=\{0,1,\cdots, n\} C={0,1,⋯,n}；
• $\mathcal{N}$：节点集合， N = { 0 , 1 , 2 , ⋯   , n , n + 1 } \mathcal{N}=\{0,1,2,\cdots,n,n+1\} N={0,1,2,⋯,n,n+1}；
• $c_{ij}$：从$i$到$j$的行驶距离；
• $d_i$：每一个客户点$i$都有需要被满足的需求量；
• $Q$：车辆容量；
• $t_{ij}$：从$i$点到$j$点的行驶时间，以及服务$i$点的时间之和；
• $[a_i,b_i]$：访问$i$点的时间窗；
• $M_{ij}$：足够大的正数。

决策变量

• $x_{ijk}$：车辆路径决策变量，$x_{ijk}=1$，车辆$k$经过弧$(i,j)$。
• $s_{ik}$：车辆$k$服务$i$点的开始时刻；

混合整数规划模型

min ⁡ ∑ k ∈ V ∑ i ∈ N ∑ j ∈ N c i j x i j k subject to ∑ i ∈ C d i ∑ j ∈ N x i j k ⩽ Q , ∀ k ∈ V , ∑ k ∈ V ∑ j ∈ N x i j k = 1 , ∀ i ∈ C ∑ j ∈ N x 0 j k = 1 , ∀ k ∈ V , ∑ i ∈ N x i h k − ∑ j ∈ N x h j k = 0 , ∀ h ∈ C , ∀ k ∈ V , ∑ i ∈ N x i , n + 1 , k = 1 ∀ k ∈ V , s i k + t i j − M i j ( 1 − x i j k ) ⩽ s j k , ∀ i , j ∈ N , ∀ k ∈ V , a i ⩽ s i k ⩽ b i , ∀ i ∈ N , ∀ k ∈ V ,  x i j k ∈ { 0 , 1 } , ∀ i , j ∈ N , ∀ k ∈ V s i k ≥ 0 , ∀ i ∈ N , ∀ k ∈ V

$$\begin{align} \min \quad &\sum_{k \in \mathcal{V}} \sum_{i \in \mathcal{N}} \sum_{j \in \mathcal{N}} c_{i j} x_{i j k} \\ \text {subject to} \quad &\sum_{i \in \mathcal{C}} d_{i} \sum_{j \in \mathcal{N}} x_{i j k} \leqslant Q, \quad \forall k \in \mathcal{V}, \\ &\sum_{k \in \mathcal{V}} \sum_{j \in \mathcal{N}} x_{i j k}=1, \quad \forall i \in \mathcal{C} \\ &\sum_{j \in \mathcal{N}} x_{0 j k}=1, \quad \forall k \in \mathcal{V}, \\ &\sum_{i \in \mathcal{N}} x_{i h k}-\sum_{j \in \mathcal{N}} x_{h j k}=0 , \quad \forall h \in \mathcal{C}, \forall k \in \mathcal{V}, \\ &\sum_{i \in \mathcal{N}} x_{i, n+1, k}=1 \quad \forall k \in \mathcal{V}, \\ &s_{i k}+t_{i j}-M_{i j}\left(1-x_{i j k}\right) \leqslant s_{j k}, \quad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{V}, \\ &a_{i} \leqslant s_{i k} \leqslant b_{i} , \quad \forall i \in \mathcal{N}, \forall k \in \mathcal{V} \text {, } \\ &x_{i j k} \in\{0,1\}, \quad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{V} \\ &s_{i k} \geq 0, \quad \forall i \in \mathcal{N}, \forall k \in \mathcal{V} \\ \end{align}$$ minsubject to​k∈V∑​i∈N∑​j∈N∑​cij​xijk​i∈C∑​di​j∈N∑​xijk​⩽Q,∀k∈V,k∈V∑​j∈N∑​xijk​=1,∀i∈Cj∈N∑​x0jk​=1,∀k∈V,i∈N∑​xihk​−j∈N∑​xhjk​=0,∀h∈C,∀k∈V,i∈N∑​xi,n+1,k​=1∀k∈V,sik​+tij​−Mij​(1−xijk​)⩽sjk​,∀i,j∈N,∀k∈V,ai​⩽sik​⩽bi​,∀i∈N,∀k∈V, xijk​∈{0,1},∀i,j∈N,∀k∈Vsik​≥0,∀i∈N,∀k∈V​​

下面是各个约束的具体含义：

• 目标函数(1)最小化总体行驶距离；
• 约束(2)说明车辆的载重量不能超过其容量上限；
• 约束(3)保证了每个客户点都被访问了一次；
• 约束(4-6)分别保证了每辆车必须从始发站出发，到达并离开每个客户点，并最终回到终点站；
• 约束(7)规定了车辆开始服务点的时刻，不能早于开始服务点的时刻，加上从点到 - 点的行驶时间以及服务点的时间之和，其中的取值下界为；
• 约束(8)使得开始服务点的时刻是在规定的时间窗范围内；
• 约束(9-10)是对于决策变量的约束。

VRPTW问题求解

• 考虑随机性的车辆路径规划问题详解(Stochastic VRP) 数据魔术师
• 使用Java调用Cplex求解带时间窗的车辆路径问题

五、取送货问题数学模型（Homogeneous Multi vehicle pickup and delivery problem formulations）

参数

• $n$：取货点数量。
• $\tilde{n}$：送货点数量，因为这里是Paired PDP问题，故$n=\tilde{n}$。
• $P$：取货点集合， P = { 1 , . . . , n } P = \{1,..., n\} P={1,...,n}
• $D$：送货点集合， D = { n + 1 , . . . , n + n ~ } D = \{n +1,..., n +\tilde{n}\} D={n+1,...,n+n~}
• $K$：车辆集合
• $q_i$：客户点$i$的需求量（供应量），如果是取货点，则$q_i>0$；如果是送货点，则$q_i<0$；如果是起点0、终点，则$n+\tilde{n}+1$，则$q_0=q_{n+\tilde{n}+1}=0$。
• $e_i$：客户点$i$允许的最早开始服务时间。
• $l_i$：客户点$i$允许的最晚开始服务时间。
• $d_i$：客户点$i$的服务时间（作业时间）。
• $L_i$：客户点$i$的服务时间（作业时间）。
• $C^k$：车辆$k$的容量。
• $T^k$：车辆$k$作业时间上限（maximum route duration of vehicle/route k）
  决策变量
• $x_{ijk}$：车辆路径决策变量，$x_{ijk}=1$，车辆$k$经过弧$(i,j)$；
• $Q_i^k$：车辆$k$离开节点$i$时的装载量；
• $B_i^k$：车辆$k$服务$i$点的开始时刻；

混合整数规划模型
min ⁡ ∑ k ∈ K ∑ ( i , j ) ∈ A c i j k x i j k subject to. ∑ k ∈ K ∑ j : ( i , j ) ∈ A x i j k = 1 ∀ i ∈ P ∪ D , ∑ j : ( 0 , j ) ∈ A x 0 j k = 1 ∀ k ∈ K , ∑ i : ( i , n + n ~ + 1 ) ∈ A x i , n + n ~ + 1 k = 1 ∀ k ∈ K , ∑ i : ( i , j ) ∈ A x i j k − ∑ i : ( j , i ) ∈ A x j i k = 0 ∀ j ∈ P ∪ D , k ∈ K , x i j k = 1 ⇒ B j k ≥ B i k + d i + t i j k ∀ ( i , j ) ∈ A , k ∈ K , x i j k = 1 ⇒ Q j k = Q i k + q j ∀ ( i , j ) ∈ A , k ∈ K , max ⁡ { 0 , q i } ≤ Q i k ≤ min ⁡ { C k , C k + q i } ∀ i ∈ V , k ∈ K , ∑ j : ( i , j ) ∈ A x i j k − ∑ j : ( n + i , j ) ∈ A x n + i , j k = 0 ∀ i ∈ P , k ∈ K B i k ≤ B n + i k ∀ i ∈ P , k ∈ K . e i ≤ B i k ≤ l i ∀ i ∈ V , k ∈ K , e i ≤ B i k ≤ l i ∀ i ∈ V , k ∈ K , B n + n ~ + 1 k − B 0 k ≤ T k ∀ k ∈ K , x i j k ∈ { 0 , 1 } ∀ ( i , j ) ∈ A , k ∈ K

$$\begin{align} \min \quad & \sum_{k\in K}\sum_{(i,j) \in A} c_{ij}^k x_{ij}^k \\ \text{subject to.} \quad &\sum_{k \in K} \sum_{j:(i, j) \in A} x_{i j}^{k} =1 & \forall i \in P \cup D, \\ &\sum_{j:(0, j) \in A} x_{0 j}^{k}=1 & \forall k \in K, \\ &\sum_{i:(i, n+\tilde{n}+1) \in A} x_{i, n+\tilde{n}+1}^{k} =1 & \forall k \in K, \\ &\sum_{i:(i, j) \in A} x_{i j}^{k}-\sum_{i:(j, i) \in A} x_{j i}^{k} =0 &\forall j \in P \cup D, k \in K, \\ &x_{i j}^{k}=1 \Rightarrow B_{j}^{k} \geq B_{i}^{k}+d_{i}+t_{i j}^{k} & \forall(i, j) \in A, k \in K, \\ &x_{i j}^{k}=1 \Rightarrow Q_{j}^{k} =Q_{i}^{k}+q_{j} & \forall(i, j) \in A, k \in K, \\ &\max \left\{0, q_{i}\right\} \leq Q_{i}^{k} \leq \min \left\{C^{k}, C^{k}+q_{i}\right\} & \forall i \in V, k \in K, \\ & \sum_{j:(i, j) \in A} x_{i j}^{k}-\sum_{j:(n+i, j) \in A} x_{n+i, j}^{k}=0 \quad \forall i \in P, k \in K\\ & B_{i}^{k} \leq B_{n+i}^{k} \quad \forall i \in P, k \in K . & e_i \leq B_i^k \leq l_i & \forall i \in V, k \in K,\\ & e_i \leq B_i^k \leq l_i & \forall i \in V, k \in K,\\ & B_{n+\tilde{n}+1}^k -B_{0}^k \leq T^k &\forall k \in K,\\ &x_{i j}^{k} \in\{0,1\} & \forall(i, j) \in A, k \in K \\ \end{align}$$ minsubject to.​k∈K∑​(i,j)∈A∑​cijk​xijk​k∈K∑​j:(i,j)∈A∑​xijk​=1j:(0,j)∈A∑​x0jk​=1i:(i,n+n~+1)∈A∑​xi,n+n~+1k​=1i:(i,j)∈A∑​xijk​−i:(j,i)∈A∑​xjik​=0xijk​=1⇒Bjk​≥Bik​+di​+tijk​xijk​=1⇒Qjk​=Qik​+qj​max{0,qi​}≤Qik​≤min{Ck,Ck+qi​}j:(i,j)∈A∑​xijk​−j:(n+i,j)∈A∑​xn+i,jk​=0∀i∈P,k∈KBik​≤Bn+ik​∀i∈P,k∈K.ei​≤Bik​≤li​Bn+n~+1k​−B0k​≤Tkxijk​∈{0,1}​∀i∈P∪D,∀k∈K,∀k∈K,∀j∈P∪D,k∈K,∀(i,j)∈A,k∈K,∀(i,j)∈A,k∈K,∀i∈V,k∈K,ei​≤Bik​≤li​∀i∈V,k∈K,∀k∈K,∀(i,j)∈A,k∈K​∀i∈V,k∈K,​​

• 目标函数（1）最小化总体行驶成本；
• 约束（2）保证了每个客户点都被访问了一次；
• 约束（3-5）分别保证了每辆车必须从始发站出发，到达并离开每个客户点，并最终回到终点站；
• 约束（6）消除子回路，
• 约束（7-8）车辆容量约束
• 约束（9），联结约束（coupling constraint），同一需求的起点和终点都必须是同一辆车提供服务
• 约束（10），优先级约束（precedence constraint），针对每一货运需求，取货任 务的服务顺序须于送货任务前。
• 约束（11）时间窗约束
• 约束（12）路径时长限制

【注】约束（6）和（7）是非线性的，可以用大M进行线性化

PDPTW问题求解

PDPTW数据集地址

https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/