Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème de tournées de véhicules
Résumé
vignette|Figure illustrant une des solutions d'un problème de tournées avec un dépôt central et 3 véhicules disponibles.
Le problème de tournées de véhicules (aussi appelé VRP pour Vehicle Routing Problem) est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une flotte de véhicules afin de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales). Le but est de minimiser le coût de livraison des biens. Ce problème est une extension classique du problème du voyageur de commerce, et fait partie de la classe des problèmes NP-complet.
Quelques variantes classiques du problème de tournées de véhicules :
tournées de véhicules avec profits (aussi appelé VRPP pour Vehicle Routing Problem with Profits) : Un problème de maximisation de collecte de profits où il faut sélectionner quels clients visiter tout en respectant les capacités limitées des véhicules .
contraintes de capacité (aussi appelé CVRP pour Capacitated Vehicle Routing Problem) : Les véhicules ont une capacité d'emport limitée (quantité, taille, poids) ;
contraintes liées aux ressources et aux clients : disponibilité, localisation, compétences requises ;
tournées de véhicules avec fenêtre de temps : Pour chaque client on impose une fenêtre de temps dans laquelle la livraison doit être effectuée ;
tournées de véhicules avec collecte et livraison : Un certain nombre de marchandises doivent être déplacées de sites de collecte vers des sites de livraisons.
La résolution du problème peut devenir très difficile lorsque les sous-problèmes interagissent entre eux, par exemple, le problème de bin packing interagit avec l'allocation et la création de tournées dans le cas d'un problème avec contraintes de capacité.
Comme pour la plupart des problèmes NP-complet il est difficile de résoudre des instances de grande taille de façon optimale. On se contente alors de trouver des solutions de « bonne qualité ».
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.