改进鲸鱼优化算法解决存在紧急需求的VRPSPD

Improving Whale Optimization Algorithm for VRPSPD with Urgent Orders

摘要: 针对在配送途中客户出现紧急需求的同时送取货车辆路径问题(Vehicle Routing Problem with Simultaneous Pickup-Delivery, VRPSPD)，以油耗和等待成本最小、客户满意度最优为目标，建立紧急需求下的同时送取货车辆路径优化模型，提出一种改进鲸鱼优化算法进行求解，合理规划配送路线。为了增强鲸鱼优化算法跳出局部最优的能力，分别在收缩包围行为、气泡捕食行为中引入顺序交叉(OX)机制与基于位置的交叉(PBX)机制，并增加个体在搜索觅食行为中的随机性。仿真实验表明，改进后的算法能够得到符合约束条件且更经济的路线，证明其在问题求解中的有效性与优越性。

Abstract: Aiming at the problem of simultaneous delivery and pickup vehicle paths when customers have urgent demands during the delivery route, with the optimization objective of minimizing the fuel cost, waiting cost, and maximizing customer satisfaction, we establish a simultaneous delivery and pickup vehicle path optimization model under urgent demands and propose an improved whale optimization algorithm for solving the problem to reasonably plan the delivery routes. To enhance the ability of the whale algorithm to jump out of the local optimum, the OX and the PBX are introduced in the contraction encircling and the bubble foraging and increase the randomness of individuals in the prey searching. Simulation experiments show that the improved algorithm can obtain a more economical route that meets the constraints, proving its effectiveness and superiority in problem-solving.

1. 引言

车辆路径规划问题(Vehicle Routing Problem, VRP)作为解决组合优化问题的技术[1]，其目标是找到一组最优路径，使得配送车辆在满足客户需求和车辆容量限制的情况下，总行驶距离或时间的最小化[2]。1989年，Min [3]首次提出将取货需求融入配送，比单独配送或取货更能减少车辆数量、提高客户满意度和装载率、最大化利用物流资源，后续VRPSPD逐渐成为学术研究的热点，诸多学者对其进行扩展。Lagos等[4]提出了一种改进的粒子群优化算法，通过引入多种社会学习策略和动态惯性权重调整，增强算法的探索和开发能力，并添加修复操作，以确保解的可行性和优化质量。李珺等[5]针对单配送中心提出一种基于模拟退火和自适应大规模邻域搜索的混合算法，范厚明等[6]则研究了多配送中心VRPSPD，各配送中心共享资源和车辆，协同完成送取货工作。Olgun等[7]建立以油耗成本最小化为目标的绿色VRPSPD模型，通过敏感性分析验证邻域结构、超启发式和局部搜索的性能，表明绿色目标函数对燃料费用有显著影响。

互联网的快速发展推动了物流行业的改革，物流企业越来越注重通过客户信息挖掘识别客户群体，为不同客户群提供定制物流服务，以提升服务质量和品牌知名度。传统的VRP中客户是同质的，但是在一些特殊的配送环境中，客户对货物有不同的需求紧急度。当前相关研究主要在应急物流领域中，Silva等[8]在应急医疗中心选址中引入病人优先级，结合最大化覆盖选址模型和优先级排队理论，优化了不同紧急程度病人的择医问题。Chen等[9]以医疗急救物资调度中考虑需求紧迫性的车辆路径优化问题为研究对象，基于紧迫性分析设计了改进的布谷鸟–蚁群混合算法求解模型，结果显示考虑需求紧迫性的路径优化方案成本较高，所需时间增加，但提高了医疗急救物资调度的效率和合理性。

