Abstrakt. Probabilistic Traveling Salesman Problem (PTSP) är ett TSP problem där varje kund har en given sannolikhet att kräva ett besök. Målet är att hitta en priori tour av minimal förväntad längd över alla kunder, med strategin att besöka en slumpmässig delmängd av kunder i samma ordning som de visas i en priori tour. Vi tar upp frågan om och i vilket sammanhang en förhandsvisning som finns av en TSP heurist också kan vara en bra lösning för PTSP. Vi besvarar denna fråga genom att testa den relativa prestandan hos två myrkolonioptimeringsalgoritmer, Ant Colony System (ACS) som införts av Dorigo och Gambardella för TSP, och en variant av det (pACS) som syftar till att minimera PTSP objektiv funktion. Vi visar i vilka sannolikhetskonfigurationer kunder pACS och ACS är lovande algoritmer för PTSP.
Bianchi m.fl. REF införde ACO för en annan version av TSP, den probabilistiska TSP, där varje kund har en given sannolikhet att kräva ett besök.
An ant colony optimization approach to the probabilistic traveling salesman problem
{'venue': 'Proceedings of the 7th International Conference on Parallel Problem Solving from Nature (PPSN VII', 'journal': None, 'mag_field_of_study': ['Computer Science']}