The Single and Multiple Vehicle Pickup and Delivery Problem: Exact and Heuristic Algorithms

摘要

The pickup and delivery problem (PUDP) represents a class of sequencing or routing problems where the key facet of the routing is that a pickup must precede the corresponding, subsequent delivery. Other considerations such as service time windows, quality of service parameters or operational constraints on either the driver or the vehicle are possible. As such, the PUDP is a constrained version of the ubiquitous travelling salesman problem (TSP), which seeks a minimum cost route that from an initial point visits each city or stop once and only once, ending at the initial stop. There are also similarities between the PUDP and the much studied vehicle routing problem (VRP), although the two problems are distinctly different because of the origin preceding destination requirement.