基于多目标模拟退火的带容量限制车辆路径问题∗

毕志升蔡茗芊

基于多目标模拟退火的带容量限制车辆路径问题∗

毕志升蔡茗芊

（广州医科大学基础学院广州511436）

车辆路径问题是运筹学中著名的NP问题。带容量限制的车辆路径问题作为最基本的车辆路径问题，其研究对其它类型的车辆路径问题具有重要的借鉴作用。论文首先从物流企业和客户两个不同的角度考察4个优化目标，将带容量限制的车辆路径问题推广到高维多目标领域。然后运用基于Pareto支配接受准则的多目标模拟退火算法在单数组和多数组两种不同的编码方式下进行求解，并通过实验分析对比两种编码方式的优劣。在9个Augerat数据集上的实验结果表明，单数组编码方式在IGD和HV指标下不如多数组编码方式。单数组编码方式得到的Pareto解集具有更好的多样性，而多数组编码方式得到的Pareto解集具有更好的收敛性。

车辆路径问题；容量限制；高维多目标优化

Class NumberTP391

1引言

车辆路径问题（Vehicle Routing Problem，VRP）是Dantzig和Ramser［1］于1959年提出的运筹学领域中著名的NP问题。它通过设计合理的车辆路线，期望以最小的运输成本，为不同的客户配送不同的货物。时至今日，VRP的研究成果已经被广泛应用于现实生活，为物流配送、巴士路线规划等［2］现实问题的求解提供理论依据，具有重要的现实意义。

带容量限制的车辆路径问题（Capacitated Ve⁃hicle Routing Problem，CVRP）是最基本的车辆路径问题。它仅仅考虑车辆具有载货量限制。由于这个约束被带时间窗车辆路径问题、多车场车辆路径问题等衍生VRP广泛采用，使得CVRP成为其它类型VRP的基础。因而，CVRP的研究成果对其它类型的VRP具有重要的借鉴意义。

近年来，VRP受到越来越多国内外学者的关注。当前对VRP的研究主要基于单目标优化［3］。然而，VRP本质上是一个目标数大于3的高维多目标优化问题。例如，物流企业为了减少成本和提高利用率，追求车辆少、运输路线短、工作量均衡；而客户期望更快收到货物，要求等待时间短。这些目标之间是存在矛盾的。减少车辆虽然能有效减少由硬件维护和人力资源带来的成本，却增加了每辆车需要服务的客户数量，导致客户需要等待更长的时间。因而，物流企业需要在诸多目标上进行取舍。不同的取舍能产生不同的解决方案，产生一组对应不同取舍的均衡解是物流企业根据自身情况选择实施方案的前提。基于多目标优化能在不固定取舍的前提下同时产生一组均衡解，因此，基于多目标优化求解CVRP是符合企业需要、具有现实意义的。

本文通过考察4个优化目标将CVRP推广到高维多目标领域。然后采用两种不同的编码方式对问题进行建模，并运用基于Pareto支配接受准则的多目标模拟退火算法（Multiobjective Simulated An⁃nealing Using Pareto-Domination Based Acceptance Criterion，PDMOSA）［4］进行求解。最后通过实验对两种不同的编码方式进行对比分析。

2带容量限制的车辆路径问题

一般地，CVRP可以定义为［2］：有1个拥有K辆车的车场，每辆车容量为Q。有N个客户需要货物配送。客户i的货物容量为gi且gi＜Q。客户可以由任意车辆服务，但只能被服务一次。在不超出容量限制的情况下，每辆车离开车场可以为多个客户提供服务。服务结束后车辆返回车场。

记节点0为车场节点；节点{1，2，…，N}为客户节点；k为车场的第k辆车；从节点i到节点j的距离为dij；R为一组满足约束的路径集合，对应问题的一个解。R中每一条路径都是一条以车场为起点、以车场为终点的环路，由一辆车提供服务。令

则CVRP可形式化描述为

其中，i∈{1，2，…，N}，k∈{1，2，…，K}，F是目标函数，通常选择路径长度或在其基础上结合车辆数等其他因素构造目标函数［5］；式（4）是容量限制；式（5）是保证每个客户都被服务且仅被服务一次。

