Online scheduling of car-sharing request pairs between two locations

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.