An Efficient Lagrangian Relaxation Algorithm for the Shared Parking Problem

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.

Automated summary

With the increase in the number of motor vehicles in big cities, the issue of parking difficulties has become more prominent. This study focuses on how to optimize the allocation of shared idle parking spaces to provide intelligent and efficient parking services for parking demanders. A matching model is developed to maximize the utilization of shared parking spaces, and a Lagrangian relaxation algorithm is used to efficiently solve the model. The algorithm shows high computational efficiency and accuracy, especially for large-scale problems.