带时间窗的车辆路径规划的改进蚁群系统算法研究_谢鑫煌.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）判定禁忌状态。在当前算法中，只使用