OASIcs.ATMOS.2019.11.pdf
- Filesize: 0.52 MB
- 15 pages
Document
Maximizing the Number of Rides Served for Dial-a-Ride
Authors
Barbara M. Anthony 
,
Ananya Christman ,
Christine Chung ,
-
Part of:
Volume:
19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-11-15
File
Document Identifiers
Author Details
Acknowledgements
The authors would like to thank Khanh Nghiem for helpful conversations regarding components of this work.
Cite As Get BibTex
Barbara M. Anthony, Sara Boyd, Ricky Birnbaum, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen. Maximizing the Number of Rides Served for Dial-a-Ride. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.ATMOS.2019.11
Abstract
We study a variation of offline Dial-a-Ride, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NP-hard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.
Subject Classification
ACM Subject Classification
- Theory of computation → Routing and network design problems
Keywords
- dial-a-ride
- revenue maximization
- approximation algorithm
- vehicle routing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Giorgio Ausiello, Vincenzo Bonifaci, and Luigi Laura. The online prize-collecting traveling salesman problem. Information Processing Letters, 107(6):199-204, 2008.
-
Baruch Awerbuch, Yossi Azar, Avrim Blum, and Santosh Vempala. New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing, 28(1):254-262, 1998.
-
Egon Balas. The prize collecting traveling salesman problem. Networks, 19(6):621-636, 1989.
-
Daniel Bienstock, Michel X Goemans, David Simchi-Levi, and David Williamson. A note on the prize collecting traveling salesman problem. Mathematical programming, 59(1-3):413-420, 1993.
-
Avrim Blum, Shuchi Chawla, David R Karger, Terran Lane, Adam Meyerson, and Maria Minkoff. Approximation algorithms for orienteering and discounted-reward TSP. SIAM Journal on Computing, 37(2):653-670, 2007.
- Ananya Christman, Christine Chung, Nicholas Jaczko, Marina Milan, Anna Vasilchenko, and Scott Westvold. Revenue Maximization in Online Dial-A-Ride. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59, pages 1:1-1:15, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.1.
-
Ananya Christman, William Forcier, and Aayam Poudel. From theory to practice: maximizing revenues for on-line dial-a-ride. Journal of Combinatorial Optimization, 35(2):512-529, 2018.
- Jean-François Cordeau and Gilbert Laporte. The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1):29-46, September 2007. URL: https://doi.org/10.1007/s10479-007-0170-8.
-
Yves Molenbruch, Kris Braekers, and An Caris. Typology and literature review for dial-a-ride problems. Annals of Operations Research, 259(1):295-325, 2017.
-
Christos H Papadimitriou and Umesh V Vazirani. On two geometric problems related to the travelling salesman problem. Journal of Algorithms, 5(2):231-246, 1984.
- stackexchange.com. Is the longest trail problem easier than the longest path problem? https://cstheory.stackexchange.com/questions/20682/is-the-longest-trail-problem-easier-than-the-longest-path-problem. Accessed: 2019-02-19.