An Efficient Lagrangian Relaxation Algorithm for the Shared Parking Problem. (February 2023)

• Record Type: Journal Article
• Authors: Tang, Zhenpeng; Jiang, Yanping; Yang, Feifei
• Is Part Of: Computers & industrial engineering. Volume 176(2023)
• Publication Date: 2023-02
• Subjects: Shared parking -- Matching -- Lagrangian decomposition -- Lagrangian relaxation -- Utilization rate; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108860
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Demanders' requests in the parking rate and the walkding distance are considered. Parking time intervals can be any real intervals. An efficient Lagrangian relaxation algorithm is designed to maximize utilization. A Bottom-up Dynamic Programming (BDP) algorithm is embedded for solving subproblems. Abstract: In recent years, with the significant increase in the number of motor vehicles in big cities, parking difficulties have become increasingly prominent. It is crucial for alleviating the problem to tap the potential of idle parking spaces. We study how to make the most of the shared idle parking spaces to provide intelligent and efficient parking services for parking demanders by optimizing the allocation of the parking spaces. First, concerning the rigid requirements of the demanders on the parking rates and the walking distances, a matching model is developed with the objective of maximizing the utilization of shared parking spaces. In this model, the parking time intervals of parking demanders and the available time intervals of shared parking spaces are generalized to real intervals from integer intervals in previous related research. Second, the model is analyzed and proved to be NP-complete. A Lagrangian relaxation algorithm is considered to solve the model efficiently since the relaxation model becomes much easier to solve if a certain set of constraints are dropped. The novel points of the Lagrangian relaxation algorithm include two algorithms BDP (Bottom-up Dynamic Programming) and GH (Greedy Heuristic). The Lagrangian relaxation algorithm repeats three processes with different Lagrangian multiplier determined by the sub-gradient method until the stop-criteria is met: (1) find upper bounds based on algorithm BDP; (2) find lower bounds by algorithm GH. (3) update the Lagrangian multiplier. Finally, we conduct the experiments to simulate a realistic scenario where the commuters share idle parking spaces to the platform and drivers find parking spaces for some daily activities. The results show that our algorithm has high computational efficiency and accuracy. The efficiency advantage is distinct, especially when the computational scale of the problem is large. In addition, the final upper bound obtained by our algorithm is validated to be tight.