带装载能力的需求依背包拆分车辆路径问题

发布时间：2020-04-11所属分类：农业论文浏览：1次

摘 要： 摘要:以最小化总的旅行时间为优化目标，以单车

　　摘要:以最小化总的旅行时间为优化目标，以单车场、单车型、装载能力和需求依背包拆分等为约束条件，将以往客户需求不可拆分的条件松弛为依背包来离散拆分,建立了带装载能力的需求依背包拆分VRP(CVRPSDB)的单目标数学模型。设计了一个自适应禁忌搜索算法(ATSA)对模型进行求解。该算法采用了自适应惩罚机制，构建了一个多邻域结构体，并针对客户点与背包都设计了相应的邻域操作算子，较好地适应了客户需求量的离散拆分程度。经算例测试与文献对比，验证了所设计模型与算法的有效性。

　　关键词:车辆路径问题;拆分;依背包拆分;禁忌搜索算法;物流

　　车辆路径问题(vehicleroutingproblem,VRP)自Dantzig[1]于1959年提出后，便引起了运筹学界和管理科学界的广泛关注。相比于传统手工排班计划，采用现代优化算法[2]来优化行车路线，可降低车辆的行驶成本，有助于减少相应的碳排放量，降低对环境造成的影响。

　　根据客户需求是否允许拆分配送，VRP可分为需求可拆分VRP[3](vehicleroutingproblemwithsplitdeliveries,VRPSD)和需求不可拆分VRP[1]。结合拆分方式是否是离散化的，VRPSD又可以分为需求离散拆分VRP[2](VRPwithdiscretesplitdeliveries,VRPDSD)与需求连续拆分的经典VRPSD[4]，而在实践离散拆分配送的VRPDSD中也有多种拆分方式，如依背包拆分、依货物特性拆分等。本文将重点针对带装载能力的需求依背包拆分VRP(capacitatedVRPwithsplitdeliveriesbybackpack,CVRPSDB)进行研究，并设计相应的禁忌搜索算法(tabusearchalgorithm,TSA)进行求解。

　　相关期刊推荐：《工业工程》(双月刊)创刊于1998年，是由广东工业大学主办，中国机械工程学会协办的期刊，国内外公开发行。本刊理论与应用结合，内容涵盖经营战略、决策研究、制造系统、物流系统、设施规划、工作研究、成本分析、工程经济、质量保障、诊断评价、信息管理、人机工程、生产组织、人力资源、组织重构等。读者对象主要是从事工业工程理论与应用研究的科技人员、各级政府工业和经济管理部门的决策人员、各类企业管理人员，高校师生及其他有关人员。

　　目前，在车辆路径问题研究中，多约定客户需求只能由一辆车一次完成，属于需求不可拆分VRP。Dror等[3]于1989年首次提出了VRPSD的一种最基本类型，即纯送货的需求可拆分VRP(vehicleroutingproblemwithsplitdeliveries,VRPSD)，并给出了VRPSD的定义，指出对客户需求进行合理地拆分配送有利于降低配送成本，其随后于1994年证明了VRPSD属于NP-hard问题[4]，并给出了VRPSD的子回路消去约束。这些研究吸引了一批学者进入可拆分VRP领域，如Archetti等[5-6]在Dror的基础上，进一步简化降低了VRPSD的研究难度，通过将车辆装载能力和客户需求予以整数单元化，假设客户需求可按照计量单位来任意连续拆分，车辆装载能力不小于客户需求，构建了经典VRPSD的整数规划模型(K-VRPSD模型)。

