Algorithm for Travelling Salesman Problem
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F63468352%3A_____%2F15%3A%230000463" target="_blank" >RIV/63468352:_____/15:#0000463 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/63468352:_____/15:#0000434 RIV/00216305:26110/15:PU113673
Výsledek na webu
<a href="http://dx.doi.org/10.1201/b18238-19" target="_blank" >http://dx.doi.org/10.1201/b18238-19</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1201/b18238-19" target="_blank" >10.1201/b18238-19</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Algorithm for Travelling Salesman Problem
Popis výsledku v původním jazyce
The paper describes a new algorithm for finding the shortest path in the graph among all nodes. The algorithm is based on the sequential removing of nodes from the graph. After removing a node, it is ne-cessary to generate new edges that represent all paths through the node. This procedure maintains the configu-ration of the graph. The newly created edges are referred to as composed edges. The newly generated edges can be connected together only with simple (original) edges, because this could lead to overlaping the edges of the original graph and thus may occur incorrect paths in the graph. During the algorithm proceeds the con-tinuous optimization of the edges so that it removes loops around the nodes. This leads to a significant re-duction of the number of combinations of edges, and it simplifies the process. The algorithm was tested tho-ugh procedure in Python and its complexity is polynomial time. The job is known as a problem of a Salesman or a Hamiltonian path or Hamiltonian circle in the graph. Results of proposed method can be used in logistics (distribution of goods among locations), in transport planning (selection of the optimal route between given points) in crisis management (optimal route for intervention in case of fire or accidents) in tourism and related services (planning the shortest route trip) or spatial analyses in geographic information systems (GIS).
Název v anglickém jazyce
Algorithm for Travelling Salesman Problem
Popis výsledku anglicky
The paper describes a new algorithm for finding the shortest path in the graph among all nodes. The algorithm is based on the sequential removing of nodes from the graph. After removing a node, it is ne-cessary to generate new edges that represent all paths through the node. This procedure maintains the configu-ration of the graph. The newly created edges are referred to as composed edges. The newly generated edges can be connected together only with simple (original) edges, because this could lead to overlaping the edges of the original graph and thus may occur incorrect paths in the graph. During the algorithm proceeds the con-tinuous optimization of the edges so that it removes loops around the nodes. This leads to a significant re-duction of the number of combinations of edges, and it simplifies the process. The algorithm was tested tho-ugh procedure in Python and its complexity is polynomial time. The job is known as a problem of a Salesman or a Hamiltonian path or Hamiltonian circle in the graph. Results of proposed method can be used in logistics (distribution of goods among locations), in transport planning (selection of the optimal route between given points) in crisis management (optimal route for intervention in case of fire or accidents) in tourism and related services (planning the shortest route trip) or spatial analyses in geographic information systems (GIS).
Klasifikace
Druh
C - Kapitola v odborné knize
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
N - Vyzkumna aktivita podporovana z neverejnych zdroju
Ostatní
Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název knihy nebo sborníku
The Role of Service in the Tourism & Hospitality Industry
ISBN
978-1-315-68852-7
Počet stran výsledku
5
Strana od-do
107-111
Počet stran knihy
237
Název nakladatele
CRC Press, Taylor & Francis
Místo vydání
Londýn
Kód UT WoS kapitoly
—