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

摘要

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 illustrates how to transform generalized precedence constrained routing problems with time windows (PCRPTW) into equivalent PDPTWs.