　　VRPSD拆分装配具有理论上的成本节约性，不过在有些情况下，任意连续拆分VRPSD方式也会给物资装配带来实践操作上的困难[7-8]，如将同一种物资拆分进入不同的车辆线路，这必然会给装货和收货带来不必要的麻烦。在物流配货中，客户的需求常可视为由一定项数的物资离散组合而成，当每项物资的特性差异很大时，配送企业可将每项物资视为一个独立的“背包”打包用于装配，同一个“背包”内的物资一般不适合再进行拆分组装。如在电商物流配送、连锁超市配送、快递收发中由于各客户的需求物品种类、体积大小、质量规则等都不同，其需求若拆分则适合按照“背包”来离散进行，不能按照物资重量来连续拆分。因此，研究需求依背包拆分VRP(VRPwithsplitdeliveriesbybackpack,VRPSDB)具有较强的实践价值。另外，在VRPSD相关文献中，除Gulczynski等[2]、Xiong等[9]、Wang等[10]、Salani等[7]、Xia等[8]的研究涉及离散拆分思想外，其余多数沿用Archetti等[5-6]构造K-VRPSD模型时采用的需求连续拆分思想。可见，对需求依背包来离散拆分的VRP进行研究具有较强的理论价值。

　　需求可拆分VRP(VRPSD)属于NP-hard问题。借用Archetti等[5-6]的需求连续拆分K-VRPSD模型，谢毅[11]、刘旺盛[12]都对经典VRPSD的求解算法进行了研究。VRPSD求解难度比传统VRP更大，而精确算法如分支定界法[4]、割平面法[13]、动态规划法[14]、聚类−路径两阶段法[15]、列生成及切面法[16]、分支−切平面法[17]等都只能有效求解中小规模问题，因此设计能够解决大规模问题的智能启发式算法(智能算法)是求解的关键。已有文献在求解VRPSD及其衍生类型时主要结合了禁忌搜索算法[10-11,18-20]、遗传算法[21]、蚁群算法[22]、蜂群算法[23]等智能优化算法。禁忌搜索算法[24-25](tabusearchalgorithm,TSA)具有简单性、适应性、易操作性等优点，是一种求解需求可拆分VRP较为高效的智能优化算法。因此，本文也采用禁忌搜索算法来进行求解。

　　在以往的需求可拆分VRP文献[5]中，对带装载能力的VRPSD(capacitatedVRP,CVRP)研究较多。因此，本文也对带装载能力的需求依背包拆分VRP(capacitatedVRPwithsplitdeliveriesbybackpack,CVRPSDB)进行研究。由于本文的CVRPDSD是依“背包”来对客户点的需求量进行离散拆分操作，因此，CVRPSDB既是需求可拆分VRP(VRPSD)中存在的一种按“背包”离散拆分情形，也是以往传统VRP的一种拓展。本文将以物流配送中单车场、单车型的纯送货为背景来对CVRPSDB进行建模，并设计一个自适应TSA(adaptiveTSA,ATSA)求解。

　　1问题描述与建模

　　本文的CVRPSDB可描述为：确定一系列同车型的车辆在客户点之间的行驶顺序，使其从车场出发，有序地对各客户点进行送货服务，最后返回原出发点，并在满足车辆装载能力的条件下最小化总的旅行时间。而且，各客户点的需求量可拆分由多辆车来共同完成，但若拆分则只能按照“背包”来离散进行，其中“背包”在本文的含义为不可进一步拆分的客户需求的最小集合。结合一般CVRP，本文的CVRPSDB有如下假设。

　　1)车场：车场为单车场，位置已知，且车辆数充足。

　　2)车辆：车辆为单车型，即全部车辆拥有相同装载能力，约定车辆不可超载，车辆的行驶速度相同，且每条线路有截止期限限制，行驶线路为闭合式[38]，即必须返回原出发点。

　　3)客户：全部客户的地理位置、需求量已知，每个客户需求可由多辆车依背包拆分送达，客户点间的旅行时间符合三角不等式约束。

　　4)道路：忽略道路交通带来的影响，车场到客户点、客户点与客户点之间都可直达。5)目标：最小化总的旅行时间。

　　2自适应TSA设计

