UP - logo
Library of Technical Faculties, Maribor (KTFMB)
  • On the probabilistic traveling salesman problem
    Žerovnik, Janez, 1958- ; Brest, Janez
    Verjetnostni trgovski potnik je problem trgovskega potnika, pri katerem je množica točk, ki jih mora obiskati, verjetnostna spremenljivka. Za primer privzemimo, da podjetje želi nažrtovati obhod ... ▫$n$▫ strank z minimalnimi stroški. Če je treba vse stranke obiskati vsakič, je to običajni problem trgovskega potnika. Če je podmnožica strank vsak dan drugačna, je naloga določiti obhod, pri katerem bo pričakovani (povprečni) strošek minimalen. PTSP je NP-težek problem, ker je posplošitev TSP. Vemo tudi, da je optimalna TSP rešitev lahko poljubno slaba rešitev za PTSP. V prispevku je predstavljena verjetnostna hevristika; ponovitve naključne konstrukcije poti, ki ji sledi lokalna optimizacija. Dodani so rezultati poskusov.
    Source: Proceedings of the 17th International Conference on Mathematical methods in Economics '99 (Str. 289-295)
    Type of material - conference contribution
    Publish date - 1999
    Language - english
    COBISS.SI-ID - 9035609

Shelf entry