VRPSPD属于NP-hard问题，其解决方法主要分为传统优化算法和元启发式算法。传统的优化方法，如动态规划、分支定界法和整数线性规划等，虽然可以求解小规模VRP，但在面对大规模实例时，往往难以在合理的时间内找到最优解。为应对车辆路径规划问题的复杂性和紧迫性，元启发式算法提供了一种有效的解决途径。鲸鱼优化算法(Whale Optimization Algorithm, WOA)作为一种群智能优化算法，在2016年被Mirjalili等[10]提出，具有原理简单易实现、参数量少易设置和全局与局部开发分别控制易平衡等特点[11]。Gharehchopogh等[12]罗列了WOA变体、改进策略与混合算法等研究的主要思想与应用，李广强等[13]针对自主水下机器人三维全局路径规划问题，设计多学习集构造个体引领者及联合引导策略，以进一步增强鲸鱼优化算法的整体性能。蔡雨岑等[14]针对地面无人车辆路径规划问题的特点，提出基于和声二次优化的平衡鲸鱼算法求解最优路径。周鲜成等[15]采用贪婪算法构造初始解，设计局部优化算子改进鲸鱼优化算法，用于求解电动车辆路径模型。

综上所述，尽管学者们已对相关问题进行了广泛研究，但依然存在以下缺口：1) 大多关于紧急需求的车辆路径规划集中在医疗药品行业，但在生活常见的业务往来中，企业遇到部分客户因库存或交易量的变化而迫切需要货物迅速配送的情况也时有发生，如制造商的原材料库存由于雨雪天气受损，急需进行补充；餐厅接待非预定的大批顾客，紧急联系供应商要求食材迅速送达等。此时，企业出于长期合作的考虑，往往愿意牺牲部分时间或路径成本进行紧急需求的配送，从而使客户更加满意。2) 现有文献采用WOA解决VRPSPD的研究比较有限，因此，在基本的VRPSPD上加入紧急需求情况并采用改进的WOA进行求解是本文的创新之处。

2. 问题描述及模型

2.1. 基本问题描述

基本的VRPSPD可以描述为：某配送中心中拥有若干个同类型车辆，在一定时间内对周围多个客户进行产品的配送和回收，每个配送车辆在配送中心装载好货物后出发，可以为多个客户点提供服务，并在满足路径上所有客户的需求后装载着回收物品最终返回配送中心，示意图如图1。

Figure 1. Schematic of VRPSPD

图1. VRPSPD示意图

2.2. 本文问题描述

本文在上述基本情况下，另有客户出现紧急需求，则货车收到请求后最先去往有紧急需求的客户点，在符合客户服务时间窗约束和车辆最大承载能力要求的前提下，以成本最小和客户满意度最优为目标，合理规划配送路线。为更好地建立模型，现作出如下假设：

1) 客户点的位置信息、取/送货的需求量、接受服务的时间窗是已知的；

2) 车辆保持固定的平均速度行驶；

3) 正、逆向需求不允许拆分执行，每个客户只能由一辆车进行服务；

4) 先对有紧急需求的客户进行配送，且新增需求量也是已知的；

5) 车辆在配送途中可以返回补货不超过一次。

2.3. 符号定义

集合：

N——节点集合，${\rm N}=\left\{0,1,2,\cdots ,n\right\}$ ，其中0为配送中心，n为客户总数；

U——紧急客户集合，$U=\left\{1,2,3,\cdots ,u\right\}$ ，u为出现紧急需求的客户数，$U\subset {\rm N}$ ；

M——可用车辆集合，${\rm M}=\left\{1,2,3,\cdots ,m\right\}$ ，m为可用车辆数。

参数：

$i,j$ ——节点，$i\ne j$ ；

u——出现紧急需求的节点；

k——配送车辆；

$c_{ij}$ ——车辆从节点i到节点j的燃油成本；

$\rho$ ——油耗率；

$t_{ij}$ ——车辆从节点i到节点j的行驶时间；

$s_{ij}$ ——节点i到节点j的距离；

Q——车辆最大承载量；

$q_{{}_i}$ ——车辆到达节点i时的载重；

$q_{ij}$ ——车辆从节点i驶向节点j时的载重；

$d_i$ ——节点i处的需求量；

$r_i$ ——节点i处的回收量；

${d^{\prime }}_u$ ——节点u的新增需求量；

$T_i$ ——车辆到达节点i的时间；

