A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem

The fleet size and mix vehicle routing problem consists of defining the type, the number of vehicles of each type, as well as the order in which to serve the customers with each vehicle when a company has to distribute goods to a set of customers geographically spread, with the objective of minimizing the total costs. In this paper, a heuristic algorithm based on tabu search is proposed and tested on several 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.     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.     

The multi-depot vehicle routing problem with inter-depot routes

This article addresses an extension of the multi-depot vehicle routing problem in which vehicles may be replenished at intermediate depots along their route. It proposes a heuristic combining the adaptative memory principle, a tabu search method for the solution of subproblems, and integer programming. Tests are conducted on randomly generated instances.     

Scatter search for the fleet size and mix vehicle routing problem with time windows

This work proposes a scatter search (SS) approach to solve the fleet size and mix vehicle routing problem with time windows (FSMVRPTW). In the FSMVRPTW the customers need to be serviced in their time windows at minimal costs by a heterogeneous fleet. Computational results on 168 benchmark problems are reported. Computational testing revealed that our algorithm presented better results compared to other methods published in the literature.     

A tabu search heuristic for the vehicle routing problem with private fleet and common carrier

This paper describes a tabu search heuristic for a vehicle routing problem where the owner of a private fleet can either visit a customer with one of his vehicles or assign the customer to a common carrier. The owner’s objective is to minimize the variable and fixed costs for operating his fleet plus the total costs charged by the common carrier. The proposed tabu search is shown to outperform the best approach reported in the literature on 34 benchmark instances with a homogeneous fleet.     

An iterated local search algorithm for the time-dependent vehicle routing problem with time windows

We generalize the standard vehicle routing problem with time windows by allowing both traveling times and traveling costs to be time-dependent functions. In our algorithm, we use a local search to determine routes of the vehicles. When we evaluate a neighborhood solution, we must compute an optimal time schedule for each route. We show that this subproblem can be efficiently solved by dynamic programming, which is incorporated in the local search algorithm. The neighborhood of our local search consists of slight modifications of the standard neighborhoods called 2- opt^*, cross exchange and Or-opt. We propose an algorithm that evaluates solutions in these neighborhoods more efficiently than the ones computing the dynamic programming from scratch by utilizing the information from the past dynamic programming recursion used to evaluate the current solution. We further propose a filtering method that restricts the search space in the neighborhoods to avoid many solutions having no prospect of improvement. We then develop an iterated local search algorithm that incorporates all the above ingredients. Finally we report computational results of our iterated local search algorithm compared against existing methods, and confirm the effectiveness of the restriction of the neighborhoods and the benefits of the proposed generalization.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

A sweep-based algorithm for the fleet size and mix vehicle routing problem

This paper presents a new sweep-based heuristic for the fleet size and mix vehicle routing problem. This problem involves two kinds of decisions: the selection of a mix of vehicles among the available vehicle types and the routing of the selected fleet. The proposed algorithm first generates a large number of routes that are serviced by one or two vehicles. The selection of routes and vehicles to be used is then made by solving to optimality, in polynomial time, a set-partitioning problem having a special structure. Results on a set of benchmark test problems show that the proposed heuristic produces excellent solutions in short computing times. Having a fast but good solution method is needed for transportation companies that rent a significant part of their fleet and consequently can take advantage of frequent changes in fleet composition. Finally, the proposed heuristic produced new best-known solutions for three of the test problems; these solutions are reported.     

Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns

We study the routing of a single vehicle that delivers multiple products under stochastic demand. Specifically, we investigate two practical variations of this problem: (i) The case in which each product type is stored in its dedicated compartment in the vehicle, and (ii) the case in which all products are stored together in the vehicle’s single compartment. Suitable dynamic programming algorithms are proposed to determine the minimum expected (routing) cost for each case. Furthermore, the optimal routing policy is derived by developing appropriate theorems. The efficiency of the algorithms is studied by solving large problem sets.     

A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

An iterated local search algorithm for the vehicle routing problem with convex time penalty functions

We propose an iterated local search algorithm for the vehicle routing problem with time window constraints. We treat the time window constraint for each customer as a penalty function, and assume that it is convex and piecewise linear. Given an order of customers each vehicle to visit, dynamic programming (DP) is used to determine the optimal start time to serve the customers so that the total time penalty is minimized. This DP algorithm is then incorporated in the iterated local search algorithm to efficiently evaluate solutions in various neighborhoods. The amortized time complexity of evaluating a solution in the neighborhoods is a logarithmic order of the input size (i.e., the total number of linear pieces that define the penalty functions). Computational comparisons on benchmark instances with up to 1000 customers show that the proposed method is quite effective, especially for large instances.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

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.     

An iterated local search algorithm for the vehicle routing problem with backhauls

The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a broad neighborhood structure at each iteration. This is efficiently done using a data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible portions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. These results show that the performance of existing metaheuristic algorithms can be considerably improved by carrying out a thorough statistical analysis of their components. In particular, it shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained.     

EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem

This paper presents EVE-OPT, a Hybrid Algorithm based on Genetic Algorithms and Taboo Search for solving the Capacitated Vehicle Routing Problem. Several hybrid algorithms have been proposed in recent years for solving this problem. Despite good results, they usually make use of highly problem-dependent neighbourhoods and complex genetic operators. This makes their application to real instances difficult, as a number of additional constraints need to be considered. The algorithm described here hybridizes two very simple heuristics and introduces a new genetic operator, the Chain Mutation, as well as a new mutation scheme. We also apply a procedure, the k-chain-moves, able to increase the neighbourhood size, thereby improving the quality of the solution with negligible computational effort. Despite its simplicity, EVE-OPT is able to achieve the same results as very complex state-of-the art algorithms.     

Recent advances in vehicle routing exact algorithms

The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. This paper provides a review of the most recent developments that had a major impact in the current state-of-the-art of exact algorithms for the CVRP. The most important mathematical formulations for the problem together with various CVRP relaxations are reviewed. The paper also describes the recent exact methods for the CVRP and reports a comparison of their computational performances.      

Lasso solution strategies for the vehicle routing problem with pickups and deliveries

This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing a pickup when delivering at a customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked up from the first visited customers. These customers are revisited in reverse order, thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times on the same route, giving rise to a general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution on the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost, their computation can be time consuming. The best lasso solution generated within a given time limit is generally better than the best general solution produced with the same computing effort.     

A heuristic for the routing and carrier selection problem

We consider the problem of simultaneously selecting customers to be served by external carriers and routing a heterogeneous internal fleet. Very little attention was devoted to this problem. A recent paper proposed a heuristic solution procedure. Our paper shows that better results can be obtained by a simple method and corrects some erroneous results presented in the previous paper.     

A powerful route minimization heuristic for the vehicle routing problem with time windows

We suggest an efficient route minimization heuristic for the vehicle routing problem with time windows. The heuristic is based on the ejection pool, powerful insertion and guided local search strategies. Experimental results on the Gehring and Homberger’s benchmarks demonstrate that our algorithm outperforms previous approaches and found 18 new best-known solutions.