Computer-aided complexity classification of dial-a-ride problem

Computer-aided complexity classification of dial-a-ride problem

0.00 Avg rating0 Votes
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: , , , ,
Keywords: computational analysis, scheduling, queues: theory
Abstract:

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.

Reviews

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