The parking allocation problem for connected vehicles
Tóm tắt
In this paper, we propose a parking allocation model that takes into account the basic constraints and objectives of a problem where parking lots are assigned to vehicles. We assume vehicles are connected and can exchange information with a central intelligence. Vehicle arrival times can be provided by a GPS device, and the estimated number of available parking slots, at each future time moment and for each parking lot is used as an input. Our initial model is static and may be viewed as a variant of the generalized assignment problem. However, the model can be rerun, and the algorithm can handle dynamic changes by frequently solving the static model, each time producing an updated solution. In practice this approach is feasible only if reliable quality solutions of the static model are obtained within a few seconds since the GPS can continuously provide new input regarding the vehicle’s positioning and its destinations. We propose a 0–1 programming model to compute exact solutions, together with a variable neighborhood search-based heuristic to obtain approximate solutions for larger instances. Computational results on randomly generated instances are provided to evaluate the performance of the proposed approaches.
Tài liệu tham khảo
Abidi, S., Krichen, S., Alba, E., Bravo, J.M.M.: A hybrid heuristic for solving a parking slot assignment problem for groups of drivers. Int. J. Intell. Transp. Syst. Res. 15(2), 85–97 (2016)
Ayala, D., Wolfson, O., Xu, B., DasGupta, B., Lin, J.: Parking in competitive settings: a gravitational approach. In: 2012 IEEE 13th International Conference on Mobile Data Management, IEEE, pp. 27–32 (2012)
Caicedo, F., Lopez-Ospina, H., Pablo-Malagrida, R.: Environmental repercussions of parking demand management strategies using a constrained logit model. Transp. Res. Part D Transp. Environ. 48, 125–140 (2016)
Cenerario, N., Delot, T., Ilarri, S.: Dissemination of information in inter-vehicle ad hoc networks. In: 2008 IEEE Intelligent Vehicles Symposium, IEEE, pp. 763–768 (2008)
Davis, A.Y., Pijanowski, B.C., Robinson, K.D., Kidwell, P.B.: Estimating parking lot footprints in the Upper Great Lakes Region of the USA. Landsc. Urban Plan. 96(2), 68–77 (2010)
Delot, T., Cenerario, N., Ilarri, S., Lecomte, S.: A cooperative reservation protocol for parking spaces in vehicular ad hoc networks. In: Proceedings of the 6th International Conference on Mobile Technology, Application and Systems, ACM, pp. 1–8 (2009)
Delot, T., Ilarri, S., Lecomte, S., Cenerario, N.: Sharing with caution: managing parking spaces in vehicular networks. Mob. Inf. Syst. 9(1), 69–98 (2013)
Gahlan, M., Malik, V., Kaushik, D.: GPS based parking system. Compusoft 5(1), 2053–2056 (2016)
Gantelet, E., Lefauconnier, A.: The time looking for a parking space: strategies, associated nuisances and stakes of parking management in France. In: Association for European Transport, Europe Transport Conference 2006, Strasbourg, France (2006)
Geoffrion, A.: Lagrangean relaxation for integer programming. In: Approaches to Integer Programming, No. 2 in Mathematical Programming Studies, Springer, Berlin, pp. 82–114 (1974)
Hanafi, S., Lazić, J., Mladenović, N., Wilbaut, C., Crévits, I.: New variable neighbourhood search based 0–1 MIP heuristics. Yugosl. J. Oper. Res. 25(3), 343–360 (2015)
Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423–454 (2016)
Ilarri, S., Delot, T., Trillo-Lado, R.: A data management perspective on vehicular networks. IEEE Commun. Surv. Tutor. 17(4), 2420–2460 (2015)
Mendez, G., Herrero, P., Valladares, R.: SIAPAS: a case study on the use of a GPS-based parking system. In: On the Move to Meaningful Internet Systems 2006: OTM 2006 Workshops, Springer, vol. 4277, pp. 945–954 (2006)
Roca-Riu, M., Fernández, E., Estrada, M.: Parking slot assignment for urban distribution: models and formulations. Omega 57(Part B), 157–175 (2015)
Schrijver, A.: Theory of Linear and Integer Programing. Wiley, New York (1986)
Shoup, D.C.: High cost of free parking. J. Plan. Educ. Res. 17(1), 3–22 (1997)
Shoup, D.C.: Cruising for parking. Transp. Policy 13(6), 479–486 (2006)
Teodorović, D., Lučić, P.: Intelligent parking systems. Eur. J. Oper. Res. 175(3), 1666–1681 (2006)
Toutouh, J., Alba, E.: Distributed fair rate congestion control for vehicular networks. In: Distributed Computing and Artificial Intelligence, 13th International Conference, No. 474 in Advances in Intelligent Systems and Computing, Springer, pp. 433–442 (2016)
Verroios, V., Efstathiou, V., Delis, A.: Reaching available public parking spaces in urban environments using ad hoc networking. In: 2011 12th IEEE International Conference on Mobile Data Management (MDM), IEEE, vol. 1, pp. 141–151 (2011)