求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法

带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解.为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出相对较优解.研究了求解带容量和时间窗约束车辆路径问题的改进离散蝙蝠算法,为增加扰动机制,提高搜索速...     

混合分散搜索算法求解带容量约束车辆路径问题

设计一种解决带容量约束车辆路径问题的混合分散搜索算法. 在基本分散搜索的基础上, 保留参考集更新策略和组合策略的全局搜索能力. 采用随机插入法作为解的多样性产生方法, 以扩大搜索空间, 避免陷入局部最优.应用简化的变邻域搜索作为改进策略进行局部开发, 引入邻域半径减少策略提高开发效率. 对改进后的新种群实施精英保留策略, 保证算法收敛. 实验结果分析表明, 混合分散搜索算法优于所对比的算法, 寻优能力可靠.

     

带容量约束车辆路由问题的改进蚁群算法

提出一种带容量约束车辆路由问题(CVRPs)的改进蚁群算法.该算法使用一种新的蚂蚁位置初始化方式,增加了蚂蚁走出最优路径的可能性.在搜索过程中,以客户之间路径的节省量作为启发式信息.信息素更新采用一种动态更新的方法,能够根据当前车辆所构建路径的情况对信息素进行更新,避免算法陷入停滞状态.局部搜索除使用2-opt方法外,针对不同车辆访问的客户,还增加了交换搜索和插入搜索以扩大搜索范围.仿真实验验证了所提出算法的有效性.     

求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法

针对带容量约束的车辆路径问题,提出一种混合变邻域生物共栖搜索算法.设计基于客户点优先序列及车辆参考点模拟信息的有序编码,该编码方案使生物共栖搜索算法可以参与CVRP的离散优化;为了提高算法的全局搜索能力,根据有序编码特点构造3种共栖搜索算子,扩大搜索空间;同时,结合变邻域搜索算法设计客户点重置、交换和2-OPT三种局部搜索策略,以提高解方案质量.算例验证分析表明,所提算法能够有效地解决容量约束车辆路径问题,求解质量优于所对比算法,具有可靠的全局稳定性.     

求解带容量约束的车辆路径问题的改进伊藤算法

针对车辆路径问题中路径选择未能确定的缺陷,引入蚁群算法对客户点选取规则进行决策。此外,采用冷却进度表作为控制温度变化的参数,将漂移和波动过程同步进行来改进根据伊藤随机过程而设计的伊藤算法,并将改进后的算法应用于CVRP的求解。实验结果表明,改进后的算法能有效求解带容量约束的车辆路径问题,取得了理想的结果。     

融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题

对于求解带时间窗口车辆路径问题,提出一种融合邻域搜索策略的改进蚁群算法,针对时间窗口特性,将等待时间加入到蚁群算法的状态转移规则之中。为提升算法的局部寻优能力,设计多种节点删除操作和插入操作对得到的路径进行邻域搜索。最后利用Solomon标准算例对改进算法进行测试,与目前已知最优解对比,实验结果表明改进后的蚁群算法对带时间窗口的车辆路径问题有较好的适用性。     

求解车辆路径问题的离散粒子群算法

考虑车辆行驶时间和顾客服务时间的不确定性,建立了以车辆配送总费用最小为目标的机会约束规划模型,将其进行清晰化处理,使之转化为一类确定性数学模型,并构造了求解该问题的一种离散粒子群算法。算法重新定义了粒子的运动方程及其相关离散量运算法则,并设计了排斥算子来维持群体的多样性。与标准遗传算法和粒子群算法比较,该算法能够有效避免算法陷入局部最优,取得了满意的结果。     

车辆路径问题的离散细菌菌落算法

为了丰富解决车辆路径优化问题的方式,提出一种融入了局部搜索的离散型细菌菌落优化算法。首先设计了算法的个体编码方式和进化模式;然后融入局部搜索方式来加速算法寻优的效率;最后将该算法应用于带时间窗的车辆路径问题,并采用solomon数据验证,通过与其他算法进行比较,验证算法的可行性。     

策略梯度的超启发算法求解带容量约束车辆路径问题

有容量车辆路径问题是组合优化问题中比较热门的问题, 它属于经典的NP-hard问题并且时间复杂度高.本文提出了一种基于策略梯度的超启发算法, 将强化学习中的确定性策略梯度算法引入到超启发算法的高层策略中的底层算法选择策略, 确定性策略梯度算法采用Actor-Critic框架, 另外为了能够在后续计算和神经网络参数更新中引用历史经验数据, 在确定性策略梯度算法中设计了经验池用于存储状态转移数据. 在超启发算法解的接受准则方面, 文中通过实验对比了3种接受准则的效果, 最终选择了自适应接受准则作为高层策略中解的接受准则. 通过对有容量车辆路径问题标准算例的计算, 并将求解结果与其他算法对比, 验证了所提算法在该问题求解上的有效性和稳定性.     

基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解

