Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings

Luo, Kelin; Erlebach, Thomas; Xu, Yinfeng

Abstract

We study an online scheduling problem that is motivated by applications such as car-sharing. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using a single server (car). 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 that precedes the pick-up time. We present lower bounds on the competitive ratio of deterministic and randomized algorithms for both variants and propose a greedy algorithm that achieves the best possible competitive ratio among deterministic algorithms.

Citation

Luo, K., Erlebach, T., & Xu, Y. (2022). Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings. Discrete Applied Mathematics, 313, 53-66. https://doi.org/10.1016/j.dam.2022.01.016

• Journal Article Type: Article
• Acceptance Date: Jan 21, 2022
• Online Publication Date: Mar 11, 2022
• Publication Date: May 31, 2022
• Deposit Date: Feb 27, 2022
• Publicly Available Date: Mar 11, 2023
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 313
• Pages: 53-66
• DOI: https://doi.org/10.1016/j.dam.2022.01.016
• Public URL: https://durham-repository.worktribe.com/output/1213616