求解需求可拆分车辆路径问题的改进的金字塔演化策略

李华峰，黄樟灿，张 蔷，湛 航，谈 庆

（武汉理工大学理学院，武汉 430073）

0 引言

车辆路径问题（Vehicle Routing Problem，VRP）最早于1959 年由Dantzig 等［1］提出。该问题可描述为：在一个物流系统中，存在若干个配送中心、若干个客户和若干辆运输车，假设客户的需求量不超过车辆的最大载重量，要求设计合理的车辆行驶路线，在不违背车辆容量限制、不超出车辆最远运输距离等约束条件下，完成所有客户的配送任务。但在实际配送过程中，客户的需求量大于车辆载重量的情况会经常发生，为了解决该问题，Dror 等［2］提出了需求可拆分的车辆路径问题（Split Delivery VRP，SDVRP）。

SDVRP 自提出以来就受到广泛的关注，很多学者也对该问题进行了深入的研究。由于SDVRP 是NP（Nondeterministic Polynomial）-hard 问题［3-4］，精确算法［5-6］求解比较困难，所以主要采用聚类算法［7-8］和启发式算法［9-12］相结合的两阶段思想对该问题进行求解。刘旺盛等［7］分别采用了先分组后路径和先路径后分组两种思想求解了该问题，从不同角度论述了两种思想的优越性；刘旺盛等［8］结合了K-means聚类与模拟退火算法的优点，实验结果表明，算法效果优于其他算法；闵嘉宁等［13］在传统K-means 聚类中加入了“推出”“拉入”操作，平衡了各类的需求量，优化了算法的性能；向婷等［14］通过设置拆分阈值对客户进行聚类，然后采用蚁群算法优化各类的线路，从而提高了求解精度；姜婷［15］分析了SDVRP 解的特点，先求解旅行商问题，然后对其进行切割拆分成单个路径，最后通过删除和最小代价插入操作采用人工蜂群算法求解该问题。

以上两阶段求解算法主要采用K-means 聚类算法，先对客户进行分组，然后运用智能优化算法优化路径。但是K-means聚类算法的分类结果过度依赖于分类中心的初始化，缺乏探索优良个体的潜能，容易陷入局部最优；同时传统的智能优化算法，如粒子群算法［16］、遗传算法［17］、禁忌搜索算法［18］未能将优化过程中种群间的竞争与协作统一起来，容易陷入局部最优，求解精度较低。而金字塔演化策略（Pyramid Evolution Strategy，PES）［19］是一种新型启发式算法，以金字塔结构为基础，有着明确的分工与晋升机制，其模型按种群个体优劣进行排序分层，对各层赋予不同的职责，将种群间和群内个体间的竞争与协作有机地融合在一起，克服了传统启发式算法容易陷入局部最优、未考虑种群间竞争与协作的缺点。因此，本文基于PES，提出了改进的金字塔演化策略（Improved PES，IPES）。首先，分析了SDVRP 解的基本特性，对其编码、解码方式进行了重新定义，保证除最后一辆车不确定满载，其余车辆均满载；其次，结合遗传算法随机、“适者生存”的高度并行、自适应等特点，提出了一种自适应算子来引导个体向最优解靠拢，从而将个体间的竞争与协作联系起来，使算法能够收敛到最优解；最后，通过设计层间协作策略，加强种群间的协作，将种群间的竞争与协作联系起来，使得算法能够跳出局部最优，提高求解精度。

1 SDVRP的数学模型

本文研究的SDVRP 描述如下：一个配送中心有若干辆规格都相同的配送车辆，分别给n个客户进行货物需求配送，其中配送中心的编号为0，客户的编号分别为1至n，且配送中心和每个客户的位置坐标(xi，yi)、货物需求量wi等信息都已知。通过安排合理的配送方案，使得在满足以下几个条件时完成配送任务的路程最短、配送车辆最少。

1）各辆配送车辆的最大载重量为W，车辆不允许超载；

2）每辆车可以服务多个客户，每个客户也可以由多辆车进行服务；

3）任意两个客户点之间的距离对称，即dij=dji，且任意三个客户点之间的距离满足dik+dkj≥dij；

4）所有服务车辆必须从配送中心出发，服务当前客户后即刻前往下一个客户或者直接返回配送中心。

本文的优化目标是配送路径最短、配送车辆最少，假定n个客户点与配送中心0 构成集合C={0，1，…，n}，R为完成所有n个客户所需要的最小车辆数，建立SDVRP 的数学模型如下：

式（1）代表车辆总的配送路径最短；式（2）代表配送过程中车辆数最少；式（3）表示流量守恒，即服务某客户的车辆数与离开该客户的车辆数相等；式（4）和式（5）确保每个客户至少被访问一次，且该客户的需求均得到满足；式（6）表示每条线路中被服务客户之间的弧边数等于被服务客户点的个数减1；式（7）为每条线路客户总的需求量不超过车辆运载能力限制；式（8）表示当且仅当车辆路过客户i时，该客户才能得到服务；式（9）表示“满载”，即所有配送车辆中，至多存在一辆车的载重量小于车辆最大载重量；式（10）表示各线路中每一个客户需求量不超过该客户的最大需求量；式（11）为决策变量，当且仅当=1时，表示在当前线路r中，车辆为客户i和j服务。

2 IPES求解SDVRP

2.1 PES

PES 是一种基于金字塔结构的智能启发式算法［19］。PES起初应用于连续函数优化问题，后来有学者将其用于求解整数规划问题［20-21］和彩色图像颜色量化问题［22］，并通过实验验证了该算法在求解这些问题时，能够跳出局部最优，具有全局寻优能力。该算法所采用的金字塔结构主要包含四层（见图1），自下至上分别为：探索层、传递层2、传递层1、开采层，层层递进，层级间和层级内个体相互竞争与协作，引导个体向最优值靠近。PES的演化机理主要包含以下几点：

1）金字塔结构有清晰的分层机制，层级根据种群中所有个体的适应度值按区间参数DIVIDE进行分层，自下而上每一层级的个体数量、适应度值、邻域搜索范围都逐渐减小，此操作明确了每一层级的职责，从而提高了算法的寻优效率。

2）金字塔结构有严格的分工机制，每一层各司其职，层层递进。探索层主要负责在全局范围内进行搜索，充分探测优良个体的潜在邻域，然后将优良个体按照一定的比例传递至上一层；传递层（传递层1和传递层2）作为探索层与开采层的纽带，兼任探索与开采两方面的任务，在接收下层传递上来的个体后，一方面继续探索个体潜在的优良区域，另一方面充分挖掘当前个体的优良潜能，最后通过一定比例将优良个体传递至开采层；开采层主要负责充分挖掘当前个体的优良潜能，使之逐步靠近最优解。

3）金字塔结构存在明确的晋升机制，通过设置传递参数TF将下层部分优秀个体传递至上层培养，继续探索个体的优秀潜能，从而使算法能够跳出局部最优，求得全局最优解。

图1 金字塔结构模型Fig.1 Pyramid structure model

2.2 IPES及设计

标准的PES 最初用于求解连续函数的优化问题，其层间协作策略可以有效地使算法跳出局部最优，具有一定的全局寻优能力。而遗传算法［23］作为一种高效、实用、鲁棒性强的优化技术，发展极为迅速，并且被验证能够有效地求解NP 问题以及多目标优化问题。遗传算法的重点在于思考了生物在繁殖过程中可能发生基因交叉和变异，引起生物性状的连续微弱改变，为外界环境的定向选择提供了物质条件和基础，使生物进化成为可能，但是遗传算法在求解此类问题时容易陷入局部最优［17］。因此，本文结合了PES和遗传算法性能优势，首先根据SDVRP 解的基本特性，重新定义了其解码方式，使得除最后一辆车外，其余车辆全部满载，提高了车辆满载率；其次，根据PES 每一层级分工机制的不同，结合遗传算法高效、实用等特性，对每层采取不同的邻域算子来引导个体向最优解收敛，将个体的竞争与协作统一起来，充分发挥各层级探索与开采的潜能；最后，通过层间协作策略，将下层部分优良个体传递至上层继续进行培养，将种群间的竞争与协作联系起来，从而提高算法的全局寻优能力。

2.2.1 IPES初始种群

本文主要采用整数编码的方式生成初始种群个体，其中0代表配送中心，i(i=1，2，…，n)表示需配送的客户。初始种群的生成过程具体如下：

步骤1 利用客户直接全排列的方式来表示种群个体，Xi=(x1，x2，…，xn)(xi∈{1，2，…，n})表示初始种群中个体i的编码。

步骤2 按式（12）随机生成Xi(i=1，2，…，NP)，作为IPES的初始种群。

其中，randperm(n)表示1～n所有整数的随机排列。

2.2.2 IPES计算适应度值及分层

对种群中的个体进行解码，计算各个体的适应度值，具体解码方式如下：

步骤1 定义变量Weigh，且Weigh=0代表配送车辆从配送中心出发，初始载重量为0。

