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 11 articles )
Showing results 1 to 11 of 11.
- Bock, Stefan: Finding optimal tour schedules on transportation paths under extended time window constraints (2016)
- Gao, Qiang; Lu, Xiwen: The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail (2016)
- Bock, Stefan: Solving the traveling repairman problem on a line with general processing times and deadlines (2015)
- 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) ioport
- 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)