带时间窗车辆路径问题的混合改进型蚂蚁算法

带时间窗车辆路径问题（VRPTW）是VRP的一种重要扩展类型,在蚂蚁算法思想基础上,设计用于求解该问题的混合改进型算法并求解Solomon标准数据库中的大量实例。经过大量数据测试并与其他启发式算法所得结果进行比较,获得了较好的效果。     

混沌扰动模拟退火蚁群算法低碳物流路径优化

低碳物流是目前物流配送领域的热点研究课题,也是群体智能优化算法的重要应用方向。针对物流配送中碳排放的度量方法,以VRP问题为基本模型,以碳排放成本为目标函数,建立了低碳物流配送路径优化模型。为了避免基本蚁群算法出现停滞及早熟现象,提出了带混沌扰动的模拟退火蚁群算法来求解低碳物流配送路径优化模型。该算法将混沌系统及模拟退火机制引入基本蚁群算法,避免了算法陷入局部最优,增强了全局搜索能力,提高了求解效率。通过实验仿真及对比分析可知,带混沌扰动的模拟退火蚁群算法的求解结果明显优于基本蚁群算法,表明了该算法的有效性和合理性。     

基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题

为求解车辆路径问题,提出一种新的基于混沌扰动和邻域交换的蚁群算法。针对标准蚁群算法存在搜索时间长,容易出现早熟收敛,得到的解不是最优解等缺点,新算法利用混沌的随机性、遍历性及规律性,在算法陷入早熟时,对小部分路径的信息素采用混沌扰动策略进行调整;针对标准蚁群算法的贪心规则随机性缺点,新算法采用邻域交换策略对最优解进行调整。在用于求解不同规模车辆路径问题的仿真结果表明,新算法比标准蚁群算法和遗传算法具有更好的效果。     

A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.     

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

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

A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem

In this paper, we propose a new metaheuristic to solve the Risk constrained Cash-in-Transit Vehicle Routing Problem (Rctvrp). The Rctvrp is a variant of the well-known capacitated vehicle routing problem and models the problem of routing vehicles in the cash-in-transit sector. In the Rctvrp, the risk associated with a robbery represents a critical aspect that is treated as a limiting factor subject to a maximum risk threshold.A new metaheuristic, called aco-lns is developed. It combines the ant colony heuristic for the travelling salesman problem and a variable neighbourhood descent within an large neighbourhood search framework.A new library of Rctvrp instances with known optimal solutions is proposed. The aco-lns is extensively tested on small, medium and large benchmark instances and compared with all existing solution approaches for the Rctvrp.     

避免车辆路径拥塞的动态蚁群算法

运用蚁群算法,对非闭合线路避免拥塞现象的车辆路径问题进行研究,提出了深度为1的树结构指针推进策略和相应的路径优化算法,为交通管理和车辆导航提供决策依据。仿真结果表明该算法具有较强的道路拥塞识别能力,能够有效缓解道路拥塞现象。     

Adaptive memory programming for the vehicle routing problem with multiple trips

The Vehicle Routing Problem with Multiple Trips is an extension of the classical Vehicle Routing Problem in which each vehicle may perform several routes in the same planning period. In this paper, an adaptive memory algorithm to solve this problem is proposed. Computational experience is reported over a set of benchmark problem instances.     

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

针对带时间窗车辆路径问题，论文通过增加虚拟配送中心的数量，改进蚁群算法，从而将VRPTW问题转化为TSP问题进行求解，使每只蚂蚁都可以构建一条可行路径，避免在该问题中以往常由多只蚂蚁协同合作来构造解的低效性，通过实验计算表明该方法是可行的。     

求解带硬时间窗车辆路径问题的时差插入启发式算法

针对已有求解带硬时间窗车辆路径问题时插入启发式算法结构复杂、参数多、求解效率不高的缺点,提出了求解该问题的时差插入启发式算法。该算法引入时差的概念,将时差作为启发规则的评价指标。相比已有求解该问题的经典启发式算法,该算法有参数个数少、算法结构简单等特点。应用标准测试算例测试表明,所提算法的求解质量优于Solomon的插入启发式算法和Potvin的平行插入启发式算法。     

生鲜电商配送的开放式时变车辆路径问题研究

针对生鲜电商配送的“最后一公里”难题,考虑到生鲜农产品的易腐易损性与生鲜电商通常采用普通车辆配送等现实情况,引入常温条件下生鲜农产品的鲜活度度量函数;分析城市路网的时变特性,设计时变路网条件下的车辆行驶时间计算方法;综合考虑客户需求量、时间窗、生鲜农产品送达客户时的鲜活度、开放式车辆路径与车辆灵活出发时间等因素,以总配送成本最小为目标构建具有鲜活度限制的开放式时变车辆路径问题优化模型,并根据模型特点设计一种改进蚁群算法求解。仿真实验结果表明：与封闭式车辆路径策略相比较,基于开放式车辆路径策略的改进蚁群算法能有效降低生鲜电商的总配送成本,减少车辆使用数量,缩短车辆行驶距离,具有合理性与可行性。     

新型遗传模拟退火算法求解带VRPTW问题

为了克服现有遗传算法不能有效求解时间窗车辆路径问题的缺陷,提出了一种由遗传算法结合模拟退火算法的混合算法求解该问题,并与遗传算法进行了比较。该算法利用了模拟退火算法具有较强的局部搜索能力的特性,有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明,该算法具有计算效率高、收敛速度快和求解质量优的特点,是解决车辆路径问题的有效方法。     

