DEUX NOUVEAUX ALGORITHMES EXACTS POUR LE PROBLEME DES M VOYAGEURS DE COMMERCE

Ce memoire contient la description de deux nouveaux algorithmes exacts pour le probleme des m voyageurs de commerce (m-PVC). Les chercheurs ont mis au point, pour la construction du premier algorithme, une nouvelle formulation du m-PVC. A l'aide de celle-ci ils ont elabore un algorithme de "branch-and-bound" tres efficace pour le m-PVC base sur la resolution a chaque noeud de l'arbre d'un probleme de flot a cout minimum. Le deuxieme algorithme qu'ils ont construit est une adaptation au cas du m-PVC d'un algorithme deja connu pour le probleme du voyageur de commerce. Ce deuxieme algorithme utilise le probleme d'affectation comme relaxation a chaque noeud de l'arbre d'enumeration. Cet algorithme s'est avere encore plus performant que le premier. (A).

• Authors:
  • TRINH, K N
• Publication Date: 1987

Language

• French

Media Info

• Pagination: 44P
• Serial:
  • CENTRE DE RECHERCHE SUR LES TRANSPORTS - PUBLICATION
  • Issue Number: 570
  • Publisher: CENTRE DE RECHERCHE SUR LES TRANSPORTS - UNIVERSITE DE MONTREAL

Subject/Index Terms

• TRT Terms: Calculation; Drivers; Itinerary; Methodology; Travel; Travelers
• ITRD Terms: 6464: Calcul; 699: Itineraire; 9102: Methode; TRANSPORT DE MARCHANDISE; 1755: Usager de la route; 698: Voyage
• Subject Areas: Society; I71: Traffic Theory; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01248078
• 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