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

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

带实际约束的大规模车辆路径问题建模及求解

针对现有算法不能有效求解卷烟配送过程中, 问题规模大并具有诸多实际约束条件限制这类实际问题, 首先分析实际约束, 建立问题模型; 然后从模型出发设计多阶段算法, 通过地理信息的分级管理实现区域划分, 在降低问题规模的同时消除交通障碍; 采用改进的k 均值聚类法分派线路, 将问题转化为求解小规模旅行商问题; 最后以济南市区的卷烟配送为例, 通过与典型优化算法的比较表明了所提出多阶段算法在实际应用中的优越性.

     

求解带容量约束车辆路径问题的离散鲸鱼算法

论文提出了一种离散鲸鱼算法求解带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem).该算法对基本鲸鱼算法的包围捕食操作、泡泡网捕食操作、随机捕食操作进行重定义,并采用基于距离代价的K-means算法在满足车辆最大载重约束条件下将客户划分到不同区域.并引入随机交换搜索、2-o...     

随机需求车辆路径问题及混合变邻域分散搜索算法求解

随机需求车辆路径问题(capacitated vehicle routing problem with stochastic demand,CVRPSD)是对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP)的扩展,需求不确定的特点使其较CVRP更复杂,对求解方法要求更高.基于先预优化后重调度思想,提出两阶段的混合变邻域分散搜索算法(variable neighborhood scatter search,VNSS)对该问题进行求解:预优化阶段构建随机机会约束规划模型,对客户点随机需求作机会约束确定型等价处理,生成最优预优化方案;重调度阶段采用新的点重优化策略进行线路调整,降低因失败点而产生的额外成本,减少对人工和车辆的占用.算例验证表明,随机机会约束模型和两阶段变邻域分散搜索算法在求解CVRPSD时较为有效,点重优化策略调整效果较佳.     

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

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

求解三维装载约束下车辆路径问题的混合禁忌搜索算法

三维装载约束下车辆路径问题是车辆路径问题集合中极为复杂的问题。针对这一问题,提出了三种混合禁忌搜索算法。该算法首先设计了空间处理方式,通过在初始解构造阶段采用不同的装载规则来实现客户货物的装载,然后引入禁忌搜索算法对解空间进行搜索。最后,扩展了Solomon的标准用例对三种算法进行了实验,实现结果显示提出的算法是求解该问题的有效算法,同时其中一种算法相对而言具有一定的优势。     

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

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

一种求解带时间窗车辆路径问题的混合差分进化算法

对带时间窗的车辆路径问题进行研究,建立以最小化车辆数量和行驶路程为目标的多目标数学模型,提出一种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成方式。其次,结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力,并在搜索过程中用随机个体替代种群中的重复个体,维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性,并采用擂台法则构造非支配解集。最后对18个不同规模的Solomon算例的求解结果表明,算法在行驶路程和车辆数量上的求解质量比人工蜂群算法分别平均提高了2.04%和14.95%,且与已知最优解相比,在车辆数量的求解质量上平均提高了14.53%,验证了所提算法的有效性。     

求解带时间窗车辆路径优化问题的改进细菌觅食算法

为求解带时间窗的车辆路径问题（VRPTW）,提出一种改进的细菌觅食算法。将待配送的客户点依据地理位置进行K-means聚类,使得到的分类结果在满足时间窗的要求下,按顺序插入配送路径的最佳位置中,构造VRPTW问题的初始解,同时通过结合趋化操作与大邻域搜索中的removal算子进行距离寻优,扩大算法搜索范围并提高运行效率。实验结果表明,在规定时间窗内,改进算法能合理安排配送路径并最小化总配送成本。     

一种求解0-1背包问题的二进制修正和声搜索算法

针对0-1 背包问题, 提出一种二进制修正和声搜索算法. 该算法修正了即兴创作过程, 对参数PAR进行动态调整, 同时提出一种随机修复机制, 有效修复不可行的和声, 增强算法的局部搜索. 采用一种可行和声初始化方式, 保证初始和声都是可行的, 整个搜索过程完全采用0-1 二进制模式, 对14 个0-1 背包问题进行测试. 将所提出算法与其他算法进行比较, 结果验证了所提出算法的有效性.

     

需求可拆分车辆路径问题的禁忌搜索算法

为解决实际配送运输中的车辆路径问题（Vehicle Routing Problem,VRP）,通过改进传统的数学模型,解除每个客户需求只能由l辆车配送的约束,建立改进的可拆分车辆路径问题（Split Delivery VRP,SDVRP）数学模型,并利用禁忌搜索算法（Taboo Search Algorithm,TSA）进行求解．在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理．算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率．     

