Online scheduling of car-sharing request pairs between two locations
- PDF / 659,633 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 207 Views
Online scheduling of car-sharing request pairs between two locations Kelin Luo1
· Yinfeng Xu2 · Haodong Liu2
© The Author(s) 2020
Abstract We consider an online car-sharing problem between two locations with advance bookings. Each customer submits a pair of requests, where each request specifies the pick-up time and the pick-up location: one request from A to B, and the other request from B to A, not necessary in this order. The scheduler aims to maximize the number of satisfied customers, where the schedule has to decide whether or not to accept a request pair immediately at the time when the request pair is submitted. This problem is called OnlineTransfersForCommuting. We present lower bounds on the competitive ratio for this problem with both fixed booking times and variable booking times, and propose two algorithms, greedy algorithm and balanced greedy algorithm, that achieve the best possible competitive ratios. Keywords Car-sharing problem · Online scheduling · Competitive analysis · Request pairs
1 Introduction The sharing economy has become more close to everyone. The car-sharing, as a new form of transport, has already been in use in daily life. In a car-sharing system, customers can book a car to drive from one place to another, and the car-sharing company will provide a car to serve this customer. Once a request for booking a car is accepted,
B
Kelin Luo [email protected] Yinfeng Xu [email protected] Haodong Liu [email protected]
1
Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands
2
School of Management, Xi’an Jiaotong University, Xi’an, China
123
Journal of Combinatorial Optimization
the customer can pick up a car at the origin, drive it to the destination and return it there. An optimization problem is denoted by car-sharing problem (C S − k in short), where the goal is to maximize the number of satisfied customers by k cars. A customer is satisfied if all his or her requests are fulfilled. In this paper, we study an online car-sharing problem where each customer submits two rides in opposite directions. This variant of online car-sharing problem is denoted by OnlineTransfersForCommuting (O T FC − k in short, where k is the number of cars), and the goal is to maximize the number of satisfied customers. A scenario is as follows: There are two popular locations, which could be a business center and a residential area. Customers want to drive from the business center to the residential area and drive back later and vise versa. Remark This work expanded the work of Luo et al. (2019b): we introduce the fixed booking time variant and variable booking time variant for this problem; we propose a balanced greedy algorithm for O T FC − k (k > 2) and prove that BGA is optimal. 1.1 Related work Off- line car- sharing problem Böhmová et al. (2016) studied two off-line versions of the car-sharing problems. In one problem, OfflineTransfersForCommuting, there are two locations and each customer submits two requests (each request is specified
Data Loading...
