优化算法 | 多车型车辆路径问题-初始解构造方法

xiaozongpeng · 发表于 2022-3-4 21:48

今天为各位讲解一个基本车辆路径问题的衍生问题-多车型车辆路径问题（heterogeneous fleet vehicle routing problem，HFVRP）。其中HFVRP还分为两种类型，第一种是不限制每种类型车辆的数目（Fleet Size and Mix Vehicle Routing Problem，FSMVRP），第二种是限制每种类型车辆的数目（Heterogeneous Fixed Fleet Vehicle Routing Problem，HFFVRP）。
今天主要讲解FSMVRP问题，该问题需要确定两方面内容：
1）确定为每条路线服务的车型。
2）确定每条路线访问顾客的顺序。
▎FSMVRP问题数学模型

$\begin{aligned} \operatorname{Min} \sum_{k=1}^{T} f_{k} \sum_{j=1}^{n} x_{0 j}^{k}+\sum_{k=1}^{T} \sum_{i=0}^{n} \sum_{j=0}^{n} c_{i j} x_{i j}^{k}\quad(1) \\ s.t. \sum_{k=1}^{T} \sum_{i=0}^{n} x_{i j}^{k}=1 \quad j=1, \ldots, n\quad(2) \\ \sum_{i=0}^{n} x_{i j}^{k}-\sum_{l=0}^{n} x_{j l}^{k}=0 \quad j=0, \ldots, n ; k=1, \ldots, T \quad(3) \\ \sum_{i=0}^{n} y_{i j}-\sum_{l=0}^{n} y_{j l}=d_{j} \quad j=1, \ldots, n \quad(4) \\ y_{0 j} \leqslant \sum_{k=1}^{T} Q_{k} x_{0 j}^{k} \quad j=1, \ldots, n \quad(5) \\ y_{i j} \leqslant M \sum_{k=1}^{T} x_{i j}^{k} \quad i \neq j=0, \ldots, n \quad(6) \\ y_{i j} \geqslant 0 \quad i \neq j=0, \ldots, n \quad(7) \\ x_{i j}^{k} \in\{0,1\} \quad i \neq j=0, \ldots, n ; k=1, \ldots, T \quad(8) \end{aligned}$
其中，0表示配送中心，1,...,n表示顾客，T表示车型数目，Qk表示车型k的最大装载量(Q1<Q2<...<QT)，fk表示车型k的固定使用成本(f1<f2<...<fT)，dj表示顾客j的需求量，cij表示车辆从顶点i行驶到顶点j的成本（cij=cji）。
此外，决策变量如下：

$x_{i j}^{k}= \begin{cases}1 & \text { 如果k车型从顶点i行驶到顶点j} \\ 0 & \text { 否则 }\end{cases} \\ y_{i j}=\text {从顶点i到顶点j的货物流量，即车辆离开顶点i前往顶点j时的货物装载量}$
公式（1）车辆使用成本和车辆行驶成本之和。公式（2）和（3）保证车辆到达一个顾客后会离开该顾客。公式（4）表示货物量的移动，确保每个顾客的需求都能被满足。公式（5）确保车辆离开配送中心时的装载量不能超过其最大装载量。公式（6）表示如果没有车辆从顶点i行驶到顶点j，那么从顶点i到顶点j没有货物流动。

▎FSMVRP问题初始解构造方法

FSMVRP和容量受限的车辆路径问题（CVRP）的差别在于FSMVRP还需确定为每条路线服务的车型。
我们在节约（CW）算法构造容量受限的车辆路径问题（CVRP）初始解MATLAB代码这篇推文中提到过CVRP初始解的构造方法，CW法的本质是依据合并两条路径带来的节约值反复合并路线最终构造出初始解。CW构造CVRP的节约值很容易理解就是路径长度的节约值。
虽然不能够直接将构造CVRP的CW法直接应用于FSMVRP问题，但是我们可以通过对节约值的改造，让改造后的CW法也能应用于FSMVRP问题。
通过前文对FSMVRP问题要确认的内容可以看出，改造后的节约值也至少应该包含两部分：1）车辆使用成本的节约值，2）车辆行驶距离的节约值。其中车辆行驶距离的节约值就是路径长度的节约值。
接下来在介绍车辆使用成本的节约值之前先引入3个概念：
F(z)-能够服务总需求量为z的路线的最小车型的使用成本
P(z)-能够服务总需求量为z的路线的最小车型的最大装载量
F&#39;(z)-不能够服务总需求量为z的路线的最大车型的使用成本
为了能够更好的理解F(z)、P(z)和F&#39;(z)，我们用下面的例子进行阐述。
假设有3个车型，每个车型的最大装载量为(Q1,Q2,Q3)=(30,50,100)，每个车型的固定成本为(f1,f2,f3)=(20,40,90)，则关于F(z)、P(z)和F&#39;(z)的分段函数如下：

$F(z)=\left\{\begin{array}{rr} 20, & 0<z \leqslant 30 \\ 40, & 30 < z\leqslant50 \\ 90, & 50 < z\leqslant100 \\ \infty, & 100 \leqslant z . \end{array}\right.$

$P(z)=\left\{\begin{array}{lc} 30, & 0<z \leqslant 30 \\ 50, & 30<z \leqslant 50 \\ 100, & 50<z \leqslant 100 \\ \infty, & 100<z \end{array}\right.$

$F^{\prime}(z)=\left\{\begin{array}{rr} 0, & z<30 \\ 20, & 30 \leqslant z<50 \\ 40, & 50 \leqslant z<100 \\ 90, & 100 \leqslant z . \end{array}\right.$
在理解完上述三个概念后，我们进而介绍路径节约值、固定成本节约值和机会节约值。首先假设现在有两条路径R1和R2，路径R1最后一个访问的顾客为i，路径R2只访问顾客j，总需求量分别为zi和zj，则上述3个节约值的定义分别如下：
（1）路径节约值

$s_{i j}^{r}=c_{i 0}+c_{0 j}-c_{i j}$
（2）固定成本节约值

$s_{i j}^{f}=F\left(z_{i}\right)+F\left(z_{j}\right)-F\left(z_{i}+z_{j}\right)$
（3）机会节约值

$s_{i j}^{o}=\delta(w) \cdot F^{\prime}\left(P\left(z_{i}+z_{j}\right)-z_{i}-z_{j}\right) \\ \text { 其中 } w=P\left(z_{i}+z_{j}\right)-P\left(\max \left\{z_{i}, z_{j}\right\}\right) \\ \delta(w)= \begin{cases}0 & \text { if } w=0 \\ 1 & \text { if } w>0\end{cases} \\$
综上所述合并R1和R2的总节约值由3部分组成：

$s_{i j}=s_{i j}^{s}+s_{i j}^{f}+s_{i j}^{o}$
依据改造后的节约值，并保留CW法构造CVRP初始解的模式，反复合并路径，直至合并任意两条路径时的sij都为负值时，FSMVRP的初始解即构造完毕。
在这里再补充一点，机会节约值的作用。机会节约值目的是鼓励使用能够带来收益的更大的车型。当需要使用更大的车型来服务两条路径合并后的路径时，使用更大车型带来的剩余装载量为后续合并小需求路径提供可能，进而降低车辆使用成本。因此可以被“挤进”剩余装载量的最大车型的固定成本即为机会成本 $s_{i j}^{o}$ 。

▎参考文献

[1]Gheysens F, Golden B, Assad A. A comparison of techniques for solving the fleet size and mix vehicle routing problem[J]. Operations-Research-Spektrum, 1984, 6(4): 207-216.
[2]Golden B, Assad A, Levy L, et al. The fleet size and mix vehicle routing problem[J]. Computers & Operations Research, 1984, 11(1): 49-66.
咱们下期再见
▎近期你可能错过了的好文章：
新书上架 | 《MATLAB智能优化算法：从写代码到算法思想》
优化算法 | 灰狼优化算法（文末有福利）
优化算法 | 鲸鱼优化算法
遗传算法（GA）求解带时间窗的车辆路径（VRPTW）问题MATLAB代码
粒子群优化算法（PSO）求解带时间窗的车辆路径问题（VRPTW）MATLAB代码

		自动登录	找回密码
密码			立即注册