Le problème de routage de véhicules (Vehicle Routing Problem, VRP dans lasuite de ce document) est un problème d'optimisation combinatoire et de recherche opérationnelle. Il fait partie de la catégorie des problèmes de transport, tout comme le problème du voyageur de commerce (Traveling Salesman Problem, (TSP) et le problème du postier chinois (Chinese Postman Problem, CPP). Dans ces problèmes relevant du domaine de la logistique, un ou plusieurs véhicules doivent couvrir un réseau de transport pour livrer des marchandises à des clients ou couvrir les routes de ce réseau.Le problème de routage de véhicules a été largement étudié durant la deuxièmemoitié du siècle dernier. Rego and Roucairol [1994] considèrent que les années1980s constituent l'apogée de ces études et l'un des plus beaux succès de la recherche opérationnelle. Les principales motivations de l'étude du VRP sont d'une part la difficulté de sa résolution et d'autre part ses nombreuses applications pratiques en logistique. Ce deuxième point concerne les retombées économiques et environnementales liées à la minimisation des coûts des systèmes de transport. En effet, selon Toth and Vigo [2001a], les frais de transport représentent généralement entre 10% et 20% des prix naux des marchandises sur le marché, et les procédures informatisées basées sur des techniques d'optimisation permettent de faire des économies de l'ordre de 5% à 20% sur ces coûts de transport. Nous commencerons tout d'abord par présenter les problèmes de TSP, VRP et CPP en mettant l'accent sur la modélisation mathématique du problème de routage de véhicules ainsi que sur ses variantes principales. Nous présenterons ensuite une synthèse des différentes méthodes de résolution du VRP et de leurs classifications. Nous apporterons une attention particulière aux algorithmes génétiques et à leur application au VRP. Nous nous intéresserons en aux approches interactives dans la résolution du problème de routage de véhicules et aux performances humaines dans ce domaine.
