LIPIcs.MFCS.2018.50.pdf
- Filesize: 473 kB
- 14 pages
Document
Car-Sharing between Two Locations: Online Scheduling with Two Servers
Authors
Kelin Luo 
,
Thomas Erlebach ,
-
Part of:
Volume:
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-27
File
Document Identifiers
Author Details
Cite As Get BibTex
Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing between Two Locations: Online Scheduling with Two Servers. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.50
Abstract
In this paper, we consider an on-line scheduling problem that is motivated by applications such as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using two servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The length of the time interval between the submission of a request (booking time) and the pick-up time is fixed. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted. We present lower bounds on the competitive ratio for this problem and propose a smart greedy algorithm that achieves the best possible competitive ratio.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
Keywords
- Car-sharing system
- Competitive analysis
- On-line scheduling
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Norbert Ascheuer, Sven Oliver Krumke, and Jörg Rambau. Online dial-a-ride problems: Minimizing the completion time. In Horst Reichel and Sophie Tison, editors, STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings, volume 1770 of LNCS, pages 639-650. Springer, 2000. URL: http://dx.doi.org/10.1007/3-540-46541-3_53.
- Gerardo Berbeglia, Jean-François Cordeau, and Gilbert Laporte. Dynamic pickup and delivery problems. European Journal of Operational Research, 202(1):8-15, 2010. URL: http://dx.doi.org/10.1016/j.ejor.2009.04.024.
- Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schlöter, and Leen Stougie. Tight bounds for online TSP on the line. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 994-1005. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.63.
- Katerina Böhmová, Yann Disser, Matús Mihalák, and Rastislav Srámek. Scheduling transfers of resources over time: Towards car-sharing with flexible drop-offs. In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, 12th Latin American Symposium on Theoretical Informatics (LATIN 2016), volume 9644 of LNCS, pages 220-234. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_17.
-
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.
- Ananya Christman, William Forcier, and Aayam Poudel. From theory to practice: maximizing revenues for on-line dial-a-ride. J. Comb. Optim., 35(2):512-529, 2018. URL: http://dx.doi.org/10.1007/s10878-017-0188-z.
- Sven Oliver Krumke, Willem 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 Thomas Erlebach and Giuseppe Persiano, editors, Approximation and Online Algorithms, Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers, volume 3879 of LNCS, pages 258-269. Springer, 2006. URL: http://dx.doi.org/10.1007/11671411_20.
-
Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-sharing between two locations: Online scheduling with flexible advance bookings. In Proceedings of the 24th International Computing and Combinatorics Conference, COCOON 2018, LNCS. Springer, 2018. To appear.
- Fanglei Yi and Lei Tian. On the online dial-a-ride problem with time-windows. In Nimrod Megiddo, Yinfeng Xu, and Binhai Zhu, editors, Algorithmic Applications in Management, First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings, volume 3521 of LNCS, pages 85-94. Springer, 2005. URL: http://dx.doi.org/10.1007/11496199_11.