Article ID: | iaor20063511 |
Country: | United States |
Volume: | 16 |
Issue: | 2 |
Start Page Number: | 120 |
End Page Number: | 132 |
Publication Date: | Mar 2004 |
Journal: | INFORMS Journal On Computing |
Authors: | Lenstra Jan Karel, Stougie Leen, Paepe Willem E. de, Sgall Jiri, Sitters Ren A. |
Keywords: | computational analysis, scheduling, queues: theory |
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.