　　禁忌搜索算法(TSA)是一种求解VRP效果较好的智能算法。Fu等[26]对带装载能力约束的不拆分开放式VRP进行了求解，其研究表明，在求解算法中接受部分不可行解，能够增强算法邻域搜索的柔性，有利于从不可行解过渡到更好的可行解，可增强算法的全局寻优能力。本文设计一种双优化解机制，每次迭代后保存相应的“最好解”和“当前解”，约定“最好解”必须可行，而“当前解”则可接受违反装载能力约束的邻域解。因此，本文在TSA搜索进程中有限的接受部分不可行解，并增设一种自适应惩罚机制，使得算法能够在迭代过程中自适应地调整搜索方向，增强自适应寻优能力，从而形成一个自适应TSA。

　　2.1解的表达方式与初始解构造

　　本文采用随机方式[26]生成初始可行解，先随机生成客户点的一个排列，然后在满足车辆装载能力的情况下，按照此排列顺序将客户点所对应的背包依次加入车辆线路中，当违背车辆装载能力限制时就开启一条新的车辆线路。其中，在构造初始可行解时，不考虑拆分，即同一客户的背包全部放入一条线路中。

　　2.2多邻域结构体设计

　　在大规模配送CVRPSDB中，组合情况特别复杂，其解空间非常庞大。设计多邻域结构体，对解空间进行邻域划分，采用不同的局部极值来逐步逼近全局最优解是一种很好的迭代寻优方式。随机邻域挑选策略能够有助于算法在各邻域之间自由变换，加速算法寻优。X0X0=50+N

　　因此，ATSA设计一个多邻域结构体，设计4种邻域操作算子，并采用随机邻域变换策略，每次随机选出一种邻域算子对当前解变换。约定每次生成邻域解的数目为，取。每次生成邻域解时，采用随机方式挑选出2条相异的线路R1与R2，然后采用随机挑选方式，在两线路内各挑选出一个非0的客户点或“背包”来进行操作。每次邻域操作后，逢多个0相邻则只保留最前面的一个，将同一线路内的同一客户点的“背包”按照前后顺序排列在一起(即同一线路内背包合并)，并对相关约束进行检验，判断生成的新邻域解是否可行。

　　在本文的CVRPSDB中，结合各“背包”与其相应客户点的对应关系，对客户点与“背包”进行统一操作，针对“客户点”和“背包”都设计相应的邻域操作算子，尽可能地降低了由于订单规模增大引发的求解难度。其中的“客户点”邻域操作算子相当于对同一客户点的“背包”实施了绑定策略，而“背包”邻域操作算子则相当于对同一客户点的需求量施行了离散拆分策略。本文针对“客户点”和“背包”都设计了相应的邻域操作算子，能够较好地适应CVRPSDB的邻域变换。

　　2.4禁忌表设计与迭代终止条件

　　禁忌表的结构与禁忌对象选取是TSA设计的重点。TSA中禁忌长度的类型与大小对算法性能影响很大，为防止算法前期的循环搜索和增强算法中后期的随机多样性，本文ATSA把固定值的禁忌长度和随机值的禁忌长度相结合，设计一个混合禁忌长度：在算法迭代寻优的前2000步内，为定值16，在2000步以后，每次迭代都在[5,16]内随机取。N×Nςςς≤0

　　ATSA设置一个阶的方阵式禁忌表，选取邻域变换中的点对(i，j)作为禁忌对象，表内的矩阵元素(i，j)用于存储禁忌对象的禁忌长度值。当点i与j或其对应的“背包”被挑选用于邻域变换，且其对应的候选解将成为下次迭代的“当前解”时，便在其对应的矩阵元素(i，j)中填入对应的值。本文约定在每次邻域变换后减1，直到方可解除对相应解的禁忌。若存在某个可行“候选解”优于当前取到的“最好解”，则把其设置为新的“当前解”与“最好解”，否则将非禁忌的最佳候选解置换为新的当前解;若全部“候选解”都被禁忌了，则释放最佳“候选解”，并将其设为新的当前解。为了增强算法全局寻优能力，防止因禁忌过度而漏搜了有关解集区域，本文增设一个“禁忌表重新初始化”策略，约定在迭代2000步以后，每隔m次迭代就将禁忌表重新初始化为全0矩阵，m=50。X1X1=5000+100N终止迭代的条件为：总迭代次数达到预设的上限值，本文取。