蜂群优化算法在车辆路径问题中的应用

车辆路径问题（VRP）是组合优化中典型的NP难题。根据车辆路径问题的实际情况,考察车辆数和总行程两个目标函数,给出了该问题的一种新的算法,蜂群算法。通过计算若干benchmark问题,并将结果与其他算法相比较与分析,验证了算法的有效性。蜂群算法是刚刚起步的智能优化算法,目前国内外关于蜂群算法的文献较少,故不仅是拓宽蜂群算法的应用范围的有效的尝试,同时也给车辆路径问题提供了一种新的解决方法。     

有软时窗多车场开放式车辆路径及其禁忌搜索

有软时窗约束多车场开放式车辆路径问题是在基本的车辆路径问题上增加了时间窗约束和多车场作业的一种变化形式,是一个典型的NP-难问题。建立了问题模型,运用改进的禁忌搜索算法测试了算例。快速获得的高质量解验证了模型的正确性和算法性能的优良性。     

具有时延约束网络路由问题的自适应蚁群优化算法

高速多媒体网络中的路由问题是有QoS约束的路由问题,满足一个或多个约束的路由问题是NP-完全问题,其中,具有时间延迟约束的QoS路由问题是一个极具代表性的问题。本文给出了一种求解具有时间延迟约束的QoS路由问题的自适应蚁群算法。该算法在种群中采用基于目标函数值的启发式信息素分配策略和根据目标函数自动调整蚂蚁搜索路径的行为。比一般蚁群算法具有更强的鲁棒性和全局优化能力。理论分析和仿真实验表明,该算法是有效的网络QoS路由算法。     

An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods simultaneously. The Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD) differs from the VRPSPD in that the customers may have either pickup or delivery demand. However, the solution approaches proposed for the VRPSPD can be directly applied to the VRPMPD. In this study, an adaptive local search solution approach is developed for both the VRPSPD and the VRPMPD, which hybridizes a Simulated Annealing inspired algorithm with Variable Neighborhood Descent. The algorithm uses an adaptive threshold function that makes the algorithm self-tuning. The proposed approach is tested on well-known VRPSPD and VRPMPD benchmark instances derived from the literature. The computational results indicate that the proposed algorithm is effective in solving the problems in reasonable computation time.     

A hybrid clonal selection algorithm for the location routing problem with stochastic demands

In this paper, a new formulation of the Location Routing Problem with Stochastic Demands is presented. The problem is treated as a two phase problem where in the first phase it is determined which depots will be opened and which customers will be assigned to them while in the second phase, for each of the open depots a Vehicle Routing Problem with Stochastic Demands is solved. For the solution of the problem a Hybrid Clonal Selection Algorithm is applied, where, in the two basic phases of the Clonal Selection Algorithm, a Variable Neighborhood Search algorithm and an Iterated Local Search algorithm respectively have been utilized. As there are no benchmark instances in the literature for this form of the problem, a number of new test instances have been created based on instances of the Capacitated Location Routing Problem. The algorithm is compared with both other variants of the Clonal Selection Algorithm and other evolutionary algorithms.     

A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands

The Glowworm Swarm Optimization (GSO) algorithm is a relatively new swarm intelligence algorithm that simulates the movement of the glowworms in a swarm based on the distance between them and on a luminescent quantity called luciferin. This algorithm has been proven very efficient in the problems that has been applied. However, there is no application of this algorithm, at least to our knowledge, in routing type problems. In this paper, this nature inspired algorithm is used in a hybrid scheme (denoted as Combinatorial Neighborhood Topology Glowworm Swarm Optimization (CNTGSO)) with other metaheuristic algorithms (Variable Neighborhood Search (VNS) algorithm and Path Relinking (PR) algorithm) for successfully solving the Vehicle Routing Problem with Stochastic Demands. The major challenge is to prove that the proposed algorithm could efficiently be applied in a difficult combinatorial optimization problem as most of the applications of the GSO algorithm concern solutions of continuous optimization problems. Thus, two different solution vectors are used, the one in the continuous space (which is updated as in the classic GSO algorithm) and the other in the discrete space and it represents the path representation of the route and is updated using Combinatorial Neighborhood Topology technique. A migration (restart) phase is, also, applied in order to replace not promising solutions and to exchange information between solutions that are in different places in the solution space. Finally, a VNS strategy is used in order to improve each glowworm separately. The algorithm is tested in two problems, the Capacitated Vehicle Routing Problem and the Vehicle Routing Problem with Stochastic Demands in a number of sets of benchmark instances giving competitive and in some instances better results compared to other algorithms from the literature.     

基于免疫遗传算法的物流配送车辆路径优化问题研究

提出一种新的启发式算法-免疫遗传算法,以处理物流配送车辆路径优化问题;并运用一种新的巡回路线编码方法和抗体浓度群体更新及多样性保持策略,在解决物流配送车辆路径优化问题上取得了较显著的效果.     

蚂蚁算法在车辆路径问题中的应用研究

本文将蚂蚁算法这种新型的生物优化思想扩展到物流管理中的车辆路径问题,从数值计算上探索了蚂蚁算法的优化能力,获得了满意的效果.