The single and multiple vehicle pickup and delivery problem : exact and heuistic algorithms

The TSP and VRP literature is extensive, offering both theory and algorithms for the solution of these problems. Given the similarities of these problems to the PUDP, those algorithms that performed well on TSP's and VRP's are discussed in detail and served as the basis for developing both exact and heuristic algorithms to solve the PUDP.

Assuming that all problem constraints arc expressible in terms of stop numbers along a vehicle's route, dynamic programming can be used to optimally solve the problem. The algorithm developed is significantly more powerful on heavily constrained problem instances than any other known technique. Solutions to problems in excess of 45 customers (equivalent to a 91 city TSP] are solved on an IBM 3031 computer in a matter of seconds. The efficiency is achieved by only generating feasible state space vectors, thus greatly reducing the storage and execution requirements. The same dynamic programming algorithm is also used to solve the multiple vehicle PUDP but with less impressive results. Other exact techniques could not be effectively used on the PUDP due primarily to the precedence requirement.

Heuristic algorithms were also developed and tested. Most of the algorithms commonly used to solve the related TSP and PUDP perform poorly on the PUDP, often producing solutions as much as 50% above optimal. An interchange (3-optimal) heuristic consistently produced superior results for the single vehicle PUDP. Solutions averaging within 1% of optimal were obtained for heavily constrained problem instances.

The multiple vehicle problem is significantly more complex than is the single vehicle problem. Results for the multiple vehicle problem were acceptable but inconclusive. Consequently, the multiple vehicle area is judged to be the most promising area for future research.