$w_i$ ——车辆在节点i处的等待时间；

$e_i$ ——节点i处开始接受服务的时间；

$l_i$ ——节点i处停止接受服务的时间；

$l_{ti}$ ——节点i处最佳时间窗的结束时间；

$h_i$ ——完成节点i处所有服务所需的时间；

$f_i$ ——节点i处客户的满意度。

变量：

$x_{ijk}$ ——车辆k是否从节点i行驶到节点j (1-是，0-否)；

$y_{ik}$ ——车辆k是否从节点i返回配送中心补货(1-是，0-否)。

2.4. 目标函数

在本文的研究中，对路径规划方案的评价标准分为三个角度，分别为油耗成本、等待成本和满意度评价，具体的函数如下：

1) 油耗成本

$Z_1={\displaystyle \sum c_{ij}}\cdot x_{ijk}$ (1)

$c_{ij}=\rho \left(q_{ij}\right)\cdot s_{ij}$ (2)

$\rho \left(q_{ij}\right)={\rho }_0+\frac{{\rho }^{*}-{\rho }_0}{Q}\cdot q_{ij}$ (3)

其中，${\rho }_0$ 表示车辆空载时的油耗率，${\rho }^{*}$ 表示满载时的油耗率。

2) 等待成本

$Z_2={\displaystyle \sum _i{w}_i}$ (4)

$w_i=\{\begin{array}{ll}{e}_i-T_i\hfill & T_i<e_i\hfill \\ 0\hfill & T_i\ge e_i\hfill \end{array}$ (5)

3) 客户满意度

在对满意度量化分析时，将满意度转为0~1数值，考虑在现实生活中客户对服务时间窗的要求并非完全刚性，并随实际服务时间与预期之间偏差的增大而降低，在临近时间窗结束时接受服务易为不满，设置满意度评价函数如图2所示。

Figure 2. Graph of the relationship between service time and customer satisfaction

图2. 时间窗与客户满意度关系

满意度评价公式可以归结为：

$Z_3={\displaystyle \sum _i{f}_i}$ (6)

$f_i=\{\begin{array}{ll}1\hfill & e_i\le T_i<l_{ti}\hfill \\ \frac{l_i-T_i}{l_i-l_{ti}}\hfill & l_{ti}\le T_i<l_i\hfill \\ 0\hfill & 其他\hfill \end{array}$ (7)

另外，在考虑客户紧急需求时$f_u=1$ ，即只要对紧急需求客户进行优先配送，该客户的满意度则为最高值。

4) 目标函数

综上所述，本文的目标函数可以归结为：

$\min Z=Z_1+Z_2-Z_3$ (8)

其中，最后一项取负，目的是将满意度最优转化为与成本部分相一致的最小化问题。

2.5. 约束模型

1) 客户点约束

${\displaystyle {\sum }_{k=1}^{{\rm M}}{\displaystyle {\sum }_{j=0}^{{\rm N}}{x}_{ijk}}}=1\begin{array}{cc}& \forall i=1,2,\cdots ,n\end{array}$ (9)

$x_{0uk}=1\begin{array}{cc}& \forall k\in {\rm M}\end{array}$ (10)

公式(9)表示客户点只能被服务一次；公式(10)表示紧急需求客户需要首先被配送。

2) 车辆承载约束

$q_i<Q\begin{array}{cc}& \forall i=1,2,\cdots ,n\end{array},\forall k\in {\rm M}$ (11)

$q_{ij}=q_i-d_j+r_i-{d^{\prime }}_u\begin{array}{cc}& \forall i,j\in {\rm N},\forall k\in {\rm M}\end{array}$ (12)

$q_{ij}<d_j\to y_{ik}=1\begin{array}{ccc}& & \forall i,j=1,\cdots ,n,\forall k\in {\rm M}\end{array}$ (13)

公式(11)表示在任意时刻车辆的载货量不能超过车辆的最大承载量；公式(12)表示在路径上相邻的两个节点之间的载重关系；公式(13)表示如果车辆k当前剩余货物量不满足下一客户点j的需求量，则返回配送中心补货。

3) 返回补货约束

${\displaystyle {\sum }_{i=1}^{{\rm N}}{y}_{ik}}\le 1\begin{array}{cc}& \forall k\in {\rm M}\end{array}$ (14)

$x_{ojk}\ge y_{ik}\begin{array}{cc}& \forall i,j=1,2,\cdots ,n,\forall k\in {\rm M}\end{array}$ (15)

公式(14)表示每个配送车辆最多只能返回配送中心补货一次；公式(15)表示车辆k补货后重新出发。

4) 路径约束

${\displaystyle {\sum }_{j=1}^{{\rm N}}{x}_{0jk}}=1\begin{array}{cc}& \forall k\in {\rm M}\end{array}$ (16)

${\displaystyle {\sum }_{i=1}^{{\rm N}}{x}_{i0k}}=1\begin{array}{cc}& \forall k\in {\rm M}\end{array}$ (17)

公式(16)、(17)表示配送车辆必须从配送中心出发，最终也必须返回配送中心。

5) 时间约束

$T_i\le l_i\begin{array}{cc}& \forall i=1,2,\cdots ,n\end{array}$ (18)

$e_i\le T_i+w_i\le l_i\begin{array}{cc}& \forall i=1,2,\cdots ,n\end{array}$ (19)

$e_i\le T_i+w_i+h_i\le l_i\begin{array}{cc}& \forall i=1,2,\cdots ,n\end{array}$ (20)

$T_j=T_i+w_i+h_i+t_{ij}\begin{array}{cc}& \forall i,j\in {\rm N}\end{array}$ (21)

$\begin{array}{ccc}{T}_j=T_i+t_{i0}+t_{0j}& & \forall i,j=1,2,\cdots ,n\end{array}$ (22)

公式(18)表示车辆到达时间不能晚于最晚服务时间；公式(19)表示开始服务时间要处于客户点的允许服务时间窗内；公式(20)表示结束服务时间要处于客户点的允许服务时间窗内；公式(21)表示在路径上相邻的两个节点之间的车辆到达时间关系；公式(22)表示返回补货情况下的时间关系。

3. 算法设计

WOA的核心思路是模拟座头鲸独有的气泡网捕食行为，实现对搜索空间的有效探索与开发，猎物的位置表示最优解。本文在上述研究情形下，对算法进行以下改进。

3.1. 改进初始解生成方式

在标准鲸鱼算法中，通常通过随机生成的浮点数编码来表示客户访问顺序，生成初始解。在本研究中由于中心仓库和顾客节点均为离散点，因此改用非负整数编码方式，中心仓库编号为0，顾客点为$1,2,\cdots ,n$ 。例如，客户数量为10，随机生成的客户顺序表示为$\left[9,5,2,7,6,1,3,10,4,8\right]$ ，其中出现紧急需求客户$\left[2,5,7\right]$ 。将解按原顺序分为两部分，分别是urgent $\left[5,2,7\right]$ 和not_urgent $\left[9,6,1,3,10,4,8\right]$ ，为减少由于不合理的初始解而增加的后期修正成本，初始解生成方式具体如下：1) 有紧急需求客户未被服务时，按urgent中的客户顺序判断车辆剩余负载和时间窗是否满足其要求，如果满足，将紧急需求客户放入路径的第一个点，并在urgent中删除该点，直至urgent为空；2) 按not_urgent中的客户顺序判断车辆剩余负载和时间窗是否满足要求，如果满足，将该客户点放入路径节点中，并在not_urgent中删除该点，以此类推；3) 在得到所有车辆的路径后，考虑紧急需求的增量，对服务紧急需求客户的车辆进行负载容量判断，如果在考虑新增需求的情况下车辆剩余负载不足，则在不满足的位置将路径一分为二，车辆于分离点返回仓库，补货至满足需求重新开始服务。

以上，通过优先处理紧急需求和合理安排非紧急需求，生成的初始解更符合实际约束条件，高质量的初始解能够帮助减少迭代次数，提高算法的求解质量和收敛速度。

