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.     

Exploiting sparsity in pricing routines for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a well-known and fundamental vehicle routing problem. A promising exact solution approach to the CARP is to model it as a set covering problem and solve it via branch-cut-and-price. The bottleneck in this approach is the pricing (column generation) routine. In this paper, we note that most CARP instances arising in practical applications are defined on sparse graphs. We show how to exploit this sparsity to yield faster pricing routines. Extensive computational results are given.     

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.     

A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints

This paper introduces a special vehicle routing problem, i.e. the cumulative capacitated vehicle routing problem with time-window constraints (Cum-CVRPTW). The problem can be defined as designing least-cost delivery routes from a depot to a set of geographically-scattered customers, subject to the constraint that each customer has to be served within a time window; accordingly, the objective costs are computed as the sum of arrival times at all the customers. The Cum-CVRPTW finds practical utility in many situations, e.g. the provision of humanitarian aids in the context of natural disasters. The Cum-CVRPTW can be viewed as a combination of two NP-hard problems, i.e. the vehicle routing problem with time windows and the cumulative vehicle routing problem. To effectively address this problem, an effective algorithm is designed, which is based on the frameworks of Large Neighborhood Search Algorithm and hybridizes with Genetic Algorithm. The proposed algorithm adopts a constraint-relaxation scheme to extend the search space, enabling the iterative exploration of both the feasible and infeasible neighborhood solutions of an incumbent solution. Furthermore, some speed-up techniques are designed to reduce the computational complexity. To elucidate its effectiveness, the proposed algorithm is examined on the benchmark instances from the literature. The resultant numerical findings show that the algorithm is able to improve and obtain some best-known solutions found by existing state-of-the-art methods.     

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.     

Discussion related to “Wang,C.-H., & Lu,J.-Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problem. Expert Systems with Applications, 36(2), 2921–2936”

This paper presents a discussion arisen after reading “A hybrid genetic algorithm that optimizes capacitated vehicle routing problem”, by Wang & Lu, (Wang, C.-H., & Lu, J.-Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert System with Applications, 35, 2921–2936.). The discussed paper presents a hybrid genetic algorithm applied to the Capacitated Vehicle Routing Problem (CVRP). When the authors present the results obtained by the technique, they claim to have overcome the best-known solution in two instances of Christofides and Eilon CVRP Benchmark. This statement can create confusion and controversy, for several reasons that we will explain and clarify in this short communication.     

Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem

This paper presents two solution representations and the corresponding decoding methods for solving the capacitated vehicle routing problem (CVRP) using particle swarm optimization (PSO). The first solution representation (SR-1) is a (n + 2m)-dimensional particle for CVRP with n customers and m vehicles. The decoding method for this representation starts with the transformation of particle into a priority list of customer to enter route and a priority matrix of vehicle to serve each customer. The vehicle routes are then constructed based on the customer priority list and vehicle priority matrix. The second representation (SR-2) is a 3m-dimensional particle. The decoding method for this representation starts with the transformation of particle into the vehicle orientation points and the vehicle coverage radius. The vehicle routes are constructed based on these points and radius. The proposed representations are applied using GLNPSO, a PSO algorithm with multiple social learning structures, and tested using some benchmark problems. The computational result shows that representation SR-2 is better than representation SR-1 and also competitive with other methods for solving CVRP.     

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.     

Solving capacitated arc routing problems using a transformation to the CVRP

A well-known transformation by Pearn, Assad and Golden reduces a capacitated arc routing problem (CARP) into an equivalent capacitated vehicle routing problem (CVRP). However, that transformation is regarded as unpractical, since an original instance with r   required edges is turned into a CVRP over a complete graph with 3r+1$3r+1$ vertices. We propose a similar transformation that reduces this graph to 2r+1$2r+1$ vertices, with the additional restriction that a previously known set of r pairwise disconnected edges must belong to every solution. Using a recent branch-and-cut-and-price algorithm for the CVRP, we observed that it yields an effective way of attacking the CARP, being significantly better than the exact methods created specifically for that problem. Computational experiments obtained improved lower bounds for almost all open instances from the literature. Several such instances could be solved to optimality.     

The rescheduling arc routing problem

In this paper, the rescheduling arc routing problem is introduced. This is a dynamic routing and scheduling problem that considers adjustments to an initial routing itinerary when one or more vehicle failures occur during the execution stage and the original plan must be modified. We minimize the operational and schedule disruption costs. Formulations based on mixed‐integer programming are presented to compare different policies in the rerouting phase. A solution strategy is developed when both costs are evaluated and it is necessary to find a solution quickly. Computational tests on a large set of instances compare the different decision‐maker policies.     

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).     

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.     

Solving the vehicle routing problem with adaptive memory programming methodology