　　2.5算法描述依据禁忌搜索算法的基本框架，ATSA的基本流程如下。

　　Step1　初始化;

　　Step2　读入相关数据及参数值;

　　Step3　随机生成初始解，并把此解取为“最好解”与“当前解”;

　　Step4While未满足总迭代次数do;

　　Step5While候选解数目未达到预设值do;

　　Step6　在预设的4种邻域操作算子之间随机挑选出一种用于邻域变换;

　　Step7　按规则对“当前解”进行邻域变换，并构建候选解集;

　　Step8End;

　　Step9　挑选出新的“最好解”与“当前解”;

　　Step10　更新禁忌表;

　　Step11End;

　　Step12　输出结果。

　　3算法测试

　　3.1算例构造

　　需求依背包拆分VRP(VRPSDB)目前尚未有标准测试算例。文献[12]、[22]、[23]在研究经典CVRPSD时，都采用一个含1个配送中心、15个客户点、客户需求总和为4881、车辆载重为500的CVRP算例进行了算法测试。因此，本文在该算例基础上构造CVRPSDB算例，并将其标记为CVRPSDB-15。将算例中各客户点的需求拆分为1~4个背包，这样便构造出了CVRPSDB的算例CVRPSDB-15，其客户需求数据如表1所示。

　　3.2求解结果

　　本文使用的编程软件为Matlab2014a，并且在Lenovo3000，CPU为2.40GHz，内存为4GB的AMD笔记本上测试ATSA。运行20次，取最好的结果。

　　求解结果显示，CVRPSDB-15的总行驶距离为1720.8，有2个客户点的需求量被依背包离散拆分配送，具体求解结果如表2所示。其中，客户点5的需求量被依背包拆分进入线路4与线路10中，对应的离散拆分量分别为(71)与(64+90);而客户点14的需求量被依背包拆分进入线路1与线路6中，对应的离散拆分量分别为(136)与(22+143+161)。

　　3.3文献对比分析

　　ATSA与文献算法的对比结果见表3。表3中给出的聚类求解算法、改进蚁群算法与蜂群优化算法都是用来求解经典K-VRPSD类型的，文献[23]给出的传统VRP算法是用来求解需求不拆分VRP类型的。从求得的结果来看，本文算法求解的结果比4种对比算法求得的结果都要优，ATSA相对于聚类求解算法、改进蚁群算法、蜂群优化算法和传统VRP算法分别改进了2.53%、3.38%、2.43%和15.64%，这说明ATSA在降低车辆旅行时间方面具有优势。

　　4结论

　　带装载能力的需求依背包拆分VRP是一种新类型的VRP。从本文研究可知，对客户需求依背包进行离散拆分配送，既方便了拆分配货，又有助于缩短旅行时间，降低行驶成本。本文结合相关约束给出了对应的数学模型，并设计了一种自适应禁忌搜索算法(ATSA)进行求解。从测试结果来看，所设计的ATSA在降低行驶成本方面具有较强的能力。另外，在算法中嵌入自适应惩罚机制，设计多邻域结构体，采用随机邻域挑选方式，使用混合禁忌长度，增设禁忌表重新初始化策略等能够提升算法的爬山能力，增强寻优能力。不过，本文主要对纯送货类型的CVRPSDB及其自适应禁忌搜索算法进行了研究，而逆向物流VRP在实践中也是急需解决的难题。因此，后续将会对同时取送货类型的CVRPSDB进行研究，并设计出更为高效的求解算法。