近五十年，CVRP一直是一个研究热点［2，5］。然而，CVRP的求解还远远没有达到令人满意的程度［2］。由于CVRP是VRP中最基础的问题，而VRP在现实生活中的应用也越发广泛，其研究还将长期持续。

3基于高维多目标优化的带容量限制车辆路径问题

CVRP本质上是一个高维多目标优化问题，从多目标优化的角度考察CVRP是合理而且必要的。本节从PDMOSA、目标函数设定、编码等方面描述基于多目标优化的CVRP及其求解。

3.1基于Pareto支配接受准则的多目标模拟退火算法

本文选择PDMOSA求解CVRP。PDMOSA是一种单点搜索算法。相比基于种群的搜索算法，单点搜索算法立足于邻域搜索，在求解VRP问题上具有优势［6］。

PDMOSA是Suman［4］在2004年提出的多目标模拟退火算法。不同于其它利用目标函数值计算接受概率的模拟退火算法，该算法提出了基于Pa⁃reto支配的适应度用于计算接受概率。Pareto支配的适应度等于支配当前解的非劣解个数加1。显然，适应度越大解越差。PDMOSA算法如算法1所示。

关于多目标优化算法的详细描述可参见文献［7］，这里不再详述。

3.2目标函数

本文分别从物流企业和客户的角度设定4个优化目标：1）从物流企业的角度考虑，考察路径总长度、车辆数、最大容量差。其中最大容量差为各车辆实际容量的最大值与最小值之差。2）从客户的角度考虑，考察客户的等待时间。客户等待时间定义为沿着路径从车场到客户之间的路径长度。例如路径0-6-2-0，第一个客户节点6的等待时间是节点0到节点6之间的距离，第二个客户节点2的等待时间是节点0到节点6再到节点2的总距离，如此类推。记R中路径数量为|R|，每一条路径上的客户等待时间为wr。则，R中客户等待时间为

故，该CVRP可形式化描述为

其中，i∈{1，2，…，N}，k∈{1，2，…，K}，wr是R中第r条路径的等待时间；式（6）是最小化总路径长度；式（7）是最小化车辆数；式（8）是最小化最大容量差；式（9）是最小化客户等待时间。问题约束如第2节所述。

3.3染色体编码

染色体编码是求解CVRP的过程中对解的一种表示方式，每一个编码代表一个解。通常采用数组和节点的编号进行编码。常用的编码方式有两种：单数组编码和多数组编码。

1）单数组编码

采用长度为N的整型数组对染色体进行编码，N为客户的数量。数组以客户的编号作为数组的元素，每个编号出现且仅出现一次。以一个有15个客户的CVRP的解为例，如图1。采用单一数组编码可以表示为chrom=｛13，2，15，5，14，4，8，3，10，9，6，7，12，11，1｝。由于仅仅采用1个数组，而解由多个路径组成，因此编码时需要将各个路径拼接起来。这种编码的优点在于编码长度是一个仅与客户数量有关的定值，为算法的搜索提供了便利。然而，这种编码并未记录路径的划分情况，因而需要额外的路径划分技术，将染色体重新划分为路径。

图1 CVRP的一个解

2）多数组编码

多数组编码与单数组编码的区别在于，对每一条路径，多数组编码采用一个数组单独表示。数组的数量等于路径的数量，数组的长度等于该路径服务的客户的数量。例如，图2所示的解将被4个数组表示，分别是｛13，2，15，5，14｝、｛4，8｝、｛3，10，9，6｝和｛7，12，11，1｝（此处不记录车场）。相比单数组编码，该方法能有效区分各个不同的路径，无须额外的路径分割技术。然而，不同的解可能拥有不同的数组数量和长度，导致解集中同时存在多种不同的结构，算法的搜索也因此不如单数组便利。

3.4邻域搜索策略

不同的编码方式采用不同的邻域搜索策略。

1）单数组编码的邻域搜索

在染色体中随机选择一个客户，并插入到另一个随机选择的位置中。

邻域搜索之后要将染色体重新划分成路径。本文采用Plot算法［8］对染色体进行解码，见算法2所示。

