Maximizing the Number of Rides Served for Dial-a-Ride

Anthony, Barbara M.; Birnbaum, Ricky; Boyd, Sara; Christman, Ananya; Chung, Christine; Davis, Patrick; Dhimar, Jigar; Yuen, David

doi:10.4230/OASIcs.ATMOS.2019.11

File

OASIcs.ATMOS.2019.11.pdf

Filesize: 0.52 MB
15 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2019.11
URN: urn:nbn:de:0030-drops-114237

Author Details

Barbara M. Anthony

Southwestern University, Georgetown TX 78626, USA

Ricky Birnbaum

Connecticut College, New London CT 06320, USA

Sara Boyd

Southwestern University, Georgetown TX 78626, USA

Ananya Christman

Middlebury College, Middlebury VT 05753, USA

Christine Chung

Connecticut College, New London CT 06320, USA

Patrick Davis

Connecticut College, New London CT 06320, USA

Jigar Dhimar

Connecticut College, New London CT 06320, USA

David Yuen

Kapolei HI 96707, USA

Acknowledgements

The authors would like to thank Khanh Nghiem for helpful conversations regarding components of this work.

Cite AsGet 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)

0

PDF Downloads

0

Metadata Views

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.