步骤2 判断路径中是否存在客户k∈{1，2，…，n}的需求量wk满足式（13），若满足，则单独安排一辆车为客户k服务，并将该客户的剩余需求量按式（14）进行更新，直至所有的客户k(k=1，2，…，n)的需求量wk都满足式（15）；

步骤3 依次将Xi中客户点添加到车辆的访问用户中直至碰到可拆分的客户点i，转下一步。

步骤4 若客户i的需求量大于车辆的剩余需求量，则根据车辆的剩余需求量将该客户的需求量分为由当前车辆服务由另外一辆车服务，与此同时判断后续客户j是否满足式（16），若满足，则优先服务j客户：

步骤5 根据步骤4 得到的个体配送线路求解完成此次配送的车辆总路径，得到相应的适应度值Objvi(i=1，2，…，NP)。

步骤6 将适应度值按式（17）进行排序，并根据分层比例DIVIDE将种群进行分层。

以上解码方式，既保证了个体线路中所使用的车辆均为最小车辆数R，又保证了除最后一辆不绝对满载以外，其余车辆均满载，将多级优化目标转化为单优化目标，适应度值objv最小，即为完成配送任务路径的路径最短、车辆数最少。

2.2.3 IPES自适应邻域算子

考虑到金字塔结构有着明确的分工机制，自下而上层级的开采能力逐渐增强，探索能力逐渐减弱，因此，对不同层级的个体进行更新时，结合遗传算法的交叉、变异算子，分别采取了不同的策略，以便最大化地发挥各个层级的开采与探索的能力。此外，针对层内个体交叉算子的交叉点个数设置了一个自适应策略，如式（18），从而加快算法的收敛。每一层级个体的邻域搜索策略具体如下：

其中：pc表示交叉点的个数；g表示当前的迭代次数；G表示最大迭代次数。

不同层级的个体进行更新所采取的不同策略如下：

1）探索层的邻域算子包括交叉算子和变异算子，该层探索能力最强，为了避免算法陷入局部最优，最大化地探索寻找优良个体的潜在邻域，将相邻个体进行交叉，其中交叉的起始点位置L_Start由式（19）确定，终点位置L_End由式（20）确定。

二者完成交叉操作后，对新个体进行变异扰动，常见的变异算子有两点（或多点）换位算子、插入算子和逆转算子。本文主要采用逆转算子进行变异，具体如图2所示。假设有5个客户待服务，个体的服务顺序为4-1-2-5-3，随机选取两个点P1 和P2，对这两个点中间的片段进行倒序排列，从而产生一个新个体，服务顺序为5-2-1-4-3。

图2 逆转算子Fig.2 Reversal operator

2）相比探索层，传递层（传递层1和传递层2）的探索能力较弱，开采能力较强，该层交叉算子为采用当代最优个体p_best与全局最优个体g_best分别引导传递层1、传递层2的个体趋于最优解，如图3所示。该层的变异算子同上。

3）开采层的探索能力最弱，开采能力最强，需充分挖掘个体的潜能。对于表现优良的个体，直接保留；对于病态个体，对其进行孵化，引导其向好的方向发展。采用的邻域算子包括变异算子和孵化算子，变异算子同上，重点介绍孵化算子。孵化算子的孵化对象是病态个体，具体步骤如下：

步骤1 从当前个体Xi中按式（21）的方式随机选择一个孵化点位置：

步骤2 将当前个体Xi按式（22）进行处理，更新Xi和待服务客户集Q：

步骤3 依次从待服务客户集Q中选择离Xi中所有已安排个体最近的个体进行插入，直至所有个体都被服务，即待服务客户集Q为空。

图3 交叉算子Fig.3 Crossover operator

2.2.4 IPES层间协作策略

各层级内部个体遵从“适者生存”的原则，优良个体被保留下来；而在层级之间，部分优良个体通过层与层之间的协作策略晋升至更高层，在新的一层中与同层个体按照邻域算子进行培养，以获得上升到更高层的机会，充分开发个体的潜能，从而将各层种群密切地联系起来，加快算法的收敛。本文的层间协作策略采用根据适应度值大小的方式按设定的参数TF晋升。

2.3 IPES步骤

IPES步骤如下：

步骤1 算法初始化，设置迭代次数g=1，最大迭代次数G，分层比例DIVIDE。

步骤2 根据本文的编码方式随机生成包含NP个体Xi(i=1，2，…，NP)，作为初始种群。

步骤3 对个体Xi(i=1，2，…，NP)进行解码，计算其适应度值objvi(i=1，2，…，NP)。

