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.     

Heuristic methods for vehicle routing problem with time windows

This paper documents our investigation into various heuristic methods to solve the vehicle routing problem with time windows (VRPTW) to near optimal solutions. The objective of the VRPTW is to serve a number of customers within predefined time windows at minimum cost (in terms of distance travelled), without violating the capacity and total trip time constraints for each vehicle. Combinatorial optimisation problems of this kind are non-polynomial-hard (NP-hard) and are best solved by heuristics. The heuristics we are exploring here are mainly third-generation artificial intelligent (AI) algorithms, namely simulated annealing (SA), Tabu search (TS) and genetic algorithm (GA). Based on the original SA theory proposed by Kirkpatrick and the work by Thangiah, we update the cooling scheme and develop a fast and efficient SA heuristic. One of the variants of Glover's TS, strict Tabu, is evaluated and first used for VRPTW, with the help of both recency and frequency measures. Our GA implementation, unlike Thangiah's genetic sectoring heuristic, uses intuitive integer string representation and incorporates several new crossover operations and other advanced techniques such as hybrid hill-climbing and adaptive mutation scheme. We applied each of the heuristics developed to Solomon's 56 VRPTW 100-customer instances, and yielded 18 solutions better than or equivalent to the best solution ever published for these problems. This paper is also among the first to document the implementation of all the three advanced AI methods for VRPTW, together with their comprehensive results.     

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%.     

An iterated local search heuristic for the split delivery vehicle routing problem

This paper concerns the Split Delivery Vehicle Routing Problem (SDVRP). This problem is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) since the customers׳ demands are allowed to be split. We deal with the cases where the fleet is unlimited (SDVRP-UF) and limited (SDVRP-LF). In order to solve them, we implemented a multi-start Iterated Local Search (ILS) based heuristic that includes a novel perturbation mechanism. Extensive computational experiments were carried out on benchmark instances available in the literature. The results obtained are highly competitive, more precisely, 55 best known solutions were equaled and new improved solutions were found for 243 out of 324 instances, with an average and maximum improvement of 1.15% and 2.81%, respectively.     

Adaptive granular local search heuristic for a dynamic vehicle routing problem

The advance of communication and information technologies based on satellite and wireless networks have allowed transportation companies to benefit from real-time information for dynamic vehicle routing with time windows. During daily operations, we consider the case in which customers can place requests such that their demand and location are stochastic variables. The time windows at customer locations can be violated although lateness costs are incurred. The objective is to define a set of vehicle routes which are dynamically updated to accommodate new customers in order to maximize the expected profit. This is the difference between the total revenue and the sum of lateness costs and costs associated with the total distance traveled. The solution approach makes use of a new constructive heuristic that scatters vehicles in the service area and an adaptive granular local search procedure. The strategies of letting a vehicle wait, positioning a vehicle in a region where customers are likely to appear, and diverting a vehicle away from its current destination are integrated within a granular local search heuristic. The performance of the proposed approach is assessed in test problems based on real-life Brazilian transportation companies.     

求解需求可拆分车辆路径问题的改进的金字塔演化策略

为了更加合理地求解需求可拆分的车辆路径问题（SDVRP）,克服传统先路径后优化两阶段的求解方法容易陷入局部最优的缺点,以及解决智能优化算法在优化阶段未能将竞争与协作有机地融合为一体的问题,以配送路径最短和配送车辆最少为优化目标,提出了一种改进的金字塔演化策略（IPES）。首先,以金字塔为基础,提出了求解SDVRP的编码、解码方式以及层级间的协作策略;其次,根据遗传算法的随机、“适者生存”的高度并行、自适应等特点,以及金字塔结构各层分工不同,设计了一种适合SDVRP的自适应邻域算子,使得算法能够快速收敛到最优;最后,得到最优解。相较于分段求解算法、聚类算法、粒子群算法、人工蜂群算法、禁忌搜索算法,四个仿真实验的结果表明,在求解各案例的最优路径时,所提IPES的求解精度分别至少提升了0.92%、0.35%、3.07%、9.40%,验证了在求解SDVRP时,IPES具有良好的性能。     

