即時車輛共乘問題在三點循環模型的競爭分析

Abstract

在汽車共乘問題中，我們旨在有效地分配有限的車輛來滿足城市中許多服務站的顧客。顧客可以在線上來指定他們的接送時間、接送地點和下車地點。演算法會以即時的方式來決定接受或拒絕請求。我們的目標是最大化滿足顧客需求的數量。 在之前的研究中，羅等人提出了一個新的車輛共乘模型，在這個模型中，每個請求都指定了預訂時間（提交請求的時間）、接送時間和接送地點。梁等人延續前面的研究，同時引入了一個新的模型稱為 kS2L-S，該模型具有 k 個服務器和兩個地點。在這個模型中，演算法可以同時看到所有在相同預訂時間的請求，並同時做出決策。梁等人證明了他們提出的貪婪平衡演算法（GBA）是最佳的。 在我們的研究中，我們想知道 GBA 中貪婪和平衡的想法是否仍然適用於延伸的 kS2L-S 模型。我們將 kS2L-S 模型延伸為三個地點的循環單向模型，稱為kS3L-S。我們的目標是在時間內最大化滿足（接受）請求的數量。我們證明了kS2L-S 中貪婪和平衡的想法仍然適用於 kS3L-S，並提出了相對應的貪婪平衡演算法 GBA-3L。在競爭分析中，我們展示了 kS3L-S 的下界是 2k/k+⌊k/3⌋ ，而 GBA-3L的 competitive ratio 也是 2k/k+⌊k/3⌋。因此，我們證明了演算法 GBA-3L 是最佳的。

In the car-sharing problem, we aim to efficiently assign the limited cars to customers across many service stations in a city. Customers can make online requests specifying their pick-up time, pick-up location and drop-off location. The decision to accept or reject a request is made in online fashion. Our goal is to maximize the number of fulfilled requests from customers. Luo et al. proposed a new car-sharing model in which each request specifies its booking time (request submission time), pick-up time, and pick-up location. Liang et al. followed the previous car-sharing formulation and then introduced a new simultaneous model called kS2L-S, featuring k servers and two locations. In this model, the scheduler (algorithm) can view all requests at the same booking time and make decisions together simultaneously. Liang et al. demonstrated that the greedy balanced algorithm (GBA) they proposed is optimal. In our work, we wonder whether the key concepts of greediness and balance in GBA are still applicable to the extended work of kS2L-S. We extend kS2L-S to a circular one- way model with three locations, named kS3L-S. Our goal is to maximize the number of fulfilled (accepted) requests over time as much as possible. We demonstrate that the key concepts of greediness and balance in kS2L-S are still applicable to kS3L-S and present the extended greedy balanced algorithm named GBA-3L. We present that the lower bound of the competitive ratio for kS3L-S is 2k/k+⌊k/3⌋ and the the competitive ratio of GBA-3L is also 2k/k+⌊k/3⌋. Therefore, we show that the bound is tight and our algorithm is optimal.