有能力约束回收车辆路径问题的食物链算法

介绍了有能力约束逆向物流回收车辆路径问题,设计了求解有能力约束逆向物流回收车辆路径问题的食物链算法;选取文献典型算例进行了仿真求解及比较分析,结果表明设计的食物链算法性能优于遗传算法、粒子群算法和量子进化算法。     

A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints

This paper introduces a special vehicle routing problem, i.e. the cumulative capacitated vehicle routing problem with time-window constraints (Cum-CVRPTW). The problem can be defined as designing least-cost delivery routes from a depot to a set of geographically-scattered customers, subject to the constraint that each customer has to be served within a time window; accordingly, the objective costs are computed as the sum of arrival times at all the customers. The Cum-CVRPTW finds practical utility in many situations, e.g. the provision of humanitarian aids in the context of natural disasters. The Cum-CVRPTW can be viewed as a combination of two NP-hard problems, i.e. the vehicle routing problem with time windows and the cumulative vehicle routing problem. To effectively address this problem, an effective algorithm is designed, which is based on the frameworks of Large Neighborhood Search Algorithm and hybridizes with Genetic Algorithm. The proposed algorithm adopts a constraint-relaxation scheme to extend the search space, enabling the iterative exploration of both the feasible and infeasible neighborhood solutions of an incumbent solution. Furthermore, some speed-up techniques are designed to reduce the computational complexity. To elucidate its effectiveness, the proposed algorithm is examined on the benchmark instances from the literature. The resultant numerical findings show that the algorithm is able to improve and obtain some best-known solutions found by existing state-of-the-art methods.     

An improved hybrid firefly algorithm for capacitated vehicle routing problem

Firefly algorithm (FA) is a new meta-heuristic which is successfully applied to solve several optimization problems. However, it suffers from a drawback of easily getting stuck at local optima. This paper proposes a new hybrid FA, called CVRP-FA, to solve capacitated vehicle routing problem. In CVRP-FA, FA is integrated with two types of local search and genetic operators to enhance the solution’s quality and accelerate the convergence. The experiments are conducted over 82 benchmark instances. The results demonstrate that CVRP-FA has fast convergence rate and high computational accuracy. It significantly outperforms the other state-of-the-art FA variants in majority of the tested instances.     

改进的求解约束P-Median问题的分散搜索算法

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。     

Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new version of the classical capacitated vehicle routing problem, and it is equivalent to a traveling repairman problem with capacity constraints and a homogeneous vehicle fleet, which aims to minimize the total arrival time at customers. Many real‐world applications can be modeled by this problem, such as the important application resulting from the humanitarian aid following a natural disaster. In this paper, two heuristics are proposed. The first one is a constructive heuristic to generate an initial solution and the second is the skewed variable neighborhood search (SVNS) heuristic. The SVNS algorithm starts with the initial solution. At each iteration, the perturbation phase and the local search phase are used to improve the solution of the CCVRP, and the distance function in acceptance criteria phase is used to improve the exploration of faraway valleys. This algorithm is applied to a set of benchmarks, and the comparison results show that the proposed algorithms provide better solutions than those reported in the previous literature on memetic algorithms and adaptive large neighborhood search heuristics.     

多舱共配绿色车辆路径问题的改进变邻域搜索算法

针对社区团购前置仓配送场景中“多中心、高时效、多品类、高排放”难题, 本文提出多车场带时间窗的绿色多舱车车辆路径问题(MDMCG-VRPTW), 构建混合整数线性规划模型, 并设计改进的变邻域搜索算法(IVNS)实现求解. 采用两阶段混合算法构造高质量初始解. 提出均衡抖动策略以充分探索解空间, 引入粒度机制以提升局部搜索阶段的寻优效率. 标准算例测试结果验证了两阶段初始解构造算法和IVNS算法的有效性. 仿真实验结果表明,模型与算法能够有效求解MDMCGVRPTW, 且改进策略提高了算法的求解效率和全局搜索能力. 最后, 基于对配送策略和时效性的敏感性分析, 为相关配送企业降本增效提供更多决策依据.     

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

设计了一种改进的蚁群算法,将蚁群系统(ACS)与最大最小蚂蚁系统(MMAS)相结合,在状态转移规则中引入时间窗跨度与服务等待时间因素,并在算法的不同阶段采用不同的信息素蒸发策略以防止算法陷入局部最优.使用路径内2-opt优化方法以及路径间2-opt*优化方法对每次迭代过程所得到的最优解进行局部优化.通过对相关文献实验数据的测试结果表明,该算法在求解效果及运算效率上优于遗传算法与禁忌搜索算法.