Loading...
Please wait, while we are loading the content...
Similar Documents
Optimisation de tournées de véhicules par programmation par contraintes : conception et développement d'un solveur industriel
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ducomman, Sylvain |
| Copyright Year | 2017 |
| Abstract | Les problemes de tournees de vehicules sont des problemes d’optimisation combinatoire epineux avec des enjeux economiques et environnementaux importants au sein de la chaine logistique. Le probleme fondamental est de desservir des clients avec un ensemble de vehicules de facon a minimiser la distance totale parcourue. En pratique, il y a une grande variete d’objectifs et de contraintes additionnelles, liees a la legislation et a la diversite des domaines d’applications. Ces problemes de tournees sont tres frequents pour de nombreuses industries et la conception d’approches de resolution generiques est devenue une question de recherche importante.Cette these porte sur la conception et le developpement d’un nouveau moteur de resolution pour les logiciels de tournees de vehicules proposes par l’entreprise GEOCONCEPT. Le solveur mis au point s’appuie sur la programmation par contraintes (PPC) pour ameliorer la flexibilite (prise en compte de contraintes additionnelles), la declarativite et la maintenance qui sont les limites des solveurs actuels de GEOCONCEPT fondes sur la recherche locale.Dans un premier temps, un modele de graphe est etabli pour la representation unifiee des donnees et de nombreuses contraintes metiers. La resolution s’effectue par des approches a base de voisinage large disponibles dans les solveurs de PPC modernes. On peut ainsi traiter des instances de tres grandes tailles efficacement tout en conservant une approche declarative pour exprimer une classe tres large de problemes de tournees de vehicules. Dans un second temps, des modeles PPC s’appuyant sur des representations redondantes du probleme sont proposes afin de renforcer le filtrage. Nous nous interessons en details aux mecanismes de filtrage c’est-a-dire aux processus d’elimination des valeurs infaisables ou sous-optimales dans les domaines des variables. Ces algorithmes permettent de simplifier rapidement le probleme et de fournir des bornes inferieures afin d’evaluer la qualite des solutions obtenues. Les bornes inferieures sont obtenues en resolvant des relaxations du plus celebre des problemes de la Recherche Operationnelle : le probleme du voyageur de commerce (TSP). Ce probleme est le cœur de la contrainte globale weightedcircuit permettant de modeliser les problemes de tournees en PPC. Nous proposons de nouveaux mecanismes de filtrage pour cette contrainte s’appuyant sur trois relaxations du TSP. Ces relaxations sont comparees sur les plans theorique et experimental. L’originalite de ce travail est de proposer un nouvel algorithme de filtrage permettant de raisonner a la fois sur les successeurs directs d’un client et sur sa position dans la tournee. Ces raisonnements sont particulierement utiles en presence de contraintes de fenetres de temps, tres communes dans les problemes industriels.Le nouveau moteur de resolution offre d’excellentes performances sur des problemes academiques et industriels tout en proposant des bornes inferieures informatives a des problemes industriels reels. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://tel.archives-ouvertes.fr/tel-01688288/file/DUCOMMAN_2017_diffusion.pdf |
| Alternate Webpage(s) | https://tel.archives-ouvertes.fr/tel-01688288/document |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
