Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings

Authors Kelin Luo , Thomas Erlebach , Yinfeng Xu



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.64.pdf
  • Filesize: 472 kB
  • 13 pages

Document Identifiers

Author Details

Kelin Luo
  • School of Management, Xi'an Jiaotong University, Xi'an, China
Thomas Erlebach
  • Department of Informatics, University of Leicester, Leicester, United Kingdom
Yinfeng Xu
  • School of Management, Xi'an Jiaotong University, Xi'an, China

Cite AsGet BibTex

Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.64

Abstract

We study 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 k 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 scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). We consider two variants of the problem with respect to constraints on the booking time: In the fixed booking time variant, a request must be submitted a fixed amount of time before the pick-up time. In the variable booking time variant, a request can be submitted at any time during a certain time interval (called the booking horizon) that precedes the pick-up time. We present lower bounds on the competitive ratio for both variants and propose a balanced greedy algorithm (BGA) that achieves the best possible competitive ratio. We prove that, for the fixed booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the fixed booking length is not less than the travel time between the two locations; for the variable booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the length of the booking horizon is less than the travel time between the two locations, and BGA is 5/3-competitive if k=5i ( i in N) and the length of the booking horizon is not less than the travel time between the two locations.

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)
    0
    PDF Downloads

References

  1. Norbert Ascheuer, Sven Oliver Krumke, and Jörg Rambau. Online Dial-a-Ride Problems: Minimizing the Completion Time. In Proc. of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS '00), volume 1770 of LNCS, pages 639-650. Springer, 2000. URL: http://dx.doi.org/10.1007/3-540-46541-3_53.
  2. 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 Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '17), pages 994-1005. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.63.
  3. 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 Proc. of the 12th Latin American Symposium on Theoretical Informatics (LATIN'16), volume 9644 of LNCS, pages 220-234. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_17.
  4. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  5. 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.
  6. 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 Proc. of the 3rd International Workshop on Approximation and Online Algorithms (WAOA 2005), Revised Papers, volume 3879 of LNCS, pages 258-269. Springer, 2006. URL: http://dx.doi.org/10.1007/11671411_20.
  7. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings. In Proc. of the 24th International Computing and Combinatorics Conference (COCOON '18), 2018. To appear. Google Scholar
  8. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing between Two Locations: Online Scheduling with two Servers. In Proc. of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS '18), 117. LIPIcs, 2018. To appear. URL: http://www.cs.le.ac.uk/~te17/papers/mfcs2018.pdf.
  9. Fanglei Yi and Lei Tian. On the Online Dial-A-Ride Problem with Time-Windows. In Proc. of the 1st International Conference on Algorithmic Applications in Management (AAIM '05), volume 3521 of LNCS, pages 85-94. Springer, 2005. URL: http://dx.doi.org/10.1007/11496199_11.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail