Combinatorially Simple Pickup and Delivery Paths

Abstract

Pickup and delivery problems discussed in the literature are often constrained to particularly simple solutions in terms of the sequence of visited locations. We study the very simplest pickup and delivery paths which are concatenations of short patterns visiting one or two requests. This restricted variant, still NP-hard, is close to the traveling salesman problem with the additional choice of what patterns to visit. We compare the number of restricted and unrestricted paths, and evaluate their respective path lengths. We conclude with two polynomially solvable cases. [PUBLICATION ABSTRACT]