LE PROBLEME DU VOYAGEUR DE COMMERCE SELECTIF

ON CONSIDERE UN GRAPHE DANS LEQUEL ON ASSOCIE DES DISTANCES AUX ARCS ET DES PROFITS AUX SOMMETS. LE PROBLEME DU VOYAGEUR DE COMMERCE SELECTIF (OU PROBLEME D'ORIENTEERING) CONSISTE A DETERMINER DANS CE GRAPHE UN CIRCUIT SIMPLE DE PROFIT MAXIMAL ET AYANT UNE LONGUEUR NE DEPASSANT PAR UNE BORNE DONNEE. ON FORMULE LE PROBLEME COMME UN PROGRAMME LINEAIRE EN NOMBRES ENTIERS. ON CALCULE ENSUITE DES BORNES SUPERIEURES ET INFERIEURES QUE L'ON UTILISE DANS DES ALGORITHMES ENUMERATIFS. UNE VERSION PLUS ELABOREE DU PROBLEME OU ON CONSIDERE PLUSIEURS ENSEMBLES DE POINTS PLUTOT QU'UN SEUL EST AUSSI ANALYSEE. (A)

    Language

    • French

    Project

    • Sponsor Organizations:

      CONSEIL DE RECHERCHES EN SCIENCES NATURELLES ET EN GENIE

      200, RUE KENT
      OTTAWA,   Canada  K1A 1H5
    • Project Managers:

      MARTELLO, S

      LAPORTE, G

    • Performing Organizations:

      CENTRE DE RECHERCHE SUR LES TRANSPORTS - UNIVERSITE DE MONTREAL

      C.P. 6128, SUCCURSALE A
      MONTREAL,   Canada  H3C 3J7
    • Start Date: 19860000
    • Expected Completion Date: 0
    • Actual Completion Date: 19890000
    • Source Data: ITRD F502247

    Subject/Index Terms

    Filing Info

    • Accession Number: 01254781
    • Record Type: Research project
    • 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 7:34AM