預約制共享停車位系統車位排程最佳化模式與演算法

本研究針對預約制共享停車位系統求解停車位指派與排程問題，提出停車位流動網路方法，並定式停車位指派與排程最佳化模式，目標為最大化業者的利潤。由於建立的模式為整數多商品網路流量問題，屬於NP-Hard，為有效率地求解大規模例題，本研究發展了以模擬退火法（simulated annealing, SA）為基礎的巨集啟發式演算法。本研究根據業者提供的歷史資料建立三組不同規模的測試例題，撰寫C++程式利用Gurobi軟體與SA演算法進行求解。數值實驗結果顯示發展的演算法在不同測試例題都能有效率地得到最佳解或近似最佳解。本研究成果將可提供相關平台業者在未來導入預約制停車位共享系統時作為車位指派與排程之參考。

關鍵字

共享停車位；排程問題；整數多商品網路流量問題；模擬退火法

並列摘要

This study deals with the parking space assignment and scheduling problem for a shared parking system with advanced reservations. We propose a parking space-flow network modeling approach to develop an optimization model that determine the optimal assignment of a set of parking requests to a set of shared parking spaces and the optimal schedule of the shared parking spaces. The objective of the model is to maximize the profit of the system operator. The problem is formulated as an integer multi-commodity network flow problem, which is NP-Hard. In order to efficiently solve large instances of the problem, this study develops a simulated annealing (SA) based metaheuristic. Three sets of test instances with different numbers of parking spaces and parking requests are generated using historical data provided by the operator a local shared parking system. The instances of the model are solved using Gurobi and the SA algorithm. The numerical results show that the proposed algorithm is able to efficiently obtain optimal or near optimal solutions for the test instances. The proposed approach in this study could assist operators of shared parking systems with advanced reservations to effectively and efficiently assign parking requests to shared parking spaces and schedule the use of shared parking spaces.