Computer-Aided Complexity Classification of Dial-a-Ride Problems

In dial-a-ride problems, items have to be transported from a source to a destination. The characteristics of the servers involved as well as the specific requirements of the rides may vary. Problems are defined on some metric space, and the goal is to find a feasible solution that minimizes a certai...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2004-05, Vol.16 (2), p.120-132
Main Authors: de Paepe, Willem E, Lenstra, Jan Karel, Sgall, Jiri, Sitters, Rene A, Stougie, Leen
Format: Article
Language:English
Subjects:
Algorithms
computational complexity
dial-a-ride
Mathematical models
Optimization
Routing
Studies
vehicle routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In dial-a-ride problems, items have to be transported from a source to a destination. The characteristics of the servers involved as well as the specific requirements of the rides may vary. Problems are defined on some metric space, and the goal is to find a feasible solution that minimizes a certain objective function. The structure of these problems allows for a notation similar to the standard notation for scheduling and queueing problems. We introduce such a notation and show how a class of 7,930 dial-a-ride problem types arises from this approach. In examining their computational complexity, we define a partial ordering on the problem class and incorporate it in the computer program DARCLASS. As input DARCLASS uses lists of problems whose complexity is known. The output is a classification of all problems into one of three complexity classes: solvable in polynomial time, NP-hard, or open. For a selection of the problems that form the input for DARCLASS, we exhibit a proof of polynomial-time solvability or NP-hardness.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1030.0052