考量即時需求之路邊租還電動共享汽車充電與調度系統

Vehicle Charging and Relocation in Free-floating Electric Carsharing System Considering Real-Time Requests

施千華(Chien-Hua Shih)

指導教授 ： 朱致遠

國立臺灣大學/工學院/土木工程學系/碩士(2022年)

https://doi.org/10.6342/NTU202201827

摘要

共享運具於近年蓬勃發展，提供人們一個運具使用的新選擇。但因共享運具存在車輛空間分布不均與使用者不確定性等因素，因此需要一個有效的營運方式來調度和管理。本研究基於營運者的角度，提出一個考量即時預約需求的路邊租還共享汽車調度系統的最佳化演算法。
因不限制顧客的預約時間，本研究設計一個即時預約需求的共享車輛系統調度問題演算法，進行共享車輛與調度員的調度與顧客需求的管理。首先使用時間分批的策略，將營業時間切分成許多等長時間段，依前一時間段預約的顧客資訊，使用事先預約需求系統的共享車輛系統調度問題演算法求解共享車輛及調度員的路線及時間表。在下個時間段開始時，根據車輛與調度員當下的位置與新的顧客資訊做重新求解。若調度員正在執行任務，則透過重新導向措施設立新的節點，尋找對營運者更有利益的目的地，即時調整為更具效益的調度任務。作為可供即時預約模式，重新最佳化的運算時間可能會影響實務上的運作，本研究也設計兩種演算法的加速方式來增加運算速度。
事先預約系統演算法為即時預約系統演算法的核心運算工具，因此本研究將該演算法與混合整數模型的結果作比較驗證，證明事先預約系統演算法具備良好的運算速度與求解成效。除此之外，本研究也透過實際共享車輛使用資料組成的中型案例與大型案例來演示即時預約系統演算法的成果，並透過敏感度分析，提供營運者對於求解頻率、最小提前預約時間、即時預約需求比例配置、車隊大小及調度員數量作決策參考。

關鍵字

即時預約需求 ； 路邊租還共享運具 ； 電動車 ； 動態調度 ； 篩選式局部搜索演算法 ； 時間分批法 ； 重新導向

並列摘要

Shared vehicles have been more common in recent years, providing people with a new mode choice. However, due to factors such as imbalance distribution of vehicles and uncertainty of users, an effective operation method is required for scheduling and management. Therefore, this study proposes an optimal model for the operator-based dynamic relocation strategy for free-floating electric vehicle sharing systems that considers the real-time demand.
Because there is no restriction on the customer's reservation time, this study designs an algorithm for the scheduling problem of the shared vehicle system with real-time demand (Real-time reservation algorithm), which is used for the scheduling of shared vehicles and dispatchers and the management of customer needs. First, we use the time batching strategy to divide the operating time into many time periods, then we use the algorithm for the scheduling problem of the shared vehicle system with advanced-reserved demand (Advanced reservation algorithm) to solve scheduling problem in every time period. Secondly, at the beginning of the next time period, the solution is re-solved based on the current location of the vehicle and the dispatcher and the new customer information. If the dispatcher is performing a task, a new dummy node will be set up through diversion measures to find a new destination that is more beneficial to the operator, and the dispatcher will be adjusted to a more profitable task in real-time. As a real-time reservation algorithm, the re-optimization computation time may affect the actual operation. Therefore, this study also designs two ways to accelerate the speed of algorithm.
The advanced reservation algorithm is the core computing tool of the real-time reservation algorithm. Therefore, this study compares the results of the algorithm with the mixed integer programing and verifies that the advanced reservation algorithm has a great performance of computational speed and solution quality. In addition, this study also displays the results of the real-time reservation algorithm through medium-sized cases and large-scale cases both designed based the on actual shared vehicle usage data. Through the sensitivity test, this study can help operator to make decision on the policy like the size of the fleet, the number of dispatchers, the frequency of re-optimization, reservation time and the real-time demand proportion.

並列關鍵字

Real-time requests ； Free-floating shared mobility ； Electric vehicle ； Dynamic relocation ； Filtered local search heuristics algorithm ； Time batching strategy ； Diversion

參考文獻

[1] Potvin, J. Y., & Rousseau, J. M. (1993). A parallel route building algorithm for the

vehicle routing and scheduling problem with time windows. European Journal of

Operational Research, 66(3), 331-340.

[2] Larsen, A., & Madsen, O. B. (2000). The dynamic vehicle routing problem (Doctoral dissertation, Institute of Mathematical Modelling, Technical University of Denmark).

[3] Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573-586.