Combinatorially simple pickup and delivery paths

Combinatorially simple pickup and delivery paths

0.00 Avg rating0 Votes
Article ID: iaor2009325
Country: Germany
Volume: 12
Issue: 4
Start Page Number: 405
End Page Number: 417
Publication Date: Dec 2004
Journal: Central European Journal of Operations Research
Authors:
Keywords: programming: travelling salesman, networks: path
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.

Reviews

Required fields are marked *. Your email address will not be published.