×

A scalable dynamic parking allocation framework. (English) Zbl 1458.90202

Summary: Cities suffer from high traffic congestion of which one of the main causes is the unorganized pursuit for available parking. Apart from traffic congestion, the blind search for a parking slot causes financial and environmental losses. We consider a general parking allocation scenario in which the GPS data of a set of vehicles, such as the current locations and destinations of the vehicles, are available to a central agency which will guide the vehicles toward a designated parking lot, instead of the entered destination. In its natural form, the parking allocation problem is dynamic, i.e., its input is continuously updated. Therefore, standard static allocation and assignment rules do not apply in this case. In this paper, we propose a framework capable of tackling these real-time updates. From a methodological point of view, solving the dynamic version of the parking allocation problem represents a quantum leap compared with solving the static version. We achieve this goal by solving a sequence of 0-1 programming models over the planning horizon, and we develop several parking policies. The proposed policies are empirically compared on real data gathered from three European cities: Belgrade, Luxembourg, and Lyon. The results show that our framework is scalable and can improve the quality of the allocation, in particular when parking capacities are low.

MSC:

90B20 Traffic problems in operations research
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abidi, S.; Krichen, S.; Alba, E.; Bravo, J. M.M., A hybrid heuristic for solving a parking slot assignment problem for groups of drivers, International Journal of Intelligent Transportation Systems Research, 15, 2, 85-97 (2017)
[2] Angelelli, E.; Arsik, I.; Morandi, V.; Savelsbergh, M.; Speranza, M., Proactive route guidance to avoid congestion, Transportation Research Part B: Methodological, 94, 1-21 (2016)
[3] Angelelli, E.; Morandi, V.; Speranza, M., A trade-off between average and maximum arc congestion minimization in traffic assignment with user constraints, Computers & Operations Research, 110, 88-100 (2019) · Zbl 1458.90197
[4] Bayram, V.; Tansel, B.; Yaman, H., Compromising system and user interests in shelter location and evacuation planning, Transportation Research Part B: Methodological, 72, 146-163 (2015)
[5] Berbeglia, G.; Cordeau, J.-F.; Laporte, G., Dynamic pickup and delivery problems, European Journal of Operational Research, 202, 1, 8-15 (2010) · Zbl 1176.90048
[6] Caicedo, F.; Lopez-Ospina, H.; Pablo-Malagrida, R., Environmental repercussions of parking demand management strategies using a constrained logit model, Transportation Research Part D: Transport and Environment, 48, 125-140 (2016)
[7] Cavadas, J., Homem de Almeida Correia, G., Gouveia, J. 2015. A MIP model for locating slow-charging stations for electric vehicles in urban areas accounting for driver tours. Transportation Research Part E: Logistics and Transportation Review 75, 188-201.
[8] Delot, T.; Cenerario, N.; Ilarri, S.; Lecomte, S., A cooperative reservation protocol for parking spaces in vehicular ad hoc networks, (Proceedings of the 6th International Conference on Mobile Technology, Application & Systems (2009), ACM), 1-8
[9] Delot, T.; Ilarri, S.; Lecomte, S.; Cenerario, N., Sharing with caution: Managing parking spaces in vehicular networks, Mobile Information Systems, 9, 1, 69-98 (2013)
[10] Dsouza, K. B.; Mohammed, S.; Hussain, Y., Smart parking-An integrated solution for an urban setting, in, (Convergence in Technology (I2CT), 2017 2nd International Conference (2017), IEEE), 174-177
[11] Farag, M. S.; Mohie El Din, M. M.; El Shenbary, H. A., Smart parking guidance using optimal cost function, Computer and Information Science, 10, 1, 48-53 (2017)
[12] Florian, M.; Los, M., Impact of the supply of parking spaces on parking lot choice, Transportation Research Part B: Methodological, 14, 1-2, 155-163 (1980)
[13] Gantelet, E.; Lefauconnier, A., The time looking for a parking space: Strategies, associated nuisances and stakes of parking management in France, Europe Transport Conference, 1-6 (2006)
[14] Geng, Y.; Cassandras, C., Dynamic resource allocation in urban settings: A smart parking approach, IEEE International Symposium on Computer-Aided Control System Design (CACSD), 2011, 1-6 (2011)
[15] Jahn, O.; Möhring, R. H.; Schulz, A. S.; Stier-Moses, N. E., System-optimal routing of traffic flows with user constraints in networks with congestion, Operations Research, 53, 4, 600-616 (2005) · Zbl 1165.90499
[16] Lin, T.; Rivano, H.; Le Mouel, F., A survey of smart parking solutions, IEEE Transactions on Intelligent Transportation Systems, 18, 12, 3229-3253 (2017)
[17] Millard-Ball, A., The autonomous vehicle parking problem, Transport Policy, 75, 99-108 (2019)
[18] Mitrović-Minić, S.; Krishnamurti, R.; Laporte, G., Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows, Transportation Research Part B: Methodological, 38, 8, 669-685 (2004)
[19] Mladenović, M., 2020. The dynamic parking allocation problem: theoretical and practical solution methods, Ph.D. thesis, Université Polytechnique Hauts-de-France.
[20] Mladenović, M.; Delot, T.; Laporte, G.; Wilbaut, C., The parking allocation problem for connected vehicles, Journal of Heuristics, 26, 377-399 (2020)
[21] Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A. L., A review of dynamic vehicle routing problems, European Journal of Operational Research, 225, 1, 1-11 (2013) · Zbl 1292.90203
[22] Psaraftis, H. N.; Wen, M.; Kontovas, C. A., Dynamic vehicle routing problems: Three decades and counting, Networks, 67, 1, 3-31 (2016)
[23] Roca-Riu, M.; Fernández, E.; Estrada, M., Parking slot assignment for urban distribution: Models and formulations, Omega, 57, Part B, 157-175 (2015)
[24] Shao, C.; Yang, H.; Zhang, Y.; Ke, J., A simple reservation and allocation model of shared parking lots, Transportation Research Part C: Emerging Technologies, 71, 303-312 (2016)
[25] Shoup, D. C., High cost of free parking, Journal of Planning Education and Research, 17, 3-22 (1997)
[26] Shoup, D. C., Cruising for parking, Transport Policy, 13, 6, 479-486 (2006)
[27] Shoup, D., The High Cost of Free Parking (2011), Planners Press: Planners Press Chicago
[28] Tang, C.; Wei, X.; Zhu, C.; Chen, W.; Rodrigues, J. J.P. C., Towards smart parking based on fog computing, IEEE Access, 6, 70172-70185 (2018)
[29] Thompson, R. G.; Bonsall, P., Drivers’ response to parking guidance and information systems, Transport Reviews, 17, 2, 89-104 (1997)
[30] Toutouh, J.; Alba, E., Distributed fair rate congestion control for vehicular networks, (Distributed Computing and Artificial Intelligence, 13th International Conference, no 474 in Advances in Intelligent Systems and Computing (2016), Springer: Springer Cham), 433-442
[31] Verroios, V., Efstathiou, V., Delis, A., 2011. Reaching available public parking spaces in urban environments using ad hoc networking. In: Mobile Data Management (MDM), 2011 12th IEEE International Conference on, vol. 1. IEEE, pp. 141-151.
[32] Zou, B.; Kafle, N.; Wolfson, O.; Lin, J. J., A mechanism design based approach to solving parking slot assignment in the information era, Transportation Research Part B: Methodological, 81, 631-653 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.