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 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.
Keywords for this software
References in zbMATH (referenced in 8 articles )
Showing results 1 to 8 of 8.
- Ilani, Hagai; Shufan, Elad; Grinshpoun, Tal; Belulu, Aviad; Fainberg, Alex: A reduction approach to the two-campus transport problem (2014)
- Maalouf, Maher; MacKenzie, Cameron A.; Radakrishnan, Sridhar; Court, Mary: A new fuzzy logic approach to capacitated dynamic dial-a-ride problem (2014)
- Averbakh, Igor: Emergency path restoration problems (2012)
- Yu, Wei; Liu, Zhaohui: Vehicle routing problems on a line-shaped network with release time constraints (2009)
- Coene, Sofie; Spieksma, Frits C.R.: Profit-based latency problems on the line (2008)
- Krumke, Sven O.; de Paepe, Willem E.; Poensgen, Diana; Lipmann, Maarten; Marchetti-Spaccamela, Alberto; Stougie, Leen: On minimizing the maximum flow time in the online dial-a-ride problem (2006)
- De Paepe, Willem E.; Lenstra, Jan Karel; Sgall, Jiri; Sitters, René A.; Stougie, Leen: Computer-aided complexity classification of dial-a-ride problems (2004)
- Feuerstein, E.; Stougie, L.: On-line single-server dial-a-ride problems (2001)