在解码前，首先在染色体前插入一个0节点。在Plot中，采用以下策略构造路径：尝试构造一条从客户chrom［i］开始的路径。如果不违反容量限制，则尝试将下一个客户节点纳入当前路径，直到违反约束或没有剩余客户节点（Line 13）。若违反容量约束，则尝试构造从客户chrom［i］开始的路径。到客户chrom［i-1］为止的路径长度由v［i-1］保存（Line 7）。在构造过程中，cost对应的是以客户chrom［i］为第一个客户、以客户chrom［j］为最后一个客户的路径长度，是当前正在构造的路径（Line 6）。Line 8中if为真，则将当前客户chrom［j］添加到当前路径，即构造了一条以chrom［i］为第一个客户节点、以chrom［j］为最后一个客户节点的路径。该方案较原方案（对应v［j］）的总路径更短，或路径等长但能使前一条路径服务更多的客户，即车辆容量的利用更充分。如果if为假，意味着原方案更优，并在下一次循环中（Line 4～Line 13）尝试构造以chrom［i］为第一个客户节点、以chrom［j+1］为最后一个客户节点的路径。路径的第一个客户节点信息由数组pred保存。若pred［j］=x，说明客户chrom［j］所在的路径是以客户chrom［x+1］开始。当路径划分完毕，最后一个客户所在的路径以chrom［pred［N］+1］为第一个客户。而以chrom［pred［N］］为最后一个客户的路径以chrom［pred［pred［N］］+1］为第一个客户。如此向前构造路径，直到chrom的第一个客户节点。例如chrom=｛0，2，5，4， 1，3｝，pred=｛0，0，0，0，1，2｝。从后向前读取数组pred，pred［5］=2，即当前最后一个客户chrom［5］所在的路径是以chrom［2+1］为第一个客户，即得到路径0-4-1-3-0，0为车场。继续读取pred。当前最后一个客户节点是chrom［2］。pred［2］=0，即客户chrom［2］所在的路径是以chrom［0+1］为第一个客户的，得到路径0-2-5-0。至此，解码结束。

显然，这种邻域搜索算法虽然仅仅改变了一个客户节点的位置，但由于解码算法的作用，插入的客户节点不仅仅改变当前路径的货物总容量和长度，还有可能由于部分客户节点被顺延到下一条路径，使得后续路径也发生变化。因而，邻域搜索的力度较大。另一方面，解码算法追求路径最短的同时追求车辆容量的最大化，因此有利于最小化路径总长度和车辆数，但不利于最小化最大容量差。

2）多数组编码的邻域搜索

在多数组编码中，每个数组代表一条路径。随机选择一条路径中的一个客户，插入到随机选择的另一条路径的一个随机位置。

这种邻域搜索不能保证被插入客户的路径依然满足容量约束。若约束无法满足，采用以下策略进行修补：对该路径中的每一个客户节点，若删除该节点后车辆容量满足约束，则计算删除该节点带来的路径长度变化，按变化从大到小排序，得到序列ListN。对其余路径，计算剩余容量，按剩余容量从大到小进行排序，得到序列ListR。选择ListN中第1个客户节点，尝试添加到ListR的第1条路径中。如果客户节点的货物超过路径的剩余容量，不允许插入，尝试下一条路径；若所有路径均插入失败，选择ListN中第2个客户节点，继续上述尝试，直到允许插入。若允许插入，计算所有可能的插入点，选择插入后路径最短的插入位置。若所有节点对于所有路径均不允许插入，新建一条路径，该路径仅有ListN中的第1个客户节点。

在无须修补的情况下，该邻域搜索仅仅改变两条路径，其余路径不受影响。即使需要修补，受影响的路径也仅有3条。因而，相比单数组编码，邻域搜索的力度较小。另一方面，除了修补时新建路径，路径的数量不会增加。而短路径有可能在邻域搜索的随机选择中被选中移出客户节点，最终越来越短并消失。故该算法有利于最小化车辆数，车辆数的变化也相对稳定。但是，这也导致车辆数的多样性不足。此外，这种邻域搜索方法对路径长度的考量仅仅局限于超重路径和超重后被插入节点的路径，因而在优化路径长度上缺乏全局性。

