License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.64
URN: urn:nbn:de:0030-drops-100122
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10012/
Luo, Kelin ;
Erlebach, Thomas ;
Xu, Yinfeng
Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings
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.
BibTeX - Entry
@InProceedings{luo_et_al:LIPIcs:2018:10012,
author = {Kelin Luo and Thomas Erlebach and Yinfeng Xu},
title = {{Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {64:1--64:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10012},
URN = {urn:nbn:de:0030-drops-100122},
doi = {10.4230/LIPIcs.ISAAC.2018.64},
annote = {Keywords: Car-sharing system, Competitive analysis, On-line scheduling}
}
|
Keywords: |
|
Car-sharing system, Competitive analysis, On-line scheduling |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
