Skip to main content

Research Repository

Advanced Search

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

Luo, Kelin; Erlebach, Thomas; Xu, Yinfeng

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


Authors

Kelin Luo

Yinfeng Xu



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
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 313
Pages 53-66
DOI https://doi.org/10.1016/j.dam.2022.01.016

Files





You might also like



Downloadable Citations