Program > By author > Beillevaire Boris

Les problèmes de tournées de véhicules consistent à déterminer un ensemble de tournées partant d'un dépôt et devant de satisfaire les demandes d'un ensemble de clients pour coût total minimal et avec une flotte de véhicules de capacité limitée. Une approche particulièrement efficace pour résoudre des problèmes de tournées de véhicules repose sur l'alternance entre deux espaces de solutions : celui des tours géants que l'on peut transformer en solution du problème de tournées dont les trips respectent la capacité des véhicules. Pour cela, le recours à l'algorithme Split (Prins, 2004) qui découpe optimalement un tour géant, est souvent utilisé (Prins et al., 2009). Dans ce papier, nous nous intéressons à la définition d'une version spécifique de l'algorithme Split permettant de traiter des problèmes multi-objectifs. L'exploration de l'espace de recherche est réalisée ici par le biais d'une métaheuristique basée sur les chemins reliants (path relinking). Pour tester notre approche, nous avons choisi le problème bi-objectif de tournées de véhicules avec équilibre des tournées (vehicle routing problem with route balancing -- VRPRB). Outre le classique critère basé sur la minimisation du coût des tournées, cette version considère la minimisation de la différence de longueur entre la plus grande et la plus petite tournée (balance). L'algorithme est testé sur sept instances introduites par (Christofides and Eilon, 1969) et (Christofides and al., 1979) et est comparé aux meilleurs résultats connus sur le critère du coût et aux résultats de (Jozefowiez et al., 2009) sur les deux critères simultanément. Il apparaît que la méthode apporte des résultats compétitifs avec la littérature.