Heuristics for multi-attribute vehicle routing problems: A survey and synthesis

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.     

Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism

We present a self-adaptive and distributed metaheuristic called Coalition-Based Metaheuristic (CBM). This method is based on the Agent Metaheuristic Framework (AMF) and hyper-heuristic approach. In CBM, several agents, grouped in a coalition, concurrently explore the search space of a given problem instance. Each agent modifies a solution with a set of operators. The selection of these operators is determined by heuristic rules dynamically adapted by individual and collective learning mechanisms. The intention of this study is to exploit AMF and hyper-heuristic approaches to conceive an efficient, flexible and modular metaheuristic. AMF provides a generic model of metaheuristic that encourages modularity, and hyper-heuristic approach gives some guidelines to design flexible search methods. The performance of CBM is assessed by computational experiments on the vehicle routing problem.     

Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows

This paper presents operators searching large neighborhoods in order to solve the vehicle routing problem. They make use of the pruning and propagation techniques of constraint programming which allow an efficient search of such neighborhoods. The advantages of using a large neighborhood are not only the increased probability of finding a better solution at each iteration but also the reduction of the need to invoke specially-designed methods to avoid local minima. These operators are combined in a variable neighborhood descent in order to take advantage of the different neighborhood structures they generate.     

Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

ARMMS: Analogical reasoning model management system for multicriteria vehicle scheduling

The transportation industry problem of scheduling vehicles combines the spatial characteristics of routing with time domain considerations of activity schedules. The problem is complex because of the numerous interacting constraints in the spatial and time domains. Further, some of the constraints are flexible and some arise in real-time. The scheduling problem is often presented with multiple objectives that are not all economic in nature and which can be contradictory to one another. In response to these needs, this paper describes an analogical reasoning model management system, called ARMMS, designed in the domain of vehicle scheduling. ARMMS consists of knowledge bases and data bases, a truth maintenance system, a user interface, an inference engine, a learning mechanism, and a model library. Given a scheduling problem, ARMMS searches its memory for solutions. If no solution is available, ARMMS falls back on an analogical problem solving approach in which similar experience can be recalled, and solutions to new, but similar, problems can be constructed. If no similar experience exists, ARMMS intelligently selects an appropriate algorithmic model from its model library, based on the input parameters and problem type, to solve the given problem. By combining experts' knowledge, analogical problem-solving approaches, and algorithmic methods, ARMMS provides an efficient problem-solving approach for vehicle scheduling and routing. ARMMS is also a feasible base for the development of intelligent model management systems.     

A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows

We propose a new population-based hybrid meta-heuristic for the periodic vehicle routing problem with time windows. This meta-heuristic is a generational genetic algorithm that uses two neighborhood-based meta-heuristics to optimize offspring. Local search methods have previously been proposed to enhance the fitness of offspring generated by crossover operators. In the proposed method, neighborhood-based meta-heuristics are used for their capacity to escape local optima, and deliver optimized and diversified solutions to the population of the next generation. Furthermore, the search performed by the neighborhood-based meta-heuristics repairs most of the constraint violations that naturally occur after the application of the crossover operators. The genetic algorithm we propose introduces two new crossover operators addressing the periodic vehicle routing problem with time windows. The two crossover operators are seeking the diversification of the exploration in the solution space from solution recombination, while simultaneously aiming not to destroy information about routes in the population as computing routes is NP-hard. Extensive numerical experiments and comparisons with all methods proposed in the literature show that the proposed methodology is highly competitive, providing new best solutions for a number of large instances.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

Target aiming Pareto search and its application to the vehicle routing problem with route balancing

In this paper, we present a solution method for a bi-objective vehicle routing problem, called the vehicle routing problem with route balancing (VRPRB), in which the total length and balance of the route lengths are the objectives under consideration. The method, called Target Aiming Pareto Search, is defined to hybridize a multi-objective genetic algorithm for the VRPRB using local searches. The method is based on repeated local searches with their own appropriate goals. We also propose an implementation of the Target Aiming Pareto Search using tabu searches, which are efficient meta-heuristics for the vehicle routing problem. Assessments with standard metrics on classical benchmarks demonstrate the importance of hybridization as well as the efficiency of the Target Aiming Pareto Search.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