步骤4 对个体适应度值进行排序，按初始参数DIVIDE进行分层。

步骤5 按照2.2.3 节提出的自适应邻域算子对个体进行更新，将优良个体保留，淘汰病态个体。

步骤6 根据参数TF将下层优良个体传递至上一层进行培养。

步骤7 判断算法终止条件是否满足，若满足，结束迭代过程，输出最优个体及最优值；否则返回步骤3，继续进行下一次迭代。

3 仿真实验与结果分析

为了验证IPES 在求解SDVRP 上的有效性，利用Matlab R2018b软件进行了仿真实验，实验环境为Windows 10操作系统，Inter Core i5-8250U 处理器，4 GB 内存。实验初始化参数设置为：初始种群NP=400，分层比例DIVIDE=(0.5，0.25，0.15，0.1)，传递比例TF=(0.6，0.4，0.2)，其他参数与所对比算法的参数相同。实验中通过四个实验分别对文献［7］的两个案例、文献［16］的一个案例和文献［14］的一个案例进行了仿真。

3.1 实验1及结果分析

实验1采用文献［7］的案例进行仿真，将本文的IPES与文献［7］的分段求解算法、文献［8］的聚类算法、文献［14］的聚类算法、文献［15］的人工蜂群算法、文献［16］的粒子群算法的结果进行了比较，具体见表1。算例可描述为：存在一个配送中心，需要为15 个客户点进行配送服务，车辆的最大载重量为500，其中客户编号0 为配送中心。算法设置最大迭代次数G=100，随机运行10次，其迭代曲线如图4所示。

表1 实验1计算结果比较Tab.1 Calculation result comparison of experiment 1

图4 实验1迭代曲线Fig.4 Iteration curve of experiment 1

由表1可知，从最优路径看，IPES效果明显优于其他文献的算法，相较于文献［7］算法、文献［8］算法，最优路径缩短了3.32%；相较于文献［14］算法，最优路径缩短了0.92%；相较于文献［15］算法，最优路径缩短了2.95%；相较于文献［16］算法，最优路径缩短了0.95%。从使用车辆数看，各算法均可求得最优车辆数。从平均运行时间看，IPES 略优于文献［7］算法、文献［8］算法，略差于文献［14］算法、文献［15］算法，但由图4可知，算法的最佳迭代次数为39，可见该算法仍具有一定的优越性。综上可知，IPES在求解SDVRP时有较强的全局寻优能力，求解精度较高。车辆的最优路径见表2，完成客户的总配送任务最少需要10 辆车，除了最后一辆车未满载，其余车辆均满载。该方案中涉及到的拆分点为1、5、7、9、12、13、14、15。

为了更加直观地反映该实验结果，图5给出了实验1的最优路径，图中圆点上面的数字表示客户的序号，每条折线代表一辆车的行驶路径。例如：0-3-11-10-14 表示车辆从配送中0出发，依次服务客户3、11、10、14，最后返回配送中心。

3.2 实验2及结果分析

该实验采用文献［7］的案例进行仿真，将本文的IPES与文献［7］的分段求解算法、文献［8］的聚类算法、文献［14］的聚类算法、文献［16］的粒子群算法、文献［18］的禁忌搜索算法的结果进行了比较，具体见表3。案例可描述为：存在一个配送中心，需要为20 个客户点进行配送服务，车辆的最大载重量为5，其中客户编号0 为配送中心。算法设置最大迭代次数G=100，随机运行10次，其迭代曲线如图6所示。

表2 实验1最优路径及满载率Tab.2 Optimal path and full load ratio of experiment 1

图5 实验1最优路径Fig.5 Optimal path of experiment 1

表3 实验2计算结果比较Tab.3 Calculation result comparison of experiment 2

由表3可知，从最优路径长度看，IPES优于其他文献的算法，相较于文献［7］算法，最优路径缩短了5.01%；相较于文献［8］算法，最优路径缩短了4.48%；相较于文献［14］算法，最优路径缩短了1.22%；相较于文献［16］算法，最优路径缩短了0.35%；相较于文献［18］算法，最优路径缩短了8.53%。从使用车辆数来看，各算法车辆数均能达到最优。由图6 可知，IPES 的最佳迭代步数为73，而文献［7］算法的最佳迭代步数为537。综合可知，IPES 相较于其他算法，具有一定的有效性和很强的收敛能力。车辆的最优路径见表4，客户的总需求量为40，8辆车的总载重也为40，刚好满载。该方案中涉及到的拆分点为1、18。

图7为实验2的最优路径，图中圆点上面的序号表示客户的序号，每条折线代表一辆车的行驶路径。例如：0-15-16-19表示车辆从配送中0出发，依次服务客户15、16、19，最后返回配送中心。

图6 实验2迭代曲线Fig.6 Iteration curve of experiment 2

表4 实验2最优路径及满载率Tab.4 Optimal path and full load ratio of experiment 2

图7 实验2最优路径Fig.7 Optimal path of experiment 2

3.3 实验3及结果分析

实验采用文献［16］的案例进行仿真，将本文的IPES 与文献［16］的粒子群算法的结果进行了比较。案例可描述为：存在一个配送中心，需要为35 个客户点进行配送服务，车辆的最大载重量为8。算法设置最大迭代次数G=800，随机运行10次，结果如表5所示。

表5 实验3计算结果比较Tab.5 Calculation result comparison of experiment 3

由表5可知，IPES结果明显优于文献［16］的粒子群算法，相较于粒子群算法，IPES 的平均路径减少了3.04%，最优路径减少了3.07%。由平均车辆数为7 可知，算法每次迭代都可以收敛到最优车辆，具有一定的稳定性。因此，IPES 在求解SDVRP 时，有一定的有效性、收敛性和稳定性，且求解精度相较于粒子群算法较高。IPES 的最优路径见表6，完成客户的总配送任务最少需要7 辆车，除了最后一辆车未满载，其余车辆均满载。该方案中涉及到的拆分点为1、5、10、18、33。

表6 实验3最优路径及满载率Tab.6 Optimal path and full load ratio of experiment 3

图8为实验3的最优路径，图中圆点上面的序号表示客户的序号，每条折线代表一辆车的行驶路径。例如：0-18-28 表示车辆从配送中0 出发，依次服务客户18、28，最后返回配送中心。

图8 实验3最优路径Fig.8 Optimal path of experiment 3

3.4 实验4及结果分析

该实验采用文献［14］的案例进行仿真，将IPES 与文献［14］算法、文献［24］算法的结果进行了比较。案例可描述为：存在一个配送中心，需要为36 个客户点进行配送服务，车辆的最大载重量为1。算法设置最大迭代次数G=800，随机运行10次，计算结果具体见表7。

表7 实验4计算结果Tab.7 Calculation results of experiment 4

由实验结果可见，随机运行10 次，IPES 的平均路径长度为308.78，最优路径为305.10，最差路径为312.25。文献［14］算法的最优路径为336.74，文献［24］算法的最优路径为354.70，可知，本文算法的最差路径优于文献［14］算法、文献［24］算法的最优路径。且相较于文献［14］的聚类算法，IPES的最优路径缩短了9.40%；相较于文献［24］的禁忌搜索算法，IPES 的最优路径缩短了13.98%。此外，每次所需要的车辆数都为16，均达到最优，由此可知，IPES 解决该问题时具有一定的收敛性、稳定性和很强的全局寻优能力。IPES 的最优路径见表8，完成客户的总配送任务最少需要16辆车，除最后一辆车未满载，其余车辆均满载。该方案中涉及到的拆分点为2、3、5、7、10、17、18、21、22、25、32、33、35。

图9为实验4的最优路径，图中圆点上面的序号表示客户的序号，每条折线代表一辆车的行驶路径。例如：0-20-29-17-3 表示车辆从配送中0 出发，依次服务客户20、29、17、3，最后返回配送中心。

图9 实验4最优路径Fig.9 Optimal path of experiment 4

4 结语

本文提出了一种改进的金字塔演化策略（IPES），以配送路径最短、配送车辆最少为优化目标，建立了数学模型，介绍了IPES 求解SDVRP 的编码方式、适应度值计算过程、每一层级的自适应邻域算子以及层间传递策略，极大提高了车辆满载率，克服了传统两阶段的求解算法容易陷入局部最优，以及传统优化算法在求解时只有个体间竞争与协作无种群间竞争与协作的缺陷。通过仿真实验表明，IPES 在求解四个案例时，相较于其他对比算法的最优精度分别至少提升了0.92%、0.35%、3.07%、9.40%，验证了IPES 求解SDVRP 的可行性和有效性，为研究车辆路径等组合优化问题提供了一种新的启发式方法。在接下来的工作中，将对算法的邻域更新策略、层间协作策略继续进行改进，探索算法在求解大规模SDVRP 上的可行性、收敛性、稳定性，使PES 能够完全应用于离散问题的求解，拓展算法的应用领域。