MODELS AND PROCEDURES FOR THE PICK-UP AND DELIVERY PROBLEM (VEHICLE ROUTING DYNAMIC PROGRAMMING HEURISTICS)

This research involves developing models and procedures for the Pick-up and Delivery problem (PDP). The Pick-up and Delivery problem is a special case of the Vehicle Routing problem and can be defined as follows. There exist N tasks to be performed by a fleet of vehicles. Each task consists of picking-up a certain amount of goods from its supply node and transporting these to its associated demand node. The pro to perform these N tasks so that a certain objective is optimized. The key characteristics of the PDP are the precedence relations in visiting the supply-demand nodes and fluctuations in the vehicle capacity usage during the course of the tour.;The lower bounds obtained are implemented in a branch and bound procedure. The algorithm is able to solve an eigh single vehicle problem optimally. By dualizing one of the PDP constraints and solving the resulting program by a Lagrangian ascent procedure, better quality lower bounds are obtained. This permits twelve task, single vehicle problems to be solved optimally.;In the multiple vehicle case, an identical vehicle task-limited problem is analyzed. This problem is transformed into a single vehicle problem and solved by the branch and bound procedure developed for the single vehicle case. Up to fifteen task problems are solved with this procedure. The generalization of this approach to other multiple vehicle problems is also suggested.;Several heuristics, including the Greedy and the Insertion procedures, are analysed and specialized for the PDP. The information obtained through the solution of the lower bounding problems is utilized in a greedy approach. The exact branch and bound procedure is also implemented as a heuristic. Computational tests with random test problems suggests that good quality solutions can be obtained by the branch and bound based heuristic procedures, at the expense of additional computational effort.;Two linear binary models which incorporate the special PDP characteristics are developed. The first model is for the single vehicle problem. This model is extended to the multiple vehicle case. The relaxation of certain constraints in the PDP model yields lower bounds for the optimal solution. These lower bounding problems are solved by dynamic programming.