Solving the Precedence Constrained Vehicle Routing Problem with Time Windows Using the Reactive Tabu Search Metastrategy.

Abstract

The vehicle routing problem (VRP) is associated with the design of a set of minimum cost routes for a fleet of vehicles to serve, exactly once, a set of customers with known demands. The pickup and delivery problem with time windows (PDPTW) is a generalization of the VRP. The PDPTW constructs optimal routes to satisfy transportation requests, each requiring both pickup and delivery under capacity, time window, precedence and coupling constraints. This dissertation presents a reactive tabu search (RTS) approach to solve the PDPTW and illustrated how to transform generalized precedence constrained routing problems with time windows (PCRPTW) into equivalent PDPTWs.

The PDPTW algorithm uses three distinct search neighborhoods that capitalize on the dominance of the precedence and coupling constraints. The algorithm employs a multineighborhood strategic search methodology, to alternate between search neighborhoods in order to negotiate different regions of the solution space and alter directions of search. All tours generated by the search require that supplies and the corresponding deliveries e located on the same route and ordered properly. Because RTS explores infeasible solutions, it can discover time window or load infeasible solutions having significantly lower objective values than optimal.

This dissertation also establishes benchmark data sets for the PDPTW through the modification of the input data structure for Solomon's 1987 benchmark VRPTW data sets. Computational results substantiate the solution quality and efficiency of the PDPTW algorithm when compared against one heuristic and two exact VRPTW algorithms.

Finally, the dissertation demonstrates how to transform representative generalized-PCRPTWs into PDPTWs. Modifications to the input data structure are presented and example problems are used to display the transformations.

Download Nanry's Dissertation