Solving the pickup and delivery problem with time windows using reactive tabu search

The pickup and delivery problem with time windows requires that a group of vehicles satisfy a collection of customer requests. Each customer request r equires the use of a single vehicle both to load a specified amount of good s at one location and to deliver them to another location. All requests mus t be performed without violating either the vehicle capacity or the custome r time window stipulated at each location. In this paper, we present a reac tive tabu search approach to solve the pickup and delivery problem with tim e windows using three distinct move neighborhoods that capitalize on the do minance of the precedence and coupling constraints. A hierarchical search m ethodology is used to dynamically alternate between neighborhoods in order to negotiate different regions of the solution space and adjust search traj ectories. In order to validate our technique's effectiveness, we have const ructed a new set of benchmark problems for the pickup and delivery problem with time windows based on Solomon's benchmark vehicle routing problem with time windows data sets, Computational results substantiate the solution qu ality and efficiency of our reactive tabu search approach. (C) 2000 Elsevie r Science Ltd. All rights reserved.