Online car-sharing problem with variable booking times
Tóm tắt
In this paper, we address the problem of online car-sharing with variable booking times (CSV for short). In this scenario, customers submit ride requests, each specifying two important time parameters: the booking time and the pick-up time (start time), as well as two location parameters—the pick-up location and the drop-off location within a graph. For each request, it’s important to note that it must be booked before its scheduled start time. The booking time can fall within a specific interval prior to the request’s starting time. Additionally, each car is capable of serving only one request at any given time. The primary objective of the scheduler is to optimize the utilization of k cars to serve as many requests as possible. As requests arrive at their booking times, the scheduler faces an immediate decision: whether to accept or decline the request. This decision must be made promptly upon request submission, precisely at the booking time. We prove that no deterministic online algorithm can achieve a competitive ratio smaller than
$$L+1$$
even on a special case of a path (where L denotes the ratio between the largest and the smallest request travel time). For general graphs, we give a Greedy Algorithm that achieves
$$(3L+1)$$
-competitive ratio for CSV. We also give a Parted Greedy Algorithm with competitive ratio
$$(\frac{5}{2}L+10)$$
when the number of cars k is no less than
$$\frac{5}{4}L+20$$
; for CSV on a special case of a path, the competitive ratio of Parted Greedy Algorithm is
$$(2L+10)$$
when
$$k\ge L+20$$
.
Từ khóa
Tài liệu tham khảo
Böhmová K, Disser Y, Mihalák M, Srámek R (2016) Scheduling transfers of resources over time: towards car-sharing with flexible drop-offs. In: Kranakis E, Navarro G, Chávez E (eds) LATIN 2016: theoretical informatics—12th Latin american symposium, Ensenada, Mexico, April 11–15, 2016, proceedings, lecture notes in computer science, vol 9644. Springer, pp 220–234. https://doi.org/10.1007/978-3-662-49529-2_17
Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge
Christman A, Forcier W, Poudel A (2018) From theory to practice: maximizing revenues for on-line dial-a-ride. J Comb Optim 35(2):512–529. https://doi.org/10.1007/s10878-017-0188-z
Guo X, Luo K (2022) Algorithms for online car-sharing problem. In: Balachandran N, Inkulu R (eds) Algorithms and discrete applied mathematics-8th international conference, CALDAM 2022, Puducherry, India, February 10–12, 2022, Proceedings, Lecture Notes in Computer Science, vol. 13179. Springer, pp 224–236. https://doi.org/10.1007/978-3-030-95018-7_18
Krumke SO, de Paepe W, Poensgen D, Lipmann M, Marchetti-Spaccamela A, Stougie L (2005) On minimizing the maximum flow time in the online dial-a-ride problem. In: Erlebach T, Persiano G (eds) Approximation and online algorithms, third international workshop, WAOA 2005, Palma de Mallorca, Spain, October 6–7, 2005, Revised papers, lecture notes in computer science, vol 3879. Springer, pp 258–269. https://doi.org/10.1007/11671411_20
Li S, Zheng L, Lee VCS (2020) Car-sharing: online scheduling k cars between two locations. In: Li M (ed) Frontiers in algorithmics-14th international workshop, FAW 2020, Haikou, China, October 19–21, 2020, proceedings, lecture notes in computer science, vol 12340. Springer, pp 49–61. https://doi.org/10.1007/978-3-030-59901-0_5
Lipton RJ, Tomkins A (1994) Online interval scheduling. In: Sleator DD (ed) Proceedings of the fifth annual ACM-SIAM symposium on discrete algorithms. 23–25 January 1994, Arlington, Virginia, USA. ACM/SIAM, pp 302–311. http://dl.acm.org/citation.cfm?id=314464.314506
Liu H, Luo K, Xu Y, Zhang H (2019) Car-sharing problem: online scheduling with flexible advance bookings. In: Li Y, Cardei M, Huang Y (eds) Combinatorial optimization and applications-13th international conference, COCOA 2019, Xiamen, China, December 13–15, 2019, proceedings, lecture notes in computer science, vol 11949. Springer, pp 340–351. https://doi.org/10.1007/978-3-030-36412-0_27
Luo K, Erlebach T, Xu Y (2018a) Car-sharing between two locations: online scheduling with flexible advance bookings. In: Wang L, Zhu D (eds) Computing and combinatorics-24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018, proceedings, lecture notes in computer science, vol 10976. Springer, pp 242–254. https://doi.org/10.1007/978-3-319-94776-1_21
Luo K, Erlebach T, Xu Y (2018b) Car-sharing between two locations: online scheduling with two servers. In: Potapov I, Spirakis PG, Worrell J (eds) 43rd International symposium on mathematical foundations of computer science, MFCS 2018, August 27–31, 2018, Liverpool, LIPIcs, vol 117. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp 50:1–50:14. https://doi.org/10.4230/LIPIcs.MFCS.2018.50
Luo K, Erlebach T, Xu Y (2018c) Online scheduling of car-sharing requests between two locations with many cars and flexible advance bookings. In: Hsu W, Lee D, Liao C (eds) 29th International symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan, LIPIcs, vol 123. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp 64:1–64:13. https://doi.org/10.4230/LIPIcs.ISAAC.2018.64
Luo K, Erlebach T, Xu Y (2019) Car-sharing on a star network: On-line scheduling with k servers. In: Niedermeier, R, Paul C (eds) 36th International symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany, LIPIcs, vol 126. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp 51:1–51:14. https://doi.org/10.4230/LIPIcs.STACS.2019.51
The future of driving: Seeing the back of the car (2012) https://www.economist.com/briefing/2012/09/22/seeing-the-back-of-the-car