为应对大数据时代对带时间窗车辆路径问题（VRPTW）的实时求解要求,提出基于Spark平台的改进蚁群算法.在算法层面,利用改进的状态转移规则和轮盘赌选择机制构建初始解,结合k-opt邻域搜索进行路径构建优化,改进最大最小蚁群算法中的信息素更新策略;在实现层面,利用Spark提供的API对蚁群RDD进行操作,实现蚁群分布式并行求解.在标准算例Solomon benchmark和Gehring&Homberger benchmark的实验结果表明,该算法在大规模问题的求解精度和速度上有明显提升.     

用于求解混合车辆路径问题的混合进化算法

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。     

A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

In this paper, a memetic algorithm with competition (MAC) is proposed to solve the capacitated green vehicle routing problem (CGVRP). Firstly, the permutation array called traveling salesman problem (TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor (kNN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search (VNS) framework and the simulated annealing (SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station (AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-of-experiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.      

A List Based Threshold Accepting Algorithm for the Capacitated Vehicle Routing Problem

The aim of this study is to describe a new stochastic search meta-heuristic algorithm for solving the Capacitated Vehicle Routing Problem (CVRP), termed as the List Based Threshold Accepting (LBTA) algorithm. The main advantage of this algorithm over the majority of other meta-heuristics is that it produces quite satisfactory solutions in reasonable amount of time by tuning only one parameter of the algorithm. This property makes this algorithm a reliable and a practical tool for every decision support system designed for solving real life vehicle routing problems.     

Memetic Algorithm With Extended Neighborhood Search for Capacitated Arc Routing Problems

The capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable to small instances, heuristic and metaheuristic methods are widely adopted when solving CARP. In this paper, we propose a memetic algorithm, namely memetic algorithm with extended neighborhood search (MAENS), for CARP. MAENS is distinct from existing approaches in the utilization of a novel local search operator, namely Merge-Split (MS). The MS operator is capable of searching using large step sizes, and thus has the potential to search the solution space more efficiently and is less likely to be trapped in local optima. Experimental results show that MAENS is superior to a number of state-of-the-art algorithms, and the advanced performance of MAENS is mainly due to the MS operator. The application of the MS operator is not limited to MAENS. It can be easily generalized to other approaches.     

混合禁忌搜索算法求解关联运输调度问题

考虑到实际生活中车辆受发车时间限制以及道路路况影响运输成本等因素,建立了带客户软时间窗、车场硬时间窗、多车型、道路路况等约束的关联运输调度问题模型.结合禁忌搜索与遗传算法的优势,构造了混合禁忌搜索算法,以通过构造多个初始解来增大搜索空间;设计了两种禁忌表,分别为局部禁忌表和全局禁忌表,这不仅能加快寻优速度,还可以摆脱对单个解的依赖;将禁忌搜索生成的优化解作为遗传算法的初始解,可以加快寻优速度;自适应调整禁忌表长度可以避免早熟收敛;提取核心路径便于进行后期优化,relocate算子能减少路径网络回路数目.对实例进行的仿真表明,提出的IVRP优于一般的VRP,可节约大量成本,且提出的算法在收敛速度和寻优结果两方面都优于遗传算法和禁忌搜索算法.由3种算法求解得到的总成本、总里程及收敛时间的标准差体现出该算法的稳定性比另外两种算法的好.     

求解应用层组播路由问题的遗传算法

分析了应用层组播路由模型，提出了更合理的应用组播路由模型．进一步给出了求解应用层组播路由问题的遗传算法，并分析了该算法的复杂性．大量的数值仿真表明该算法有较好的数值效果．     

客户分类下生鲜配送两级路径问题与算法研究

生活水平的提高使得消费者对生鲜产品的需求不断增长,进而促进了冷链物流行业的快速发展。将客户按重要性分为重要客户和普通客户两类,以总配送成本最小为目标,建立考虑客户分类的两级容量有限车辆路径优化模型。提出两阶段启发式算法求解该模型：第一阶段设计改进的遗传-模拟退火算法增强全局搜索能力,其中采用轮盘赌选择机制结合精英保留策略保留优秀个体,部分匹配交叉算子结合自适应交叉率维持种群多样性,Metropolis准则以一定概率接受较差解;第二阶段使用精确方法求解一级配送路径。基于Perboli的Set2算例集和Hemmelmayr的Set5算例集,共30个基准案例,分别将所提出算法与四种现有算法进行对比分析,验证了改进算法的效果,并测试了算法的收敛性。基于模拟数据进行模型分析,验证了所提出模型和算法的有效性和适用性。     

求解旅行商问题的改进离散竞争进化算法

在分析竞争进化算法原理和特点的基础上,针对旅行商问题的求解,提出一种改进的离散竞争进化算法(IDCE),其中采取三项关键策略:根据个体适值排名计算变异次数、实施逆转子变异算子和并行贪心机制执行多次子变异,目的在于提高算法的全局搜索能力和单位时间内的进化效率.IDCE算法跟另两种离散竞争进化算法对于4个对称旅行商问题算例进行了性能对比,实验结果显示,在解的整体水平、最好解质量以及求解效率上,IDCE算法都优于另两种算法.