Car-Sharing : Online Scheduling k Cars Between Two Locations

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationFrontiers in Algorithmics
Subtitle of host publication14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings
EditorsMinming Li
PublisherSpringer Nature Switzerland AG
Pages49-61
ISBN (Electronic)9783030599010
ISBN (Print)9783030599003
Publication statusPublished - 2020

Publication series

NameLecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
Volume12340
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title14th International Frontiers of Algorithmics Workshop (FAW 2020)
LocationOnline
PlaceChina
CityHaikou
Period19 - 21 October 2020

Abstract

This paper studies a special setting of the online order-dispatching problem in the car-sharing system (CSS). Once an order is released online by a user at its booking time, it specifies the departure time and two locations (in which one is the departure location while the other is the destination). The CSS operator needs to determine whether to accept or reject an online order at its booking time. Once accepting an order, the operator should assign a car among k cars to serve the order right at its departure time, gaining a constant revenue paid by the user. However, a movement without taking an order (i.e., empty movement) incurs a constant cost for the operator. The goal is to schedule the k cars to serve a set of online released orders that maximizes the overall profits (i.e., the overall revenue minus the overall cost generated by accepted orders). With regard to the cost of empty movement and the time gap between an order’s booking time and departure time, we consider different settings. We show the lower bounds on the competitive ratio for different settings respectively, and propose two online algorithms GD and BD, with their competitive ratios matching and approaching the lower bounds in corresponding settings respectively.

Research Area(s)

  • Car-sharing system, Online algorithm, Online scheduling

Citation Format(s)

Car-Sharing : Online Scheduling k Cars Between Two Locations. / Li, Songhua; Zheng, Leqian; Lee, Victor C. S.

Frontiers in Algorithmics: 14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings. ed. / Minming Li. Springer Nature Switzerland AG, 2020. p. 49-61 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 12340).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review