4仿真实验

本节运用PDMOSA［4］求解CVRP。针对单数组编码方式，构造算法实例CVRP-S；针对多数组编码方式，构造算法实例CVRP-M。

4.1测试平台

本文以MOEAFramework（http：//moeaframe⁃work.org/index.html）为实验平台，它是一个用于开发和测试多目标优化算法的开源平台，提供了丰富的测试接口。

本实验的实验环境是MOEA Framework 2.11；JDK 8；CPU 2.3GHz；16GB RAM。

4.2数据集及参数设置

本实验的数据集来自University of Malaga的Networking and Emerging Optimization研究组（http：//neo.lu.uma.es/vrp/vrp-instances）。该研究组持续研究各种VRP，并提供了一系列CVRP数据集。实验在9个Augerat数据集进行，数据集的基本参数如表1所示。

表1 测试集的基本参数

参照文献［4］的建议值，实验中PDMOSA的初温为3000，降温系数为0.98，内循环次数为50次，外循环次数为3000次。

4.3性能指标

本文选择了2个常用的性能指标对算法的运算结果进行比较：

1）逆世代距离（Inverted Generational Dis⁃ tance，IGD）［9］：IGD是一种通过计算算法求得的Pa⁃reto前沿与真实Pareto前沿的之间的距离评价算法优劣的方法。该指标同时度量Pareto最优解集的收敛性和多样性。指标值越小越好。

2）超体积（Hypervolume，HV）［10］：HV是一种通过计算Pareto最优解集在空间中与参考点围成的空间大小度量算法优劣的方法。该指标同时度量Pareto最优解集的收敛性和多样性。指标值越大越好。

对算法的各性能指标值进行显著性检验，显著性水平为0.05。

4.4实验结果

实验中，每个算法在每个数据集上独立运行30次，运行结果如表2和图2所示。加粗底纹表示算法在该指标下显著优于其它对比算法。

从表2可知，CVRP-S除了在A-n32-k5和A-n55-k9上IGD指标下较优，B-n31-k5上IGD指标下没有显著差异，其余情况均不如CVRP-M。这意味着，从总体而言，CVRP-S不如CVRP-M。由于IGD和HV同时度量收敛性和多样性，表2无法对收敛性和多样性作更深入的分析。本文通过每个目标函数值的盒图，从另一个角度分析算法的结果。通过图3中A-n55-k9实验结果在各目标函数上的盒图可以发现，CVRP-S的Pareto解集在各个目标上的四分位数极差均大于CVRP-M。特别地，CVRP-M在车辆数（f2）上几乎所有Pareto解均得到同样的函数值。虽然两个算法在各目标函数取得极值的数量差不多，但CVRP-S在其极值附近的分布明显比CVRP-M密集。其它数据集的盒图也反映出类似的结果。这意味着，在Pareto解集的多样性上CVRP-S优于CVRP-M。CVRP-S在IGD和HV指标上不如CVRP-M更多的是因为其Pareto解集的收敛性弱。

表2 各算法在9个数据集上运行30次IGD和HV比较

图2 A-n32-k5上各目标函数值的盒图

5结语

本文通过考察4个与物流企业和客户密切相关的目标函数，将CVRP推广到的高维多目标领域，并运用PDMOSA进行求解。在求解过程中，采用了单数组和多数组两种不同的编码方式，并给出了相应的邻域搜索策略。实验分析表明，在IGD和HV指标上，采用单数组编码的CVRP-S不如采用多数组编码的CVRP-M。CVRP-S能获得多样性更好的Pareto解集，而CVRP-M能获得收敛性更好的Pareto解集。

本文采用的邻域搜索策略对目标函数具有较明显的偏向。例如多数组编码下，车辆数的多样性很差。这在实际应用中将影响物流企业对最终实施方案的选择。后续的研究需要提出更为有效的局部搜索策略，在提高Pareto解集收敛性的同时，减少搜索策略的偏向，以期获得多样性更好的Pa⁃reto解集。

