Variable Neighbourhood Decent for Parking Allocation Problem

Marko Mladenovic (1) , Thierry Delot (1) , Christophe Wilbaut (1)

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

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%.

Mots clés: Parking allocation problem; Variable neighborhood descent; General assignment

Domaines: Informatique [cs]

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⟩