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.

References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Christman, Ananya; Forcier, William; Poudel, Aayam: From theory to practice: maximizing revenues for on-line dial-a-ride (2018)
  2. Stephan, Konrad; Boysen, Nils: Crane scheduling in railway yards: an analysis of computational complexity (2017)
  3. Bock, Stefan: Finding optimal tour schedules on transportation paths under extended time window constraints (2016)
  4. Gao, Qiang; Lu, Xiwen: The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail (2016)
  5. Bock, Stefan: Solving the traveling repairman problem on a line with general processing times and deadlines (2015)
  6. Ilani, Hagai; Shufan, Elad; Grinshpoun, Tal; Belulu, Aviad; Fainberg, Alex: A reduction approach to the two-campus transport problem (2014)
  7. Maalouf, Maher; MacKenzie, Cameron A.; Radakrishnan, Sridhar; Court, Mary: A new fuzzy logic approach to capacitated dynamic dial-a-ride problem (2014) ioport
  8. Averbakh, Igor: Emergency path restoration problems (2012)
  9. Yu, Wei; Liu, Zhaohui: Vehicle routing problems on a line-shaped network with release time constraints (2009)
  10. Coene, Sofie; Spieksma, Frits C.R.: Profit-based latency problems on the line (2008)
  11. 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)
  12. De Paepe, Willem E.; Lenstra, Jan Karel; Sgall, Jiri; Sitters, René A.; Stougie, Leen: Computer-aided complexity classification of dial-a-ride problems (2004)
  13. Feuerstein, E.; Stougie, L.: On-line single-server dial-a-ride problems (2001)