An adaptive tabu search heuristic for the location routing pickup and delivery problem with time windows with a theater distribution application

The time constrained pickup and delivery problem (PDPTW) is a problem of finding a set of routes for a fleet of vehicles in order to satisfy a set of transportation requests. Each request represents a user-specified pickup and delivery location. The PDPTW may be used to model many problems in logistics and public transportation. The location routing problem (LRP) is an extension of the vehicle routing problem where the solution identifies the optimal location of the depots and provides the vehicle schedules and distribution routes.; This dissertation seeks to blend the PDPTW and LRP areas of research and formulate a location scheduling pickup and delivery problem with time windows (LPDPTW) in order to model the theater distribution problem and find excellent solutions. This research utilizes advanced tabu search techniques, including reactive tabu search and group theory applications, to develop a heuristic procedure for solving the LPDPTW. Tabu search is a metaheuristic that performs an intelligent search of the solution space. Group theory provides the structural foundation that supports the efficient search of the neighborhoods and movement through the solution space.; This research evaluates the robustness of the developed adaptive tabu search algorithm. A linear program is developed to calculate lower bounds for the generated problem objectives.