3.2. 改进收敛性行为

在鲸鱼算法中，鲸鱼个体的气泡捕食行为和包围收缩行为都是以群体中的最优解作为参考来更新位置并趋向于最优解，虽然可以快速减少大范围的搜索区域，但是依赖群体最优解会导致局部最优。为了增强鲸鱼算法跳出局部最优的能力，引入交叉机制来生成新解，并与鲸鱼算法得到的新解作对比，保留相对优秀的解作为此个体在本次迭代中的最新解。

1) 收缩包围行为下的交叉机制优化

随着迭代次数增加，参数$\left|A\right|>1$ 的时候会选择收缩包围行为，此时处于算法运行后期。为了不降低算法的收敛速度，同时又兼具一定的随机性，选择OX交叉机制来实现对收缩包围行为的优化。首先，以鲸鱼优化算法中气泡捕食行为的位置更新公式生成新解S₁，再以种群中的最优解和S₁为父代，取最优解的一段连续片段，用S₁补全剩余元素，生成子代随机新解S₂。分别求取并对比S₁与S₂的评价值，选择更好的结果作为此个体在本次迭代中的新解，具体公式如下：

$SN=round\left(\left(1-abs\left(\frac{A}{2}\right)\right)/2\cdot S\right)$ (23)

$OS=round\left(\frac{C}{2}\cdot \left(S-SN\right)\right)$ (24)

其中，SN决定了从群体最优个体中复制的连续基因段长度，OS决定了交叉段在群体最优个体中的起始点，式中参数A、C即为包围收缩中位置更新的参数。

2) 改进气泡捕食行为下的交叉机制

在气泡捕食行为中，虽然个体以群体最优解为参考更新位置，但是以螺旋形式进行，目的是在靠近群体最优解的过程中增加对未知区域的探索。此时为进一步提升所得新解的随机性，加入随机性更高的PBX交叉机制来实现对气泡捕食行为的优化，执行过程与上文相似，但在生成子代随机新解S₂时不再取连续片段，而是随机取最优鲸鱼个体$X^{*}$ 中$\lambda$ 个位置的元素，具体公式如下：

$\lambda =abs\left(round\left(D^{\prime }\cdot \cos \left(2\Pi l\right)\right)\right)$ (25)

其中，$D^{\prime }$ 表示两个父代解中位置相同且数值相同的元素个数。

3.3. 改进后的算法工作流程

改进的鲸鱼算法(Improved Whale Optimization Algorithm, IWOA)工作流程如图3所示。

Figure 3. Flowchart of the IWOA

图3. IWOA流程图

4. 案例验证

选取Wang等[16]设计的带时间窗的VRPSPD测试集Cdp101为验证算例，该算例中包含100个客户节点，车辆的最大承载量为200。随机选出有新增需求的紧急客户并设定新增需求量：紧急客户点5，7，13，27，40，46，57，71，84，98；新增需求分别为55，88，60，30，62，123，59，73，77，56。在CPU为3.2 GHz，运行内存16 GB，64位Windows11操作系统的情况下应用Python3.10分别运行WOA与IWOA求解，算法最大迭代次数为200，同取程序运行10次的最优解，对比分析所得路径方案。

4.1. IWOA的有效性

IWOA成功输出配送结果，最优解的车辆路径如图4，考虑增量前后的路径拆分情况如图5。

Figure 4. Vehicle paths of IWOA

图4. IWOA车辆路径结果图

(a) 考虑增量前的路径 (b) 考虑增量后的路径

Figure 5. The path change after the increase

图5. 考虑增量后的路径变化

经过分析，该方案有效性体现在：1) 完整度，所有客户需求均被满足。2) 满足模型中的车辆容量及客户时间窗限制，具有实际应用价值。3) 贴合问题设定，即紧急需求点均在路径首位，并且有部分路径由于新增的紧急需求而进行拆分，图示较难观察，现给出具体配送方案见表1，其中异色标注的为紧急需求点，同一行代表二者在紧急需求新增前为同路径。

