An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows

November 2006
Transportation Science;Nov2006, Vol. 40 Issue 4, p455
Academic Journal
The pickup and delivery problem with time windows is the problem of serving a number of transportation requests using a limited amount of vehicles. Each request involves moving a number of goods from a pickup location to a delivery location. Our task is to construct routes that visit all locations such that corresponding pickups and deliveries are placed on the same route, and such that a pickup is performed before the corresponding delivery. The routes must also satisfy time window and capacity constraints. This paper presents a heuristic for the problem based on an extension of the large neighborhood search heuristic previously suggested for solving the vehicle routing problem with time windows. The proposed heuristic is composed of a number of competing subheuristics that are used with a frequency corresponding to their historic performance. This general framework is denoted adaptive large neighborhood search. The heuristic is tested on more than 350 benchmark instances with up to 500 requests. It is able to improve the best known solutions from the literature for more than 50% of the problems. The computational experiments indicate that it is advantageous to use several competing subheuristics instead of just one. We believe that the proposed heuristic is very robust and is able to adapt to various instance characteristics.


Related Articles

  • A TABU SEARCH HEURISTIC FOR THE CAPACITATED ARC ROUTING PROBLEM. Hertz, Alain; Laporte, Gilbert; Mittaz, Michel // Operations Research;Jan/Feb2000, Vol. 48 Issue 1, p129 

    The Capacitated Are Routing Problem arises in several contexts where streets or roads must be traversed for maintenance purposes or for the delivery of services. A tabu search is proposed for this difficult problem. On benchmark instances, it outperforms all known heuristics and often produces a...

  • A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Gendreau, Michel; Laporte, Gilbert // Operations Research;May/Jun96, Vol. 44 Issue 3, p469 

    This paper considers a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands. A tabu search heuristic is developed for this problem. Comparisons with known optimal solutions on problems whose sizes vary from 6...

  • Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Bramel, Julien; Simchi-Levi, David // Operations Research;May/Jun96, Vol. 44 Issue 3, p501 

    In the Vehicle Routing Problem with Time Windows, a set of customers are served by a fleet of vehicles of limited capacity, initially located at a central depot. Each customer provides a period of time in which they require service, which may consist of repair work or loading/unloading the...

  • A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows. Tan, K. C.; Chew, Y. H.; Lee, L. H. // Computational Optimization & Applications;May2006, Vol. 34 Issue 1, p115 

    Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as...

  • Heuristics, LPs, and trees on trees: Network design analyses. Balakrishnan, Anantaram; Magnanti, Thomas I. // Operations Research;May/Jun96, Vol. 44 Issue 3, p478 

    We study a class of models, known as overlay optimization problems, composed of "base" and "overlay" subproblems, linked by the requirement that the overlay solution be contained in the base solution. In some telecommunication settings, a feasible base solution is a spanning tree, and the...

  • Models and Tabu Search Metaheuristics for Service Network Design with Asset-Balance Requirements. Pedersen, Michael Berliner; Crainic, Teodor Gabriel; Madsen, Oli B. G. // Transportation Science;May2009, Vol. 43 Issue 2, p158 

    This paper focuses on a generic model for service network design, which includes asset positioning and utilization through constraints on asset availability at terminals. We denote these relations as "design-balance constraints" and focus on the design-balanced capacitated multicommodity network...

  • Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems. Li, Chung-Lun; Simchi-Levi, David // ORSA Journal on Computing;Winter90, Vol. 2 Issue 1, p64 

    We consider the multidepot capacitated vehicle routing problems and analyze the tour partitioning heuristics for different versions of the model. We prove that the worst-case ratios of the heuristics are bounded by some fixed numbers. Examples are provided to show that the worst-case bounds are...

  • A Tabu Search Heuristic for the Vehicle Routing Problem. Gendreau, Michel; Hertz, Alain; Laporte, Gilbert // Management Science;Oct94, Vol. 40 Issue 10, p1276 

    The purpose of this paper is to describe TABUROUTE, a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algorithm considers a sequence of adjacent solutions obtained by repeatedly removing a vertex from its current route and reinserting it...

  • A COMPARISON OF HEURISTIC AND OPTIMUM SOLUTIONS IN RESOURCE-CONSTRAINED PROJECT SCHEDULING. Davis, Edward W.; Patterson, James H. // Management Science;Apr1975, Vol. 21 Issue 8, p944 

    The problem addressed is that of scheduling the activities of a project network to minimize project duration under conditions of multiple limited resource requirements and availabilities. Various heuristic sequencing rules have been applied to this problem, and the effectiveness of these rules...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics