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 17 articles )

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

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