HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Two-stage matching-and-scheduling algorithm for real-time private parking-sharing programs

Abstract : This paper studies a real-time parking-sharing program with which owners of private parking spaces can lend out their parking spaces to other drivers to park when these are not in use. Compared with curbside and garage parking problems, the information of supplies and demands is randomly announced by drivers and owners respectively via a parking-sharing APP installed on their smartphones. Besides, the parking spaces made available by independent owners are usually heterogeneous in terms of their locations and available time intervals. Thus, two critical issues need to be resolved: (a) appropriately matching demands and supplies under an uncertain setting; and (b) efficiently scheduling the demands matched to avoid potential parking conflicts. We propose a novel real-time reservation approach based on a rolling-horizon framework, which can assign multiple drivers to a single parking space in order to better utilize scarce parking resources. For each period, an integrated optimal matching-and-scheduling problem is formulated as a mixed integer programming model and proved to be strongly NP-hard. To fast generate a near-optimal solution to the problem, a two-stage heuristics derived from the minimum-cost flow problem is developed. The computational results validate the efficiency and effectiveness of the proposed approach. Some operational insights are also presented and discussed.
Document type :
Journal articles
Complete list of metadata

Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Friday, September 11, 2020 - 10:51:21 PM
Last modification on : Monday, December 13, 2021 - 9:17:17 AM

Links full text



Pengyu Yan, Xiaoqiang Cai, Debing Ni, Feng Chu, Heng He. Two-stage matching-and-scheduling algorithm for real-time private parking-sharing programs. Computers & Operations Research, 2021, 125, pp.105083. ⟨10.1016/j.cor.2020.105083⟩. ⟨hal-02936963⟩



Record views