In this paper we develop an adaptive memory programming method for solving the capacitated vehicle routing problem called Solutions’ Elite PArts Search (SEPAS). This iterative method, first generates initial solutions via a systematic diversification technique and stores their routes in an adaptive memory. Subsequently, a constructive heuristic merges route components (called elite parts) from those in the adaptive memory. Finally, a tabu search approach improves the heuristically constructed solution and the adaptive memory is appropriately updated. SEPAS has been tested on two benchmark data sets and provides high quality solutions in short computational times for all problem instances. The method reaches several new best solutions for benchmark instances with a large number of customers.     

A fast two-level variable neighborhood search for the clustered vehicle routing problem

In this paper, we present an improved two-level heuristic to solve the clustered vehicle routing problem (CluVRP). The CluVRP is a generalization of the classical capacitated vehicle routing problem (CVRP) in which customers are grouped into predefined clusters, and all customers in a cluster must be served consecutively by the same vehicle. This paper contributes to the literature in the following ways: (i) new upper bounds are presented for multiple benchmark instances, (ii) good heuristic solutions are provided in much smaller computing times than existing approaches, (iii) the CluVRP is reduced to its cluster level without assuming Euclidean coordinates or distances, and (iv) a new variant of the CluVRP, the CluVRP with weak cluster constraints, is introduced. In this variant, clusters are allocated to vehicles in their entirety, but all corresponding customers can be visited by the vehicle in any order.The proposed heuristic solves the CluVRP by combining two variable neighborhood search algorithms, that explore the solution space at the cluster level and the individual customer level respectively. The algorithm is tested on different benchmark instances from the literature with up to 484 nodes, obtaining high quality solutions while requiring only a limited calculation time.     

A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints

The capacitated vehicle routing problem with three-dimensional loading constraints combines capacitated vehicle routing and three-dimensional loading with additional packing constraints concerning, for example, unloading operations. An efficient hybrid algorithm including a tabu search algorithm for routing and a tree search algorithm for loading is introduced. Computational results are presented for all publicly available test instances. Most of the best solutions previously reported in literature have been improved while the computational effort is drastically reduced compared to other methods.     

An integration of Lagrangian split and VNS: The case of the capacitated vehicle routing problem

In this paper, we propose an efficient and novel Lagrangian relaxation method which incorporates a new integer linear programming (ILP) formulation to optimally partition a giant tour in the context of a capacitated vehicle routing problem (CVRP). This approach, which we call Lagrangian split (Ls), is more versatile than the ILP which, in most cases, can be intractable using a conventional solver. An effective repair mechanism followed by a local search are also embedded into the process. The mathematical validity of the repair mechanism and its time complexity are also provided. An integration of Ls into a powerful variable neighbourhood search (VNS) is also presented. Computational experiments are conducted to demonstrate that Ls provides encouraging results when applied on benchmark instances and that the integration of Ls into a metaheuristic scheme produces good results when compared to those found by state-of-the-art methods.     

有能力约束回收车辆路径问题的食物链算法

介绍了有能力约束逆向物流回收车辆路径问题,设计了求解有能力约束逆向物流回收车辆路径问题的食物链算法;选取文献典型算例进行了仿真求解及比较分析,结果表明设计的食物链算法性能优于遗传算法、粒子群算法和量子进化算法。     

A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries

The vehicle routing problem with simultaneous pick-up and deliveries, which considers simultaneous distribution and collection of goods to/from customers, is an extension of the capacitated vehicle routing problem. There are various real cases, where fleet of vehicles originated in a depot serves customers with pick-up and deliveries from/to their locations. Increasing importance of reverse logistics activities make it necessary to determine efficient and effective vehicle routes for simultaneous pick-up and delivery activities. The vehicle routing problem with simultaneous pick-up and deliveries is also NP-hard as a capacitated vehicle routing problem and this study proposes a genetic algorithm based approach to this problem. Computational example is presented with parameter settings in order to illustrate the proposed approach. Moreover, performance of the proposed approach is evaluated by solving several test problems.     

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.     

Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW

In this work, a novel multi-phase modified shuffled frog leaping algorithm (MPMSFLA) framework is presented to solve the multi-depot vehicle routing problem (MDVRP) more quickly. The presented algorithm adopts the K-means algorithm to execute the clustering analyses for all customers, generates a frog population according to the result of the clustering analyses, and then proceeds to the three-phase process. In the first phase, a cluster MSFLA local search is carried out for each cluster. In the second phase, the algorithm selects good individuals through a binary tournament to construct a new population and then performs a global optimization for all customers and depots using the global MSFLA. In the third phase, a cluster adjustment is implemented for the population to generate new clusters. These procedures continue until the convergence criterion is satisfied. The experimental results show that our algorithm can achieve a high quality solution within a short runtime for the MDVRP, the MDVRP with time windows (MDVRPTW) and the capacitated vehicle routing problem (CVRP). The proposed algorithm is suitable for solving large-scale problems.