Skip to Main content Skip to Navigation
Conference papers

Variable Neighbourhood Decent for Parking Allocation Problem

Abstract : Searching for available parking lots presents a mayor problem in urban areas. Massive unorganized pursuit for parking provokes traffic congestion, financial losses, negative environmental effects, among others. Most studies on this topic base their research on simulations due to the large set of non-deterministic input. In this paper we propose an approach where each vehicle that is looking for a parking lot is equipped with GPS device. Based on this assumption, the static Parking allocation problem (PAP) can be modeled as a variant of Generalized assignment problem (GAP). Here we also discuss inclusion of the static model into a dynamic real-world circumstances. Moreover, we developed a heuristic based on sequential Variable Neighborhood Decent (VND) to solve static PAP. It uses two neighborhood structures : reallocation and interchange. It appears that the deviation of VND based heuristic, compared with the optimal solutions, are always less than 0.1%.
Document type :
Conference papers
Complete list of metadata
Contributor : Kathleen TORCK Connect in order to contact the contributor
Submitted on : Thursday, October 21, 2021 - 2:57:26 PM
Last modification on : Thursday, September 15, 2022 - 5:55:54 PM


  • HAL Id : hal-03390681, version 1



Marko Mladenovic, Thierry Delot, Christophe Wilbaut. Variable Neighbourhood Decent for Parking Allocation Problem. ROADEF 2017, 18ème conférence de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2017, Metz, France. ⟨hal-03390681⟩



Record views