OASIcs.ATMOS.2017.1.pdf
- Filesize: 0.5 MB
- 15 pages
Document
Revenue Maximization in Online Dial-A-Ride
Authors
-
Part of:
Volume:
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
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: 2017-09-04
Cite As Get BibTex
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). Open Access Series in Informatics (OASIcs), Volume 59, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/OASIcs.ATMOS.2017.1
Abstract
We study a variation of the Online-Dial-a-Ride Problem where each request comes with not only a source, destination and release time, but also has an associated revenue. The server's goal is to maximize its total revenue within a given time limit, T. We show that the competitive ratio is unbounded for any deterministic online algorithm for the problem. We then provide a 3-competitive algorithm for the problem in a uniform metric space and a 6-competitive algorithm for the general case of weighted graphs (under reasonable assumptions about the input instance). We conclude with an experimental evaluation of our algorithm in simulated settings inspired by real-world Dial-a-Ride data. Experimental results show that our algorithm performs well when compared to an offline version of the algorithm and a greedy algorithm.
Subject Classification
Keywords
- online algorithms
- dial-a-ride
- competitive analysis
- vehicle routing
- metric space
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Norbert Ascheuer, Sven O. Krumke, and Jörg Rambau. Online dial-a-ride problems: Minimizing the completion time. In Annual Symposium on Theoretical Aspects of Computer Science, pages 639-650. Springer, 2000.
-
Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, and Maurizio Talamo. Algorithms for the on-line travelling salesman 1. Algorithmica, 29(4):560-581, 2001.
-
Nabila Azi, Michel Gendreau, and Jean-Yves Potvin. A dynamic vehicle routing problem with multiple delivery routes. Annals of Operations Research, 199(1):103-112, 2012.
-
Ananya Christman and William Forcier. Maximizing revenues for on-line dial-a-ride. In International Conference on Combinatorial Optimization and Applications, pages 522-534. Springer, 2014.
- Minnesota City of Plymouth. Plymouth metrolink dial-a-ride. URL: http://www.plymouthmn.gov/departments/administrative-services-/transit/plymouth-metrolink-dial-a-ride.
- Stagecoach Corporation. Dial-a-ride. URL: http://stagecoach-rides.org/dial-a-ride/.
- Metropolitan Council. Transit link: Dial-a-ride small bus service. URL: https://metrocouncil.org/Transportation/Services/Transit-Link.aspx.
-
Esteban Feuerstein and Leen Stougie. On-line single-server dial-a-ride problems. Theoretical Computer Science, 268(1):91-105, 2001.
-
Michel Gendreau, Alain Hertz, and Gilbert Laporte. A tabu search heuristic for the vehicle routing problem. Management Science, 40(10):1276-1290, 1994.
-
Patrick Jaillet and Michael R Wagner. Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses. Operations Research, 56(3):745-757, 2008.
-
Patrick Jaillet and Michael R. Wagner. Online vehicle routing problems: A survey. The Vehicle Routing Problem: Latest Advances and New Challenges, pages 221-237, 2008.
-
Yannick Kergosien, Ch. Lente, D. Piton, and J.-C. Billaut. A tabu search heuristic for the dynamic transportation of patients between care units. European Journal of Operational Research, 214(2):442-452, 2011.
-
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Maarten Lipmann, Alberto Marchetti-Spaccamela, and Leen Stougie. On minimizing the maximum flow time in the online dial-a-ride problem. In International Workshop on Approximation and Online Algorithms, pages 258-269. Springer, 2005.
-
Sandro Lorini, Jean-Yves Potvin, and Nicolas Zufferey. Online vehicle routing and scheduling with dynamic travel times. Computers &Operations Research, 38(7):1086-1090, 2011.
-
Michael Schilde, Karl F. Doerner, and Richard F. Hartl. Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports. Computers &Operations Research, 38(12):1719-1730, 2011.