1. Home
  2. TRID
  3. View Record
https://nap.nationalacademies.org/catalog/27432/critical-issues-in-transportation-for-2024-and-beyond

PLANIFICATION DE TOURNEES DE VEHICULES

Cette these porte sur la planification de tournees de vehicules pour la cueillette et la livraison de colis sous des contraintes de fenetres-horaire et de duree de tournee, et lorsque la capacite des vehicules n'est pas contraignante. Les chercheurs analysent un systeme utilisant un centre de tri, ce qui permet de separer la cueillette et la livraison. L'approche utilisee est de type "clustering first, routing second" et le probleme est ainsi decompose en deux parties : d'une part, la planification des zones i.e. le regroupement de points a visiter par un meme vehicule et, d'autre part, la confection des itineraires pour chacun des vehicules. La contribution de cette these se situe principalement a deux niveaux : premierement, ils ont mis au point une methode analytique de decoupage de zones pour le probleme de tournees de vehicules avec contraintes de duree et, deuxiemement, ils ont propose et analyse une formulation originale du probleme du voyageur de commerce particulierement bien adaptee a la modelisation de contraintes d'horaire. Pour la planifications des zones, les chercheurs presentent une methode analytique de decoupage d'une region en zones, chacune etant affectee a un seul vehicule. Le decoupage tient compte de la duree maximale d'une tournee et vise en minimiser les couts de transport. La methode determine les dimensions optimales d'une zone en fonction de son eloignement du depot et de la densite de la demande dans cette zone. Ils etudient aussi l'impact de la variabilite journaliere de la demande sur le design des zones et de la cooperation entre les vehicules. Enfin, ils indiquent comment la methode peut etre integree a un systeme interactif d'aide a la decision. Pour la confection des tournees de chacun des vehicules, ils proposent une nouvelle formulation du probleme du voyageur de commerce bien adaptee a la modelisation des contraintes d'horaire. La relaxation lineaire de cette formulation contient, pour un probleme comportant n points a visiter, 4n contraintes incluant les contraintes de fenetres-horaire. Ceci permet d'utiliser cette formulation pour resoudre des problemes de taille realiste sur micro-ordinateur. Les proprietes de cette formulation ont permis de mettre au point une methode interessante pour obtenir une borne au probleme du voyageur de commerce sans resoudre la relaxation lineaire de la formulation. La qualite de cette borne permet donc l'utilisation efficace d'une methode d'enumeration et evaluation progressive (Branch & Bound) pour obtenir la solution optimale. Une analyse et une classification des bornes obtenues par la relaxation lineaire d'un certain nombre de formulations du probleme du voyageur de commerce sont presentees. Enfin, ils demontrent l'equivalence de certaines formulations au niveau de la qualite de la borne. (A).

  • Authors:
    • LANGEVIN, A
  • Publication Date: 1988

Language

  • French

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01248061
  • Record Type: Publication
  • Source Agency: Institut Francais des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)
  • Files: ITRD
  • Created Date: Nov 20 2010 4:31AM