A new tabu search algorithm for the vehicle routing problem with backhauls

In the distribution of goods from a central depot to geographically dispersed customers happens quite frequently that some customers, called linehauls, receive goods from that depot while others, named backhauls, send goods to it. This situation is described and studied by the vehicle routing problem with backhauls. In this paper we present a new tabu search algorithm that starting from pseudo-lower bounds was able to match almost all the best published solutions and to find many new best solutions, for a large set of benchmark problems.     

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.     

A reactive tabu search for the vehicle routing problem

The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems.     

A deterministic iterated local search algorithm for the vehicle routing problem with backhauls

The vehicle routing problem with backhauls is a variant of the classical capacitated vehicle routing problem. The difference is that it contains two distinct sets of customers: those who receive goods from the depot, who are called linehauls, and those who send goods to the depot, who are referred to as backhauls. In this paper, we describe a new deterministic iterated local search algorithm, which is tested using a large number of benchmark problems chosen from the literature. These computational tests have proven that this algorithm competes with the best known algorithms in terms of the quality of the solutions and at the same time, it is simpler and faster.     

An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls

This paper presents the case study of an Italian carrier, Grendi Trasporti Marittimi, which provides freight transportation services by trucks and containers. Its trucks deliver container loads from a port to import customers and collect container loads from export customers to the same port. In this case study, all import customers in a route must be serviced before all export customers, each customer can be visited more than once and containers are never unloaded or reloaded from the truck chassis along any route. We model the problem using an Integer Linear Programming formulation and propose an Adaptive Guidance metaheuristic. Our extensive computational experiments show that the adaptive guidance algorithm is capable of determining good-quality solutions in many instances of practical or potential interest for the carrier within 10?min of computing time, whereas the mathematical formulation often fails to provide the first feasible solution within 3?h of computing time.     

A new tabu search heuristic for the open vehicle routing problem

In this paper, another version of the vehicle routing problem (VRP)—the open vehicle routing problem (OVRP) is studied, in which the vehicles are not required to return to the depot, but if they do, it must be by revisiting the customers assigned to them in the reverse order. By exploiting the special structure of this type of problem, we present a new tabu search heuristic for finding the routes that minimize two objectives while satisfying three constraints. The computational results are provided and compared with two other methods in the literature.     

A tabu search algorithm for the single vehicle routing allocation problem

In the single vehicle routing allocation problem (SVRAP) we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem. In this paper, we present a tabu search algorithm for the SVRAP. Our tabu search algorithm includes aspiration, path relinking and frequency-based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others.     

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.     

A tabu search algorithm for the multi-trip vehicle routing and scheduling problem

This paper describes a novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers' schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.     

An incremental tabu search heuristic for the generalized vehicle routing problem with time windows

This paper describes an incremental neighbourhood tabu search heuristic for the generalized vehicle routing problem with time windows. The purpose of this work is to offer a general tool that can be successfully applied to a wide variety of specific problems. The algorithm builds upon a previously developed tabu search heuristic by replacing its neighbourhood structure. The new neighbourhood is exponential in size, but the proposed evaluation procedure has polynomial complexity. Computational results are presented and demonstrate the effectiveness of the approach.     

Erratum: A new tabu search heuristic for the open vehicle routing problem

Correction to: Journal of the Operational Research Society (2005) 56, 267–274. doi:10.1057/palgrave.jors.2601817     

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.     

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.     

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.     

A simple and efficient tabu search heuristic for solving the open vehicle routing problem

The open vehicle routing problem (VRP) is an immediate variant of the standard vehicle routing problem where the vehicle need not return to the depot after servicing its last customer. In this paper, we present results on an implementation of the attribute-based hill climber heuristic to the open VRP. The attribute-based hill climber heuristic is a parameter-free variant of the tabu search principle and has shown to be highly effective for the standard vehicle routing problem.     

A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars

The purpose of this article is to propose a tabu search heuristic for the split delivery Vehicle Routing Problem with Production and Demand Calendars (VRPPDC). This new problem consists of determining which customers will be served by a common carrier, as well as the delivery routes for those served by the private fleet, in order to minimize the overall transportation and inventory costs. We first model this problem and then propose a simple decomposition procedure that can be used to provide a starting solution. Next, we introduce a new tabu search heuristic and we describe two new neighbor reduction strategies. Finally, we present the results of our extensive computational tests. According to these tests, our reduction strategies are efficient not only at reducing computing time but also at improving the overall solution quality.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

An adaptive memory algorithm for the split delivery vehicle routing problem

The split delivery vehicle routing problem (SDVRP) relaxes routing restrictions forcing unique deliveries to customers and allows multiple vehicles to satisfy customer demand. Split deliveries are used to reduce total fleet cost to meet those customer demands. We provide a detailed survey of the SDVRP literature and define a new constructive algorithm for the SDVRP based on a novel concept called the route angle control measure. We extend this constructive approach to an iterative approach using adaptive memory concepts, and then add a variable neighborhood descent process. These three new approaches are compared to exact and heuristic approaches by solving the available SDVRP benchmark problem sets. Our approaches are found to compare favorably with existing approaches and we find 16 new best solutions for a recent 21 problem benchmark set.     

Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls

Recently, an increasing number of papers on vehicle routing problems with backhauling has been published. Different types of backhauling problems are discussed. Two of them—the vehicle routing problem with backhauls and so-called ‘mixed loads’ (VRPBM) and the vehicle routing problem with simultaneous delivery and pick-up (VRPSDP)—are closely related. In this paper, we discuss that relationship. Our findings are that previously published results for VRPSDP instances obtained by using a heuristic suggested for the VRPBM do not take into account specific properties of the VRPSDP. As a result of the analysis of the relation between both problem types the possibility of solving the VRPBM by applying an insertion heuristic based on the concept of ‘residual capacities’ originally designed for the VRPSDP is investigated. Numerical results indicate that, for certain instances, this approach is more favourable than the application of a heuristic suggested for the VRPBM in the literature.