［1］G Dantzig，J Ramser.The Truck Dispatching Problem［J］. ManagementScience，1959，6（8）：80-91.

［2］S Akpinar.Hybrid Large Neighbourhood Search Algorithm for Capacitated Vehicle Routing Problem［J］.Expert Sys⁃tems with Applications，2016，61：28-38.

［3］T Sooktip，N Wattanapongsakorn.Identifying Preferred Solutions for Multi-Objective Optimization：Application to Capacitated Vehicle Routing Problem［J］.Cluster Com⁃puting，2015，18（4）：1435-1448.

［4］B Suman.Study of Simulated Annealing Based Algorithms for Multiobjective Optimization of a Constrained Problem［J］.Computers&Chemical Engineering，2004，28（9）：1849-1871.

［5］K Braekers，K Ramaekers，IVan Nieuwenhuyse.The Ve⁃hicle Routing Problem：State of The Art Classification and Review［J］.Computers&Industrial Engineering，2016，99：300-313.

［6］J Wang，Y Zhou，Y Wang，J Zhang，C L P Chen，Z Zheng.Multiobjective Vehicle Routing Problems with Si⁃multaneous Delivery and Pickup and Time Windows：For⁃mulation，Instances，and Algorithms［J］.IEEE Transac⁃tions on Cybernetics，2016，46（3）：582-594.

［7］公茂果，焦李成，杨咚咚，等.进化多目标优化算法研究［J］.软件学报，2009，20（2）：271-289.

GONG Maoguo，JIAO Licheng，YANG Dongdong，et al. Research on Evolutionary Multi-Objective Optimization Algorithms［J］.Journal of Software，2009，20（2）：271-289.

［8］邓欣.基于遗传算法的多车场车辆路径问题研究［D］.重庆：重庆大学，2007.

GENG Xin.Research on Multiple Depot Vehicle Routing Problem Based on Genetic Algorithm［D］.Chongqing：Chongqing University，2007.

［9］Q Zhang，H Li.MOEA/D：A Multiobjective Evolutionary Algorithm Based on Decomposition［J］.IEEE Transac⁃tions on Evolutionary Computation，2007，11（6）：712-731.

［10］E Zitzler，M Laumanns，L Thiele.SPEA2：Improving the Strength Pareto Evolutionary Algorithm［C］//Evolution⁃ary Methods for Design，Optimization and Control with Applications to Industrial Problems（EUROGEN 2001）. K Giannakoglou，D T Tsahalis，J Periaux，K D Papail⁃iou，T Fogarty，Eds.，Athens，Greece：International Center for Numerical Methods in Engineering，2002，95-100.

Capacitated Vehicle Routing Problem Based on Multi-Objective Simulated Annealing

BI Zhisheng CAI Mingqian
（Schoolof Basic Science，Guangzhou MedicalUniversity，Guangzhou 511436）

Vehicle routing problem is a well-known NP problem in operations research.As the mostbasic vehicle routing prob⁃lem，the research of capacitated vehicle routing problem has important reference for other types of vehicle routing problems.In this paper，four optimization functions are firstly inspected from the view oflogistics enterprise and customer，which extends the capaci⁃tated vehicle routing problem to many-objective field.Then，the multiobjective simulated annealing using Pareto-domination based acceptance criterion is used to solve this problem under single-array encoding and multi-array encoding.The advantages and disad⁃vantages ofthese two methods are analyzed with experiment.The experiments on nine Augeratdatasets show thatthe single-array en⁃coding method is better than the multi-array encoding method with the measure of IGD and HV.The Pareto setobtained by the sin⁃gle-array encoding method has better diversity and worse convergence than thatobtained by the multi-array encoding method.

vehicle routing problem，capacitated，many-objective optimization

TP391

10.3969/j.issn.1672-9722.2017.08.012

2017年3月17日，

2017年4月21日

国家自然科学基金（编号：61603106）；广州市市属高校科研项目（编号：1201630320）；广州医科大学科学科研项目（编号：L135042）资助。

毕志升，男，博士，讲师，研究方向：计算智能和数据挖掘。蔡茗芊，女，研究方向：数据挖掘。