Table 1. Distribution programs of IWOA

表1. IWOA的具体配送方案

路径编号	配送方案
1	0-98-28-22-52-49-0
2	0-71-70-77-1-0
3	0-57-54-37-48-89-91-0
4	0-46-88-68-0
5	0-84-39-51-0
6	0-25-74-93-59-80-0
7	0-81-78-92-60-64-2-0
8	0-67-18-15-12-4-0
9	0-20-17-62-30-100-0
10	0-41-83-45-0
11	0-95-94-72-6-0
12	0-87-76-82-85-0
13	0-24-35-61-26-0
14	0-42-86-16-14-0
15	0-32-33-31-56-97-0
16	0-96-44-58-0
17	0-3-8-10-0
18	0-65-0
19	0-90-55-0
20~21	0-5-66-0，0-47-0
22~23	0-27-9-23-0，0-69-75-0
24~25	0-13-63-53-38-36-0，0-34-21-0
26~27	0-7-0，0-19-11-99-0
28~29	0-40-29-0，0-73-79-50-0

4.2. IWOA的优越性

4.2.1. 目标函数评价值对比

Table 2. Comparison of function values

表2. 各评价值对比

算法	油耗成本	等待成本	客户满意度	总评价值
WOA	525.74	33.17	96.87	462.04
IWOA	401.94	30.96	97.12	335.78

由表2的对比分析可知，无论总评价值还是各项成本IWOA结果都比WOA更加理想。经过计算，以追求总评价值最小化为目标，IWOA结果较WOA降低了27.3%，尤其体现在油耗成本方面，降低23.5%，等待成本则降低6.7%。同时，由于均满足客户紧急需求，所以方案的满意度评价较高，IWOA略优于WOA。以上对比说明IWOA能够有效地降低企业同时送取货成本，保持较高满意度，体现了该算法所得方案的优越性。

根据方案结果进一步推断，对于企业而言，迅速响应并有效满足客户的紧急需求，对于提升顾客对于配送服务的满意度有重要意义。这种快速响应机制能够促使客户对相关服务产生高度的认可与信赖，进而增强其对企业的忠诚度，有助于双方建立稳固合作关系。这种关系的建立是企业长远发展的坚实基础，并为企业在竞争激烈的市场环境中赢得更多的竞争优势。

4.2.2. 收敛效果对比

从图6的算法迭代对比可以看出，WOA因为自身局限性，过早陷入局部最优，在第7代就实现收敛，优化效果不再提升，最终目标函数值约为462；IWOA因为使用改进的初始解生成方式，初始解的成本评价值便比WOA低；同时，因为引入OX交叉机制和PBX交叉机制，算法的探索性和随机性增加，跳出局部最优的能力提升，IWOA的评价值持续下降，并且在整个迭代过程中呈现出更加平滑和逐步优化的趋势，经历数个平台期，最终在第124代收敛到更低的目标函数值约为336，可知其在更广泛的搜索空间内找到了更优的解，体现了改进后算法的优越性。

Figure 6. Comparison of algorithm iteration

图6. 算法迭代对比图

5. 结论与启示

本文在含紧急需求的VRPSPD下，以获得更优配送路径为目标构建数学模型；以模型的具体设置为依据改进鲸鱼算法初始解的生成策略，并引入交叉机制提高算法跳出局部最优的能力；最后通过对比WOA与IWOA在案例求解中的表现，得到改进后的算法使得总评价值较改进前降低27.3%，且在成本降低的同时保持97.12的高满意度，证明了IWOA的有效性和优越性。

企业可以通过优化物流网络和采用先进的配送管理系统得到更加经济的配送方案，但除了考虑时间与资金成本外，与客户相辅相成、保持紧密互信的合作关系也同样重要。在客户出现紧急需求时进行优先处理，能够帮助企业在成本控制的目标下提高客户的满意度，实现长远发展与竞争优势。

基金项目

上海“科技创新行动计划”社会发展科技攻关项目(22dz1203400, 22dz1203405)。