License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.64
URN: urn:nbn:de:0030-drops-100122
URL: https://drops.dagstuhl.de/opus/volltexte/2018/10012/
Go to the corresponding LIPIcs Volume Portal


Luo, Kelin ; Erlebach, Thomas ; Xu, Yinfeng

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

pdf-format:
LIPIcs-ISAAC-2018-64.pdf (0.5 MB)


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
Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 27.11.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI