考慮即時訂單加入後對現有車輛和調度員重定位規劃的優化問題

Abstract

關於租車業的車輛調度一直以來都是受關注的議題。而對於當下的互聯網時代，即時性是影響用戶消費決策的重要因素，用戶們希望在移動端送出預訂需求後能夠快速知曉自己的預訂是否被公司接受；而公司端也需要快速做出接受與否的決定以及若接受的話如何調整當前的調度計劃以承接該筆新訂單。 本研究針對考慮調度員的車輛重定位問題，討論實時預訂請求下的接受與否以及動態調整當前調度員與車輛的重定位計劃。本研究的目標是最大化公司收益，即訂單總利潤減去車輛重定位成本以及調度員重定位成本。我們將問題分為兩個階段，第一階段僅解決車輛的重定位問題，考慮新訂單加入後如何調整目前的車輛重定位計劃；第二階段考慮在當前經過調整的車輛重定位計劃下，如何調整每一個調度員的重定位任務路線。在第一階段，我們使用時空網路圖表示車輛的重定位問題，並證明了在時空網路圖模型建模問題後，存在快速找出車輛重定位計劃最佳調整方式的線性時間方法；第二階段我們則將其轉化為時窗限制動態車輛路線問題（Dynamic vehicle routing problems with time windows，VRPTW），使用啟發式演算法解決該問題。 為了展示演算法的有效性以及效率，本文將在十二種情境下進行實驗。實驗結果表明，我們的演算法可在第一階段大幅減少找出最佳解的所需時間，在第二階段則可在有效減少計算所需時間的同時獲得近似解。

The vehicle relocation in the car rental industry has consistently been a focal point of attention. Real-time responsibility significantly influences consumer decision-making. They anticipate rapid feedback on whether their booking requests have been accepted by the company after submission via mobile platforms. Concurrently, companies must swiftly decide whether to accept these requests and, if accepted, how to adjust the existing dispatch plans to accommodate the new orders. This study addresses the vehicle relocation problem with dispatcher scheduling, discussing the acceptance or rejection of real-time booking requests and the dynamic adjustment of the current vehicle and dispatcher relocation plans. The objective of this research is to maximize company profits, defined as the total profit from orders minus the costs associated with vehicle and dispatcher relocations. The problem is divided into two stages: the first stage focuses solely on vehicle relocation, examining how to adjust the current vehicle relocation plan in response to new orders; the second stage addresses the adjustment of the dispatcher schedule within the revised vehicle relocation plan. In the first stage, we construct a space-time network graph to represent the vehicle relocation problem and demonstrate that, following the modeling of the problem with the space-time network graph, a linear-time method exists to efficiently identify the optimal adjustment of the vehicle relocation plan. In the second stage, we convert the problem into a Dynamic Vehicle Routing Problem with Time Windows (VRPTW) and solve it using a heuristic algorithm. To validate the efficacy and efficiency of the algorithm, we designed twelve scenarios and conducted experiments. The experimental results indicate that our algorithm significantly reduces the time required to find the optimal solution in the first stage and effectively minimizes computation time while obtaining approximate solutions in the second stage.