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

Subject/Index Terms

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