Pick-Up and Delivery Problem: Models and Single Vehicle Exact Procedures,
Abstract
The pick-up and delivery problem (PDP) is a special case of the vehicle routing problem and can be defined as follows. There exists 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. The problem is to perform these N tasks to that a certain objective is optimized. The key characteristics of the PDP are the precedence relations in visiting the supply-demand nodes and fluctuation in vehicle capacity usage during the course of the tour. Two linear binary models which incorporate the special PDP characteristics are presented. 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 single vehicle PDP model yields lower bounds for the optical solution. These lower bounding problems are solved by dynamic programming. The lower bounds obtained are implemented in a branch and bound procedure. The algorithm is able to solve an eight task, 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1985
- Accession Number
- ADA168175
Entities
People
- John J. Jarvis
- Omer Kirca
Organizations
- Georgia Tech