An evolutionary algorithm for the vehicle routing problem with route balancing

In this paper, we address a bi-objective vehicle routing problem in which the total length of routes is minimized as well as the balance of routes, i.e. the difference between the maximal route length and the minimal route length. We propose a meta-heuristic method based on an evolutionary algorithm involving classical multi-objective operators. To improve its efficiency, two mechanisms, which favor the diversification of the search, have been added. First, an elitist diversification mechanism is used in cooperation with classical diversification methodologies. Second, a parallel model designed to take into account the elitist diversification is proposed. Our method is tested on standard benchmarks for the vehicle routing problem. The contribution of the introduced mechanisms is evaluated by different performance metrics. All the experimentations indicate a strict improvement of the generated Pareto set.     

A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem

The heterogeneous fleet vehicle routing problem is investigated using some adaptations of the variable neighborhood search (VNS). The initial solution is obtained by Dijkstra’s algorithm based on a cost network constructed by the sweep algorithm and the 2-opt. Our VNS algorithm uses several neighborhoods which are adapted for this problem. In addition, a number of local search methods together with a diversification procedure are used. Two VNS variants, which differ in the order the diversification and Dijkstra’s algorithm are used, are implemented. Both variants appear to be competitive and produce new best results when tested on the data sets from the literature. We also constructed larger data sets for which benchmarking results are provided for future comparison.     

Routing vehicles to minimize fuel consumption

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.     

A two-phase tabu search approach to the location routing problem

In many distribution systems, the location of the distribution facilities and the routing of the vehicles from these facilities are interdependent. Although this interdependence has been recognized by academics and practitioners alike, attempts to integrate these two decisions have been limited. The location routing problem (LRP), which combines the facility location and the vehicle routing decisions, is NP-hard. Due to the problem complexity, simultaneous solution methods are limited to heuristics. This paper presents a two-phase tabu search architecture for the solution of the LRP. First introduced in this paper, the two-phase approach offers a computationally efficient strategy that integrates facility location and routing decisions. This two-phase architecture makes it possible to search the solution space efficiently, thus producing good solutions without excessive computation. An extensive computational study shows that the TS algorithm achieves significant improvement over a recent effective LRP heuristic.     

成品油配送多车舱车辆指派及路径优化问题研究

针对成品油配送中多车型、多车舱的车辆优化调度难题,综合考虑多车型车辆指派、多车舱车辆装载及路径安排等决策,以派车成本与油耗成本之和的总成本最小为目标,建立了多车型多车舱的车辆优化调度模型。为降低模型求解的复杂性,本文提出一种基于C-W节约算法的“需求拆分→合并装载”的车辆装载策略,并综合利用Relocate和Exchange算子进行并行邻域搜索改进,获得优化的成品油配送方案。最后,通过算例验证了本文提出的模型与算法用于求解大规模成品油配送问题的有效性。并通过数据实验揭示了以下规律:1)多车舱车辆相对于单车舱车辆在运营成本上具有优越性;2)大型车辆适合远距离配送,小型车辆适合近距离配送;3)多车型车辆混合配送相对于单车型车辆配送在运营成本上具有优越性。这些规律可为成品油配送公司的车辆配置提供决策参考。     

Research on the vehicle routing problem with interval demands

In this paper, a vehicle routing problem with interval demands is investigated based on the motivation of dispatching vehicles to deliver perishable products in practice. A nonlinear interval-based programming method is used to build a model for the vehicle routing problem with interval demands, which assumes that demands of customers are uncertain but fall in given intervals and actual demand of a customer becomes known only when the vehicle visited the customer. A vehicle-coordinated strategy was designed to solve the service failure problem. A hybrid algorithm based on the artificial immune system is also proposed to solve the model for vehicle routing problem with interval demands. The validity of methods and sensitivity analysis are illustrated by conducting some numerical examples. We find that the tolerant possibility degree of interval number has significant impacts on the distances. The planned distance strictly increased, while the additional distance strictly decreased and the total distance after coordinated transport has a U-typed relationship with the tolerant possibility degree of interval number.     

A library of local search heuristics for the vehicle routing problem

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.     

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.