带时间窗的车辆路径规划的改进蚁群系统算法研究_谢鑫煌.pdf

第36卷第3期2023年6月Vol.36 No.3Jun.2023四川轻化工大学学报（自然科学版）Journal of Sichuan University of Science&Engineering(Natural Science Edition)带时间窗的车辆路径规划的改进蚁群系统算法研究谢鑫煌，朱文忠，魏启康，江嘉文(四川轻化工大学计算机科学与工程学院，四川宜宾644000)摘要：带时间窗的车辆路径规划（VRPTW）是一个多项式复杂程度的非确定性（NP）的组合问题，在运输与配送物流邻域有着广泛的应用。研究表明，元启发式算法是解决VRPTW问题的有效方法。针对基础蚁群算法收敛速度慢、易陷入局部最优的问题，本研究提出了一种改进的蚁群系统。首先，在原算法中修改了信息素更新策略，采用分段函数调整信息素挥发因子；然后，在算法中引入禁忌搜索的邻域搜索算法，对路径的搜索采用2-opt变换策略；最后，实验采用Solomon Benchmark标准算例C1类数据进行Matlab仿真实验，验证并分析了改进策略的有效性。实验结果表明，对比基础蚁群算法，本次的改进算法在寻找全局最优解上有较好的效果，在不同客户数量规模下，由基础蚁群算法求解的成本221.6、424.4、1006.5分别减少至191.8、363.2和828.9。该数据集不同规模下的最优解分别为191.3、362.4及827.3，本次改进的算法实验解与最优解的差值比率仅有0.26%、0.22%和0.19%。关键词：路径规划；蚁群算法；蚁群系统；禁忌搜索中图分类号：TP391文献标志码：A引言随着电子商务经济的发展，商品的输送与传递日益依赖于物流行业1，而车辆路径规划问题（Vehicle Routing Problem，VRP）在物流运输中占有重要地位2。数据显示，2021年，我国的物流成本为16.7 万亿元，约占全国 GDP 的 14.6%，远高于其他国家3-4。Dantzig5在1959年提出VRP问题，将它定义为一个整数线性规划和一个组合优化问题。VRP是多 项 式 复 杂 程 度 的 非 确 定 性（Non-deterministicPolynomial，NP）的组合问题6，它主要包含一组车辆以及一组特定位置的客户构成的客户集合。每个客户都必须接受一次服务，所有车辆的每次行驶路线的起点和终点都是配送中心。VRP问题旨在为车队找到一组最优路线，以提高向相应的客户提供服务的效率，并实现最小化总路线成本的核心目标。收稿日期：2022-05-06基金项目：四川省科技研发重点项目(2019YFG0200);四川省科技创新(苗子工程)培育项目(2022049);四川省智慧旅游研究基地技术研发项目(ZHZJ19-01);四川轻化工大学研究生创新基金(y2021090;y2021092)通信作者：朱文忠(1971-),男,教授,硕士,研究方向为企业信息化与集成、物联网技术及应用、智能信息处理、最优控制等,(E-mail)文章编号：20967543（2023）03006808DOI:10.11863/j.suse.2023.03.09第36卷第3期谢鑫煌，等：带时间窗的车辆路径规划的改进蚁群系统算法研究带时间窗的车辆路径问题（Vehicle RoutingProblem with Time Window，VRPTW）是VRP的扩展。在VRPTW问题中，每个客户都有固定的时间窗口，只 有 在 对 应 时 间 段 内 货 物 才 可 被 客 户 接 收。VRPTW 是组合优化问题，众多学者对该问题的求解主要分为两种7-8：精确式求解和元启发式算法求解。就精确式算法而言，列生成法9和分支限界法10都有可行性较高的算法最优解；但随着数据量的增加，元启发式算法的优势更加明显11。常见的元启发式算法有蚁群算法12、粒子群算法13、遗传算法14、禁忌搜索算法15、模拟退火算法16等。关于元启发式算法在VRP上的解决，许多学者做了诸多探索17，如吴新胜等18通过总结群体移动规律，调整萤火虫的位置更新机制，提高了算法的路径寻优能力；针对需求可拆分的VRP，姜婷19提出先求出最短路径，再对最短路径进行切割，并按客户点的需求进行拆分。蚁群算法（Ant Colony Optimization，ACO）拥有较强的鲁棒性，且可与其他算法相结合20。蚁群系统算法（Ant Colony System，ACS）是一种自适应蚁群算法，是蚁群算法的变体，通过对蚁群算法的状态转移概率、信息挥发因子及信息量等因素进行自适应调节作为改进策略。针对基础的ACO解决VRP时容易陷入局部最优的情况，本研究采用ACS，以及采用不同的信息素更新策略，当ACO接近收敛时，采用禁忌搜索来保持ACS解的多样性，并探索新的解决方案，增强算法寻找全局最优的能力。1VRPTW数学模型的构建在 VRPTW 中，追求的目标是在有时间窗的情况下解决车辆路径问题的最佳方案。这类问题包括一队卡车，离开仓库时，必须覆盖多个客户，并使用尽可能短的路径返回仓库。卡车的数量是任意的，每辆卡车访问的客户数量也是任意的，但每个客户都有一个时间窗口，客户只在时间窗内接受服务。因此，有以下约束：1）车辆起点和终点都是配送中心；2）每辆车的承载量都不能超过最大容量Q；3）每个客户都必须接受一次服务；4）客户只在时间窗内接受服务。定义G=(V，A)为有向完全图，V=c0,c1,cn为节点集合，A=|ci,cj V,ci cj为车辆行驶路线的边集。c0表示配送中心，ci()i=1,2,n表示客户i，其对应的需求量为qi，配送中心c0的需求为 0。节 点ci和cj的 距 离 由 欧 氏 距 离 表 示，且dij=dji。客户i节点都有对应的时间窗口si,ei，表示客户i接受服务的时间区间。VRPTW 需要实现两个目标：1）车辆路线的数量最小化；2）在相同的路线数量下，车辆的总行程最小化。综上，该问题有目标函数（式(1)）与约束条件（式(2)）：|minZ1=NVminZ2=i=0nj=0nk=1NVtij Xkij（1）|xkij=0,1yki=0,1i=0nxkij=yki,k=1,2,NV,i=1,2,nj=0nxkij=ykj,k=1,2,NV,j=1,2,ni=0nyki qi Q,k=1,2,NVk=1NVyki=1,i=1,2,nk=1NVyk0=NVsj tj ej,j=1,2,nwi=maxei-ti,0,j=1,2,nti+wi+si+tij=t,i,j=1,2,n,i j（2）其中，Z1表示车辆路线最小化数量，Z2表示在相同的路线数量下车辆最小化总行程；xkij表示车辆k是否从客户i到客户j，若是，则为1，反之为0；yki表示客户i是否由车辆k所服务，若是，则为1，反之为0；692023年6月四川轻化工大学学报（自然科学版）i=0nxkij=yki或j=0nxkij=ykj表示客户i和客户j的服务车辆为同一车辆k；i=0nykiqiQ表示每辆车携带的货物数量不能超过容量Q；k=1NVyki=1表示每个客户只能被一辆车服务；k=1NVyk0=NV表示所有路线都从配送中心开始；sj tj ej与wi=maxei-ti,0为时间窗口约束，ti为车辆到达客户i的时间，wi为车辆在客户位置等待到si的时间，ei为客户i接受服务的结束时间；tij是节点i和j之间的车辆行驶时间。最后时间t保证了可行解中服务时间、等待时间和出行时间的连续性。2改进蚁群系统ACS 比基本的 ACO 拥有更好的性能，ACS 在ACO 的基础上，使用伪随机比例规则选择一个节点，建立蚂蚁选择当前路线还是探索新路线的平衡。ACS思想如下：给定一定数量的蚂蚁，起初每个蚂蚁随机搜索路径，在路径上留下信息素，并行搜索问题的解决方案。后代蚂蚁通过信息素浓度大小选择路径。信息素蒸发降低了第一只蚂蚁选择的路径对下一只蚂蚁的吸引力，扩大了搜索空间，在一定程度上避免了算法陷入局部最优。每只蚂蚁都从一个初始为空的解决方案开始，解决方案将通过选择一个具有以下规则的可行解决方案来扩展：1）优先选择等待时间短的客户；2）优先选择时间窗宽度小的客户；3）如果随机值ri小于r0，则选择下一个j；4）否则，使用轮盘赌法计算Pkij并选择下一个客户。只有当蚂蚁服务完n个顾客后，才算该蚂蚁完成任务。假设蚂蚁当前在顾客i，向下一个顾客j转移的概率P为：|P=argmaxjNkiijij1/widthj1/waitj,r r0Pkij=ijij1/widthj1/waitjiNki()ijij1/widthj1/waitj,r r0（3）其中，为信息素；为启发式信息，等于节点i和j距离的反值；widthj为顾客的紧急程度，其值等于顾客接受服务的结束时间与开始时间的差值；waitj为顾客的等待时间，其值等于车辆到达顾客的时间与车辆从配送中心出发的时间的差值；、为各因素的加权值；r0为区间0,1之间的常量。若该蚂蚁找不到下一个顾客服务，那么该蚂蚁返回配送中心，时间置为0，载货重置为0。当所有蚂蚁完成任务后，找到总路程长度最小的蚂蚁，使用该蚂蚁更新最佳路线。3改进策略3.1设立分段信息素挥发因子在 ACO 算法中，信息素更新是极为重要的阶段。大部分 ACO 算法的变体，如蚂蚁系统（AntSystem，AS），最大-最小蚂蚁系统（Max-Min AntSystem，MMAS）及精英蚂蚁系统(Elite Ant System，EAS)等之间的差异都是由信息素规则的差异引起21。信息素用于模拟蚂蚁之间的局部的信息交互。挥发因子太小可以加强前代蚂蚁对后代蚂蚁的引导力，但容易使算法陷入局部最优；挥发因子太大可以增强蚂蚁的全局寻优能力，但易使算法结果不稳定。本次研究设立分段信息素挥发因子，以适用于不同阶段的算法需求。=|0.10,0 N Nmax/30.25,Nmax/3 N 2Nmax/30.50,2Nmax/3 N Nmax（4）其中，N为当前迭代次数，Nmax为最大迭代次数。70第36卷第3期谢鑫煌，等：带时间窗的车辆路径规划的改进蚁群系统算法研究3.2最优路径的信息素更新基础蚁群算法信息素浓度更新如式(5)(6)所示：newij=(1-)oldij+mij（5）mij=QTDm（6）其中，newij为更新之后的信息素浓度，oldij为更新前的信息素浓度，mij为本次迭代的信息素增量，为信息素挥发因子，Q为常数，表示蚂蚁初始时携带的信息素总量；TDm为第m只蚂蚁行走的路径总长。在基础蚁群算法的每次迭代中，蚂蚁经过的所有路径信息素都按式(5)(6)进行更新。随着迭代次数的增加，最优路径和其他路径的信息素之间存在较大的浓度差异。在后续的迭代中，蚂蚁倾向于选择这条最佳路径，算法容易陷入局部最优。本次只针对最优路径更新：newij=(1-)oldij+QBD（7）其中BD为当前全局最优的路径长度。3.32-opt邻域搜索2-opt又叫二元素优化，其核心在于随机选择一个区间段进行优化，该优化只是对于当前状态的优化，并不是对全局的优化22。2-opt策略对比如图1所示，正方形代表配送中心，圆圈代表客户，虚线表示两点间省略了多个节点，实线表示两点间直接相接。与原搜索状态（图1(a)）相比，2-opt邻域搜索（图1(b)）通过从一条路线中删除两条连接，并用另外两条路线替换它们来重新连接节点，且由于客户时间窗口的因素，采用2-opt邻域搜索后，子路径（i+1,j+1）的方向会有变化。(a)原搜索状态(b)改进状态图12-opt策略对比3.4改进算法流程本文提出改进算法主要步骤如下：1）改进 ACS算法初始化。设置改进 ACS的参数，初始化路径的信息素。2）路径构造。每只蚂蚁从仓库出发后根据转移规则构建路线。3）本地搜索。每只蚂蚁构造出一个解决方案后，邻域搜索用于探索邻居解决方案。2-opt交换策略用于改进邻域解。如果邻域解优于当前解，邻域解将替代当前解。4）信息素更新。根据解的优劣情况计算信息素增量，更新最优路径上的信息素。5）判定禁忌状态。在当前算法中，只使用一次禁忌搜索。且当改进ACS算法获得3个连续的相同解时，考虑是否是全局最优解或是陷入局部最优。如果尚未使用禁忌搜索，转至步骤 6）；否则，转至步骤8。6）禁忌搜索。将改进 ACS算法中当前最优解转化为禁忌搜索的初始解。然后，根据2-opt搜索邻域解决方案，并在改进ACS算法中更新最优路径的信息素。7）禁忌搜索终止。检查禁忌搜索终止条件。若满足终止条件，则转至步骤2）并继续执行算法；否则，转至步骤6）并继续执行禁忌搜索。8）改进ACS终止。检查改进ACS的终止条件。如果满足终止条件，则终止ACS；否则，请转至步骤2）并继续进行改进ACS算法搜索。实验算法总流程如图2所示。712023年6月四川轻化工大学学报（自然科学版）图2实验流程4实验结果与分析4.1实验条件及数据集说明不同的参数设置会对算法性能产生较大的影响。本次 ACS 实验参数取值如下：=1，=3，=2，=3，Q=1000，m=1.5 节点数，NCmax=2000。本文所设计的实验运行在i5-4210M双核CPU2.6 GHz、内存8 G的便携式笔记本电脑，运行环境为Matlab2018a。实 验 原 始 数 据 从 Solomon Benchmark 获 得。Solomon benchmark 是国际通用的 VRP标准测试数据集，内附有当前最优解。VRPTW 的标准数据有R1、R2、C1、C2、RC1、RC2 6个类别，共56个数据集。不同的类别划分依据为客户是否聚集、时间窗宽度大小等。实验采用C1类数据作为实验源数据，考虑单配送中心对聚集型客户群体的路线规划问题。C1类数据下共有9个子数据集，列举C101的前十个客户数据内容类型见表 1，单次最多车辆（VEHICLE NUMBER）为 25，每个车辆的最大载重量（CAPACITY）为200。表1中，CUST No0为配送中心；XCOORD 和 YCOORD 分别为节点横、纵坐标；DEMAND为客户的需求量；节点的时间窗分别为起始时间（READY TIME）、结束时间（DUE DATE）及服务时间（SERVICE TIME）。表1样本数据说明CUSTNo012345678910XCOORD4045454242424040383835YCOORD5068706668656966687066DEMAND010301010102020201010READYTIME09128256572715621170255534357DUEDATE123696787014678267702225324605410SERVICETIME0909090909090909090904.2改进ACS算法与基本ACO算法对比实验首先将C1类下的9个子数据集细化分为3个规模：小规模、中规模、大规模。实验测试了不同数据规模下的问题求解，分别为25个客户、50个客户以及100个客户。其中，C101的仿真结果如图3及图4(a)所示。由图3及图4(a)可知，本文所用的算法在客户的聚集识别上表现出了较大的优势，能较好地区分不同区域的客户集群，并且能安排相应的车辆服务各个区域的客户，不同区域的车辆的服务路线未出现重合或交叉。由图4(a)可知，本文所用的改进ACS算法在大规模数据中对客户群体的区域划分仍有较好的效果。而 基 础 蚁 群 算 法 在 车 辆 的 路 径 规 划 上（图4(b)），存在一些显著缺陷，如，将不同区域的客户安排至同一条车辆服务路线；对于同一区域的客户，不能较好地完成路线规划；部分车辆的行驶路线存在交叉。72第36卷第3期谢鑫煌，等：带时间窗的车辆路径规划的改进蚁群系统算法研究(a)25个客户仿真(b)50个客户仿真图3小规模和中规模的实验仿真(a)100个客户仿真(b)基本蚁群算法仿真图4大规模实验仿真对比基础ACO算法和改进ACS算法的收敛情况如图5所示。从收敛速度来看，改进ACS算法能较快地完成第一次收敛。从寻优能力来看，改进ACS算法完成第一次收敛后能不断地进行向前搜索，而基础 ACO 算法则在较长的一段时间停滞在当前解。反映在图5中，即基础ACO算法在第90次左右找到改进解，在完成120次迭代后就停滞在当前最优解。相较之下，改进的ACS算法寻优能力更强，在陷入局部最优时能及时地跳出，完成后续的寻优操作。因此，改进ACS算法的收敛速度良好，寻优能力更强，且最优路径的总长度最短，达到了算法改进的目的。图5收敛曲线对比各类数据规模下的历来最优解由列生成算法求得，公开在Solomon Benchmark官网。列生成算法最优解是指，当客户规模分别为25、50和100时，在732023年6月四川轻化工大学学报（自然科学版）控制对应规模的车辆数量情况下的最短行驶距离。对比基本ACO算法、改进ACS算法以及官网数据，各个规模的实验结果对比见表2。表2最优解对比数据集C101.25C101.50C101.100基础ACO算法解车辆规模/辆3510行驶距离221.6424.41006.5改进ACS算法解车辆规模/辆3510行驶距离191.8363.2828.9列生成算法最优解车辆规模/辆3510行驶距离191.3362.4827.3由表 2 可知，在不同的数据规模下测试基本ACO 算法和改进 ACS 算法发现，本次采用的改进ACS算法在各个车辆规模中的效果都有较大提升，明显减少了服务成本。其中，小、中、大规模数据下的行驶距离分别减少了 29.8、61.2 和 177.6。对比Solomon官网公布的数据，虽然本次改进的 ACS算法解与列生成算法最优解有一定差距，但数据总体表现良好，不同规模下两者的差值比率仅有0.26%、0.22%和0.19%。5结束语本文首先分析了基础蚁群算法求解VRP易陷入局部最优、收敛速度慢等特点，随后提出采用改进的蚁群系统算法，通过设置分段的信息素挥发因子控制算法的收敛，并在算法过程更改了信息素的更新策略。算法的每次迭代只更新最优路径的信息素浓度，且当蚁群算法可能陷入局部最优时，采用禁忌搜索并引入2-opt邻域搜索来扩大算法的求解空间，以探索新的解决方案，增强了算法寻找全局最优的能力，保持了蚁群系统算法解的多样性。实验数据源于 Solomon Benchmark C1类数据，并分别进行了25个客户、50个客户、100个客户的实验仿真。结果表明，较之基础蚁群算法，改进ACS算法在C1类数据上取得了较好的效果，且实验结果接近历史最优的列生成算法解。VRP变体较多，且不同变体的数据集也有较大差异。本文工作对于前期实验的参数设置，仍靠人工调整的方式获取最佳参数，且实验的仿真数据仅考虑了单配送中心的C1类聚集型的客户数据，未对多配送中心和位置分散型客户等的数据集进行实验验证。后续研究应努力寻找获得最佳参数值的方式，而不是靠人工调整。同时，后期实验论证应向VRP添加更多约束，使其更具动态性和即时性。参考文献：1 柏鑫,鲁力群,孙萌,等.电商企业物流模式的比较与选择J.物流技术,2022,41(3):81-85,120.2 赵灿华,侍洪波.基于自适应变邻域搜索的大规模电动车辆路径优化J.华东理工大学学报(自然科学版),2020,46(5):694-701.3 高鑫.基于深度强化学习的异构车队分批交付问题研究D.兰州:西北师范大学,2022.4 潘立军.带时间窗车辆路径问题及其算法研究D.长沙:中南大学,2012.5 DANTZIG G B,RAMSER J H.The truck dispatching problemJ.Management Science,1959,6(1):80-91.6 刘虹庆,王世民.基于强化学习的车辆路径规划问题研究J.计算机应用与软件,2021,38(8):303-308.7 庞燕,罗华丽,邢立宁,等.车辆路径优化问题及求解方法研究综述J.控制理论与应用,2019,36(10):1573-1584.8 黄秋爱,李珍萍.多时间窗车辆路径问题的数学模型及算法J.物流技术,2012,31(13):194-196.9 金伟,李夏苗,周凌云,等.基于列生成算法的高速铁路快捷货运组织方案优化研究J.铁道学报,2020,42(9):26-32.10 WANG Z,ZENG Q.Abranch-and-bound approach forAGV dispatching and routing problems in automated container terminalsJ.Computers&Industrial Engineering,2022,166:107968.11 尚正阳,顾寄南,唐仕喜,等.针对几种元启发式算法的应用性能对比研究J.机械设计与制造,2021,362(4):34-38.74第36卷第3期谢鑫煌，等：带时间窗的车辆路径规划的改进蚁群系统算法研究12 陈磊.基于蚁群算法的物流配送车辆路径问题研究D.兰州:兰州交通大学,2016.13 谢传聪.粒子群优化算法在车辆路径问题中的应用研究D.成都:电子科技大学,2019.14 韩亚娟,彭运芳,魏航,等.超启发式遗传算法求解带软时间窗的车辆路径问题J.计算机集成制造系统,2019,25(10):2571-2579.15 庞燕,罗华丽,夏扬坤.基于禁忌搜索算法的废弃家具回收车辆路径优化J.计算机集成制造系统,2020,26(5):1425-1433.16 巩敦卫,曾现峰,张勇.基于改进模拟退火算法的机器人全局路径规划J.系统仿真学报,2013,25(3):480-483.17 蒋华伟,郭陶,杨震.车辆路径问题研究进展J.电子学报,2022,50(2):480-492.18 吴新胜,姜婷,赵梦超,等.基于群智能混合算法的应急物流路径优化研究J.四川理工学院学报(自然科学版),2018,31(4):68-73.19 姜婷.求解需求可拆分车辆路径问题的人工蜂群算法J.四川理工学院学报(自然科学版),2017,30(3):6-9.20 徐玉琼,娄柯,李婷婷,等.改进自适应蚁群算法的移动机器人路径规划J.电子测量与仪器学报,2019,33(10):89-95.21 DORIGO M,BIRATTARI M,STUTZLE T.Ant colony optimizationJ.IEEE Computational Intelligence Magazine,2006,1(4):28-39.22 CROES GA.Amethod for solving traveling-salesman problemsJ.Operations Research,1958,6(6):791-812.引用格式：中文:谢鑫煌,朱文忠,魏启康,等.带时间窗的车辆路径规划的改进蚂蚁系统算法研究J.四川轻化工大学学报(自然科学版),2023,36(3):68-75.英文:XIE X H,ZHU W Z,WEI Q K,et al.Research on improved ant colony system algorithm for vehicle routing planning with time windowJ.Journal of Sichuan University of Science&Engineering(Natural Science Edition),2023,36(3):68-75.Research on ImprovedAnt Colony SystemAlgorithm forVehicle Routing Planning withTimeWindowXIE Xinhuang,ZHU Wenzhong,WEI Qikang,JIANG Jiawen(School Computer Science and Engineering,Sichuan University of Science&Engineering,Yibin 644000,China)Abstract:Vehicle routing planning with time window(VRPTW)is a Non-deterministic Polynomial(NP)combinatorial problem with complexity,which is widely used in the neighborhood of transportation anddistribution logistics.It is found that meta heuristic algorithm is an effective method to solve problems existed inVRPTW.Aiming at the problems of slow convergence speed and easy to fall into local optimization of basic antcolony algorithm,an improved ant colony system has been proposed in the present study.Firstly,the pheromoneupdating strategy is modified in the original algorithm,and the piecewise function is used to adjust thepheromone volatilization factor;then,the neighborhood search algorithm of tabu search is introduced into thealgorithm,and the 2-opt transformation strategy is adopted for the path search;Finally,Matlab simulationexperiments are carried out on C1 data of Solomon benchmark standard example to verify and analyze theeffectiveness of the improved strategy.The experimental results show that the improved algorithm has a goodeffect on finding the global optimal solution.Under different customer sizes,the cost of solving by the basic antcolony algorithm decreased from 221.6,424.4,and 1006.5 to 191.8,363.2,and 828.9,respectively.The optimalsolutions for different scales of this dataset are 191.3,362.4,and 827.3,respectively.The difference ratio betweenthe experimental solution and the optimal solution of this improved algorithm is only 0.26%,0.22%,and 0.19%.Key words:route planning;ant colony algorithm;ant colony system;tabu search75