VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • A comparative study of the nearest neighbor and arbitrary insertion for the travelling salesman problem
    Balantič, Karmen ...
    In the paper, the Travelling Salesman Problem (TSP) is being discussed. TSP is a problem, where the salesman visits all the cities exactly once and then returns to the starting point, while the ... shortest path is being travelled. The problem is NP-hard, since the difficulty of solving procedure arises with the increase of the number of cities being visited. For TSP solving, there are many heuristic algorithms, which return relatively good solutions but not necessarily optimal. In the paper two algorithms, Nearest Neighbor (NN) and Arbitrary Insertion (AI) are tested taking into account a security company case. We consider the Euclidian distances between the nodes and the actual street network distances. Case study shows that both algorithms returns the same sequence if we consider Euclidian distances, while using actual distances the better result corresponds to the use of AI algorithm.
    Vir: Pre-conference proceedings of the 11th International Conference on Logistics & Sustainable Transport 2014, Celje, Slovenia, 19-21 June 2014 [Elektronski vir] ([6] str.)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2014
    Jezik - angleški
    COBISS.SI-ID - 512578621

Vnos na polico