Implementation techniques for the vehicle routing problem

Six methods for implementing the widely used Clarke-Wright algorithm for the vehicle routing problem (VRP) are presented and compared. Fifty-five large test problems are used to compare the methods. The methods involve alternative ways to access adjacency information in both low and high density problems. The results clearly establish methods of choice for VRP problems with given characteristics.     

A heuristic for the vehicle routing problem with due times

This paper studies the vehicle routing problem with due times. The vehicles are supposed to visit customers within the due times, and a penalty cost is imposed in case the vehicle arrives past the due times. The objective is to minimize the weighted sum of the traveling time of vehicles and the tardiness of the service customers receive. A mixed integer programming formulation and a heuristic based on the tabu search for a practical use are suggested. Route-perturb and route-improvement method for the neighborhood generation is proposed. Performances are compared with other heuristics appeared in the literature using the bench-mark data set modified to be fit to the model. It is shown that the suggested heuristic gives a good solution in a short computation time.     

A cooperative parallel metaheuristic for the capacitated vehicle routing problem

This paper introduces a cooperative parallel metaheuristic for the capacitated vehicle routing problem. The proposed metaheuristic consists of multiple parallel tabu search threads that cooperate by asynchronously exchanging best-found solutions through a common solution pool. The solutions sent to the pool are clustered according to their similarities. The search history information identified from the solution clusters is applied to guide the intensification or diversification of the tabu search threads. Computational experiments on two sets of large-scale benchmark instance sets from the literature demonstrate that the suggested metaheuristic is highly competitive, providing new best solutions to ten of those well-studied instances.     

A matheuristic for the MinMax capacitated open vehicle routing problem

In this paper, the MinMax‐COVRP (where COVRP is capacitated open vehicle routing problem) is considered as a variation of the COVRP where the objective is to minimize the duration of the longest route. For the purpose of producing high‐quality solutions, elements from the fields of mathematical programming and metaheuristics are combined, resulting in a matheuristic for solving the MinMax‐COVRP. The matheuristic benefits from the diversification produced by a metaheuristic and the intensification from mixed‐integer linear programming (MILP). The initial solution provided by a multistart heuristic is used to seed and accelerate the MILP in which a local branching framework and the separation of k‐path inequalities are suitably combined. Computational experience shows promising results not only improving the initial solution provided by the multistart algorithm, but also ensuring optimality for most of the small‐ and medium‐sized instances.     

A generalized exchange heuristic for the capacitated vehicle routing problem

We consider the problem of dispatching the minimum number of vehicles from a central depot to make deliveries to a set of clients with known demands. The objective is to minimize the total distance travelled, subject to vehicle capacity requirements. We present a new heuristic algorithm for solving this problem. The algorithm is based on generalized edge-exchange search procedures, and relaxation of the capacity requirements. Computational results, based upon standard test problems with up to 249 customers, indicate that our heuristic compares favourably with known heuristics in terms of solution quality.     

求解车辆路径问题的一种混合方法

提出一种求解带软时间窗车辆路径问题的混合算法。采用蚁群系统算法产生阶段最优解,以此作为粒子模板,随机生成粒子群,利用粒子群算法在阶段最优解基础上进一步优化。且在蚁群系统算法中,当容量超过限制后,从剩余的客户里选择需求量最大的作为新的起点继续探索路径,直到所有客户都被访问一遍。实验表明,该混合算法是解决带软时间窗车辆路径问题的一个有效算法。     

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 iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows

The Multi-Commodity Multi-Trip Vehicle Routing Problem with Time Windows calls for the determination of a routing planning to serve a set of customers that require products belonging to incompatible commodities. Two commodities are incompatible if they cannot be transported together into the same vehicle. Vehicles are allowed to perform several trips during the working day. The objective is to minimize the number of used vehicles.We propose an Iterated Local Search that outperforms the previous algorithm designed for the problem. Moreover, we conduct an analysis on the benefit that can be obtained introducing the multi-trip aspect at the fleet dimensioning level. Results on classical VRPTW instances show that, in some cases, the fleet can be halved.     

Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem

This paper proposes a hybrid approach for solving the multidepot vehicle routing problem (MDVRP) with a limited number of identical vehicles per depot. Our approach, which only uses a few parameters, combines “biased randomization”—use of nonsymmetric probability distributions to generate randomness—with the iterated local search (ILS) metaheuristic. Two biased‐randomized processes are employed at different stages of the ILS framework in order to (a) assign customers to depots following a randomized priority criterion—this allows for fast generation of alternative allocation maps and (b) improving routing solutions associated with a “promising” allocation map—this is done by randomizing the classical savings heuristic. These biased‐randomized processes rely on the use of the geometric probability distribution, which is characterized by a single and bounded parameter. Being an approach with few parameters, our algorithm does not require troublesome fine‐tuning processes, which tend to be time consuming. Using standard benchmarks, the computational experiments show the efficiency of the proposed algorithm. Despite its hybrid nature, our approach is relatively easy to implement and can be parallelized in a very natural way, which makes it an interesting alternative for practical applications of the MDVRP.     

A branch-and-price approach for a multi-period vehicle routing problem

In this paper, we consider tactical planning for a class of multi-period vehicle routing problems (MPVRP). This problem involves optimizing daily product collections from several production locations over a given planning horizon. In this context, a single routing plan for the whole horizon must be prepared, and the seasonal variations in the producers’ supplies must be taken into account. Production variations over the horizon are approximated using a sequence of periods, each corresponding to a production season, while the intra-period variations are neglected. We propose a mathematical model that is based on the two-stage a priori optimization paradigm. The first stage corresponds to the design of a plan which, in the second stage, takes the different periods into account. The proposed set partitioning-based formulation is solved using a branch-and-price approach. The subproblem is a multi-period elementary shortest path problem with resource constraints (MPESPPRC), for which we propose an adaptation of the dynamic-programming-based label-correcting algorithm. Computational results show that this approach is able to solve instances with up to 60 producers and five periods.     

一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法。     

Efficient local search on the GPU—Investigations on the vehicle routing problem

We study how to implement local search efficiently on data parallel accelerators such as Graphics Processing Units. The Distance-constrained Capacitated Vehicle Routing Problem, a computationally very hard discrete optimization problem with high industrial relevance, is the selected vehicle for our investigations. More precisely, we investigate local search with the Best Improving strategy for the 2-opt and 3-opt operators on a giant tour representation. Resource extension functions are used for constant time move evaluation. Using CUDA, a basic implementation called The Benchmark Version has been developed and deployed on a Fermi architecture Graphics Processing Unit. Both neighborhood setup and evaluation are performed entirely on the device. The Benchmark Version is the initial step of an incremental improvement process where a number of important implementation aspects have been systematically studied. Ten well-known test instances from the literature are used in computational experiments, and profiling tools are used to identify bottlenecks. In the final version, the device is fully saturated, given a large enough problem instance. A speedup of almost an order of magnitude relative to The Benchmark Version is observed. We conclude that, with some effort, local search may be implemented very efficiently on Graphics Processing Units. Our experiments show that a maximum efficiency, however, requires a neighborhood cardinality of at least one million. Full exploration of a billion neighbors takes a few seconds and may be deemed too expensive with the current technology. Reduced neighborhoods through filtering is an obvious remedy. Experiments on simple models of neighborhood filtering indicate, however, that the speedup effect is limited on data parallel accelerators. We believe these insights are valuable in the design of new metaheuristics that fully utilize modern, heterogeneous processors.