Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

An effective tabu search approach with improved loading algorithms for the 3L-CVRP

In this paper, we consider the Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines the routing of a fleet of vehicles and the loading of three-dimensional shaped goods into the vehicles while minimizing the total travel distance incurred. Apparently, 3L-CVRP is a combination of capacitated vehicle routing and three-dimensional bin packing problem and thus of high complexity. Different from most of previous works, we propose an innovative approach, called improved least waste heuristic for solving the loading subproblem, which is iteratively invoked by a simple tabu search algorithm for the routing. The good performance in terms of the solution quality and computational efficiency of our approach is shown through the numerical experiments on the benchmark instances from literature.     

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

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

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.     

An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a variation of the classical capacitated vehicle routing problem in which the objective is the minimization of the sum of arrival times at customers, instead of the total routing cost. This paper presents an adaptive large neighborhood search heuristic for the CCVRP. This algorithm is applied to a set of benchmark instances and compared with two recently published memetic algorithms.     

A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem

This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.     

平衡装载约束下的车辆路径问题研究

针对车辆三维装载约束下的车辆路径问题（3L-VRP）进行研究,引进车辆的平衡装载约束,综合考虑传统的先进后出、局部支撑、脆弱性等约束,构建平衡装载约束下的车辆路径问题（BL-VRP）模型。针对模型中的平衡约束,提出一种接触面积的装载算法。在此基础上,构建以回溯遗传算法（B-GA）为骨架的多阶段算法框架,对车辆路径优化进行求解。研究结果表明,多阶段算法不仅在解决3L-VRP上好于目前已有算法,同时对BL-VRP表现优秀。提出的多阶段算法为解决BL-VRP问题提供一条参考思路,但在时效性上需要进一步完善。     

Genetic algorithm with iterated local search for solving a location-routing problem

This paper deals with a location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. We seek for new methods to make location and routing decisions simultaneously and efficiently. For that purpose, we describe a genetic algorithm (GA) combined with an iterative local search (ILS). The main idea behind our hybridization is to improve the solutions generated by the GA using a ILS to intensify the search space. Numerical experiments show that our hybrid algorithm improves, for all instances, the best known solutions previously obtained by the tabu search heuristic.     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

考虑动态平衡装卸的点对点取送货车辆路径优化

针对点对点取送货车辆路径优化问题,引入动态平衡、后进先出、三维装载等约束,以总路径最短为优化目标,构建多车多客户应用场景下的动态平衡装卸点对点取送货车辆路径优化模型;基于研究问题的特征,采用启发式插入法确定路径初始方案,设计节点交换和重新定位算子,构造路径邻域方案,并将动态平衡装卸纳入路径迭代过程,运用多重指标定序策略和三分空间策略,设计客户动态平衡装卸检算算法,并提出基于禁忌搜索的点对点取送货车辆路径优化算法,制订多车多客户取送货车辆路径方案的同时编制动态平衡装载方案。最后,通过标准算例验证方法的有效性,计算表明：所提方法能高效解决带动态平衡约束的点对点取送货车辆路径优化问题;在多车多客户应用场景下具有更强的寻优能力,求解效率更高。     

带装载量约束的物流配送车辆路径优化研究

建立了物流配送车辆路径模型,设计了一种禁忌搜索算法,进行了多个算例测试和比较。测试表明模型的正确性,显示出禁忌搜索算法在物流配送车辆路径优化中计算时间节省、路程里程节省、总费用最小化等方面比遗传算法、模拟退火算法、蚁群算法及其混合算法具有明显的优势,能很好地适应现代物流对配送环节快速、低成本的要求。     

An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers. The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

Active-guided evolution strategies for large-scale capacitated vehicle routing problems

We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 70 test instances.     

Active guided evolution strategies for large-scale vehicle routing problems with time windows

We present a new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows. The algorithm combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. More precisely, guided local search is used to regulate a composite local search in the first stage and the neighborhood of the evolution strategies algorithm in the second stage. The vehicle routing problem with time windows is a classical problem in operations research, where the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified time windows. The presented algorithm is specifically designed for large-scale problems. The computational experiments were carried out on an extended set of 302 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 86% of all test instances within reasonable computing times. The power of the algorithm is confirmed by the results obtained on 23 capacitated vehicle routing problems from the literature.     

垃圾分类收运路径问题的新型混合蚁群算法求解

针对垃圾分类收运路径问题,考虑车辆装载容量约束、硬时间窗约束、装载率对成本的影响等条件下,以最小化运输成本和车辆固定成本为目标建立了数学模型。将考虑时间吻合度因子和车容量利用率因子的改进蚁群算法与混沌电磁场优化算法进行动态融合,并结合2-opt和两点交换的局部搜索方法,提出一种以改进蚁群算法为外部框架,混沌电磁场优化算法为内部模块的新型混合蚁群算法对城市生活垃圾分类收运问题进行求解。根据算法间优势互补的思想,利用两种算法的优点来弥补单个算法的缺陷,使其成功应用于该问题。最后,用车辆路径问题标准测试集和上海市杨浦区的数据作为实例进行测试与对比,验证了模型的正确性以及算法的有效性与优化能力。     

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.     

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

带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解.为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出相对较优解.研究了求解带容量和时间窗约束车辆路径问题的改进离散蝙蝠算法,为增加扰动机制,提高搜索速度和精度,在对客户点按其所在位置进行聚类的基础上,在算法中引入了变步长搜索策略和两元素优化方法进行局部搜索.仿真实验结果表明,所设计算法具有较高寻优能力和较强的实用价值.     

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.