Decomposition-based multi-objective evolutionary algorithm for vehicle routing problem with stochastic demands

Vehicle routing problem with stochastic demands (VRPSD) is a famous and challenging optimization problem which is similar to many real world problems. To resemble the real world scenario, total traveling distance, total driver remuneration, the number of vehicles used and the difference between driver remuneration are considered and formulated in the multi-objective optimization perspective. This paper aims to solve multi-objective VRPSD under the constraints of available time window and vehicle capacity using decomposition-based multi-objective evolutionary algorithm (MOEA/D) with diversity-loss-based selection method incorporates with local search and multi-mode mutation heuristics. We have also compared the optimization performance of the decomposition-based approach with the domination-based approach to study the difference between these two well-known evolutionary multi-objective algorithm frameworks. The simulation results have showed that the decomposition-based approach with diversity-loss-based selection method is able to maintain diverse output solutions.     

An ant colony algorithm for the multi-compartment vehicle routing problem

We demonstrate the use of Ant Colony System (ACS) to solve the capacitated vehicle routing problem associated with collection of recycling waste from households, treated as nodes in a spatial network. For networks where the nodes are concentrated in separate clusters, the use of k-means clustering can greatly improve the efficiency of the solution. The ACS algorithm is extended to model the use of multi-compartment vehicles with kerbside sorting of waste into separate compartments for glass, paper, etc. The algorithm produces high-quality solutions for two-compartment test problems.     

带时间窗车辆路径问题的多目标文化基因算法

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.     

An effective memetic algorithm for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a transportation problem which occurs when the objective is to minimize the sum of arrival times at customers, instead of the classical route length, subject to vehicle capacity constraints. This type of challenges arises whenever priority is given to the satisfaction of the customer need, e.g. vital goods supply or rescue after a natural disaster. The CCVRP generalizes the NP-hard traveling repairman problem (TRP), by adding capacity constraints and a homogeneous vehicle fleet. This paper presents the first upper and lower bounding procedures for this new problem. The lower bounds are derived from CCVRP properties. Upper bounds are given by a memetic algorithm using non-trivial evaluations of cost variations in the local search. Good results are obtained not only on the CCVRP, but also on the special case of the TRP, outperforming the only TRP metaheuristic published.     

Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands

In this paper, we develop a paired cooperative reoptimization (PCR) strategy to solve the vehicle routing problem with stochastic demands (VRPSD). The strategy can realize reoptimization policy under cooperation between a pair of vehicles, and it can be applied in the multivehicle situation. The PCR repeatedly triggers communication and partitioning to update the vehicle assignments given real-time customer demands. We present a bilevel Markov decision process to model the coordination of a pair of vehicles under the PCR strategy. We also propose a heuristic that dynamically alters the visiting sequence and the vehicle assignment given updated information. We compare our approach with a recent cooperation strategy in the literature. The results reveal that our PCR strategy performs better, with a cost saving of around 20–30%. Moreover, embedding communication can save an average of 1.22%, and applying our partitioning method rather than an alternative can save an average of 3.96%.     

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

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

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.     

粒子群算法求解需求随机的分批配送VRP

对需求随机的分批配送车辆路径问题进行研究,建立带修正的随机规划模型。设计与局部搜索算法相结合的粒子群算法进行求解,算法使用整数编码和基于Bellman方程的允许分割需求的解码方法。并针对允许分批配送时导致的粒子速度、粒子自身最优位置、局部最优位置及全局最优位置等向量非零元素个数不同的问题,设计可行的统一向量长度的方法。算法在调整的Solomon算例测试集和调整的Christiansen和Lysgaard算例测试集上进行测算,测试有效参数、速度长度及速度更新方程。同时与现有结果进行对比,虽然计算效率较低,但在测试的26个算例中,有14个算例的最优解得到更新,剩余的算例最优解与现有最优解相差小于1%。     

Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows

This paper presents an adaptive memetic algorithm to solve the vehicle routing problem with time windows (VRPTW). It is a well-known NP-hard discrete optimization problem with two objectives—to minimize the number of vehicles serving a set of geographically dispersed customers, and to minimize the total distance traveled in the routing plan. Although memetic algorithms have been proven to be extremely efficient in solving the VRPTW, their main drawback is an unclear tuning of their numerous parameters. Here, we introduce the adaptive memetic algorithm (AMA-VRPTW) for minimizing the total travel distance. In AMA-VRPTW, a population of solutions evolves with time. The parameters of the algorithm, including the selection scheme, population size and the number of child solutions generated for each pair of parents, are adjusted dynamically during the search. We propose a new adaptive selection scheme to balance the exploration and exploitation of the solution space. Extensive experimental study performed on the well-known Solomon’s and Gehring and Homberger’s benchmark sets confirms the efficacy and convergence capabilities of the proposed AMA-VRPTW. We show that it is very competitive compared with other state-of-the-art techniques. Finally, the influence of the proposed adaptive schemes on the AMA-VRPTW behavior and performance is investigated in a thorough sensitivity analysis. This analysis is complemented with the two-tailed Wilcoxon test for verifying the statistical significance of the results.     

双重信息引导的蚁群算法求解绿色多舱车辆路径问题

针对当前实际运输中广泛存在的绿色多舱车辆路径问题(GMCVRP), 文章提出一种双重信息引导的蚁群优化算法(DIACO)进行求解. 首先, 在DIACO的全局搜索阶段, 重新构建传统蚁群优化算法(TACO)中的信息素浓度矩阵(PCM), 使其同时包含客户块信息和客户序列信息, 即建立具有双重信息的PCM(DIPCM), 从而更全面学习和累积优质解的信息; 采用3种启发式方法生成较高质量个体, 用于初始化DIPCM, 可快速引导算法朝向解空间中优质区域进行搜索. 其次, 在DIACO的局部搜索阶段, 设计结合自适应策略的多种变邻域操作, 用于对解空间的优质区域执行深入搜索. 再次, 提出信息素浓度平衡机制, 以防止搜索陷入停滞. 最后, 使用不同规模的算例进行仿真测试和算法对比, 结果验证了DIACO是求解GMCVRP的有效算法.     

The capacitated vehicle routing problem with stochastic demands and time windows

The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach.     

A self-adaptive memeplexes robust search scheme for solving stochastic demands vehicle routing problem

In this article, we proposed a self-adaptive memeplex robust search (SAMRS) for finding robust and reliable solutions that are less sensitive to stochastic behaviours of customer demands and have low probability of route failures, respectively, in vehicle routing problem with stochastic demands (VRPSD). In particular, the contribution of this article is three-fold. First, the proposed SAMRS employs the robust solution search scheme (RS ³) as an approximation of the computationally intensive Monte Carlo simulation, thus reducing the computation cost of fitness evaluation in VRPSD, while directing the search towards robust and reliable solutions. Furthermore, a self-adaptive individual learning based on the conceptual modelling of memeplex is introduced in the SAMRS. Finally, SAMRS incorporates a gene-meme co-evolution model with genetic and memetic representation to effectively manage the search for solutions in VRPSD. Extensive experimental results are then presented for benchmark problems to demonstrate that the proposed SAMRS serves as an efficable means of generating high-quality robust and reliable solutions in VRPSD.     

A memetic approach to vehicle routing problem with dynamic requests

The paper presents an effective algorithm for solving Vehicle Routing Problem with Dynamic Requests based on memetic algorithms. The proposed method is applied to a widely-used set of 21 benchmark problems yielding 14 new best-know results when using the same numbers of fitness function evaluations as the comparative methods. Apart from encouraging numerical outcomes, the main contribution of the paper is investigation into the importance of the so-called starting delay parameter, whose appropriate selection has a crucial impact on the quality of results. Another key factor in accomplishing high quality results is attributed to the proposed effective mechanism of knowledge transfer between partial solutions developed in consecutive time slices. While particular problem encoding and memetic local optimization scheme were already presented in the literature, the novelty of this work lies in their innovative combination into one synergetic system as well as their application to a different problem than in the original works.     

带时间窗的同时取送货车辆路径问题建模及模因求解算法

为解决逆向物流背景下的带时间窗的同时取送货车辆路径问题（VRPSPDTW）,根据实际情况建立了相应的车辆路径问题模型,并采用模因算法进行求解。在模型的求解过程中使用引导弹射搜索（GES）生成初始种群,在种群进化的过程中采用边界组合交叉（EAX）产生子代,并采用多种邻域结构对子代进行修复、教育,以提高解的质量和算法的搜索效率。通过在Wang和Chen测试数据集上与遗传算法（GA）、并行模拟退火（p-SA）算法、离散布谷鸟（DCS）算法进行比较,实验结果显示：在小规模算例进行求解时,所提算法全部取得了当前最优解;对标准规模算例进行求解时,所提算法使70%的算例更新或获取了当前最优解,获得的最优求解算例结果与当前最优解相比有超过5%的提升,充分验证了所提算法求解VRPSPDTW的良好性能。     

An iterated tabu search for the multi-compartment vehicle routing problem

We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into a iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it to results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.     

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。     

需求点随机的分批配送VRP模型与算法研究

针对城市配送中需求点不确定的现象, 在分批配送车辆路径问题中引入随机需求点进行研究.建立带修正的随机规划模型, 采用先验优化策略, 根据分批配送的特点, 在自适应大邻域搜索算法中引入改进的分割插入算子进行求解.在调整的Solomon算例上进行的测试表明, 允许分批配送在大部分算例中的费用低于不允许分批配送的情形.通过分析计算过程中各个算子权重变化, 确定性最差删除算子和随机删除算子在求解此类问题时表现较好; 贪婪插入算子、后悔插入算子表现较好; 而分割插入算子虽然权重较低, 但能对解产生质的影响.