考慮彈性車輛供給的租車車輛調度問題

Abstract

本研究探討了車輛調度中的車隊管理問題，著重於在計劃期內動態地從總站獲取臨時車輛以滿足既定的訂單需求。主要挑戰在於平衡接受更多訂單的收入與使用臨時車輛所產生的相關成本，包括車輛的每日使用成本和獲取成本。目標是通過最佳化車輛在各個站點之間的調度操作，並確定從總站獲取的最佳臨時車輛數量來最大化利潤，利潤包括訂單收入減去車輛的調度成本、使用成本和獲取成本。 我們提出了一個四階段的演算法：首先，我們通過調整臨時車的數量來建例子實例。接著，使用時空網路（TSN）方法將問題轉換為最小成本流問題。在第三階段，我們考慮臨時車輛的使用成本跟獲取成本，並且僅在增加更多臨時車輛能改善結果時才繼續。最後，我們比較所有結果，以確定最佳解決方案。在由四個因素的不同水平組成：臨時車輛數量、使用成本、獲取成本和訂單數量的 16 個情境中的實驗顯示，我們的演算法在決定是否使用臨時車輛時，能夠有效地考慮每日使用成本。隨著使用成本的增加，我們的演算法會避免使用臨時車輛，導致能接受的訂單數量減少，但能控制使用成本；而標竿則不受使用成本的影響，接受更多訂單，顯示出更高的訂單接受率和利潤，從而擴大了我們演算法跟標竿的差距。然而，我們合理地認為，我們的演算法與原問題的最佳解之間差距不會太大。此外，演算法的執行時間會隨著使用的臨時車數量增加而增加，但平均仍在一分鐘之內。總結來說，我們的演算法在管理臨時車輛分配方面表現穩健，能夠適當地考慮使用成本，平衡訂單接受率，並保持合理的計算時間，有效地確定所需的最佳臨時車輛數量，以實現利潤最大化。

In this study, we address fleet management in car relocation, focusing on dynamically acquiring temporary cars from a depot to meet order demands. The challenge is to balance the benefits of accepting more orders against the costs of temporary cars, including daily usage and acquiring costs. Our objective is to maximize profit by optimizing car relocation and determining the number of temporary cars, considering revenue from orders minus relocation, usage, and acquiring costs. We propose a four-phase algorithm: First, we create sub-instances with varying numbers of temporary cars. Next, we solve these using a time-space network (TSN) approach to transform the problem into a minimum cost flow problem, producing partial plans. In the third phase, we refine these plans to include usage and acquiring costs, continuing only if adding more temporary cars improve results. Finally, we compare the refined plans to determine the best solution, maximizing profit and the number of temporary cars. We conduct experiments across 16 scenarios characterized by varying levels of four factors: temporary car quantity, usage cost, acquiring cost, and order quantity. The results demonstrate that our algorithm effectively accounts for the daily usage cost when deciding whether to use temporary cars. As usage cost increases, our algorithm avoids using high-cost temporary cars, leading to fewer accepted orders but maintaining controlled usage cost. This contrasts with the benchmark model, which, unaffected by usage cost, accepts more orders and shows a higher acceptance rate and profit, widening the optimality gap. However, we reasonably believe that the solutions provided by our algorithm do not differ significantly from the optimal solution of the original problem. Additionally, the execution time of our algorithm increases with the number of temporary cars used, though it remains under one minute on average. In conclusion, our algorithm shows robust performance in managing temporary car allocation by appropriately considering usage cost, balancing order acceptance, and maintaining reasonable computation times. It effectively determines the best number of temporary cars required to maximize profits.