Résolution du problème généralisé de tournées de véhicules

National audienceNous traitons le problème généralisé de tournées de véhicules (GVRP) qui est une extension du problème de tournées de véhicules (CVRP). Soit G = (V;E) un graphe non-orienté, où V est l'ensemble des noeuds et E est l'ensemble des arêtes. V est l'ensemble des n noeuds qui peuvent être visités, le noeud v0 est le dépôt où m véhicules identiques avec une capacité commune Q sont localisés. C est un ensemble de K grappes (ayant une demande et incluant un ensemble de nœuds). Le nombre de véhicules m peut être fixe ou variable. Un coût est associé à chaque arête de E. Le GVRP consiste à déterminer m routes pour m véhicules commençant et terminant au dépôt, telles que exactement un noeud de chaque grappe est visité une seule fois, la capacité des véhicules est respectée et le coût est minimisé. Le nombre de véhicules est une variable de décision. Nous présentons une nouvelle formulation pour ce problème et nous développons un algorithme de branchement et coupes classique pour résoudre exactement le GVRP. Nous introduisons ensuite une métaheuristique qui donne de bonnes solutions pour le GVRP. Elle est utilisée aussi pour fournir des bornes supérieures initiales pour notre algorithme de branchement et coupes. Sa caractéristique nouvelle est une procédure de Découpe qui convertit un tour géant incluant uniquement les grappes et encodé comme les tours de TSP en une solution du GVRP. Cette procédure est ensuite intégrée dans un algorithme hybride entre GRASP et ELS proposé dans Prins(2009). Nous présentons également les résultats des expérimentations numériques