Car-sharing between two locations: online scheduling with flexible advance bookings

Kelin Luo, Thomas Erlebach, Yinfeng Xu

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

8 Citaten (Scopus)
1 Downloads (Pure)


We study an on-line 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 for both variants and propose a greedy algorithm that achieves the best possible competitive ratio.
Originele taal-2Engels
TitelComputing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
RedacteurenDaming Zhu, Lusheng Wang
Plaats van productieCham
Aantal pagina's13
ISBN van elektronische versie978-3-319-94776-1
ISBN van geprinte versie978-3-319-94775-4
StatusGepubliceerd - 2018
Extern gepubliceerdJa

Publicatie series

NaamLecture Notes in Computer Science

Citeer dit