Problém obchodního cestujícího

Traveling salesman problem

Software

Algoritmy aktivní dynamiky Hopfieldovy neuronové sítě uskutečňující gradientní sestup po spádu energetické funkce sítě a iteračního procesu simulovaného žíhání permutací uzlů grafu ve formě dynamicky linkovaných knihoven. Problém obchodního cestujícího je NP obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi vrcholy ohodnoceného grafu. V praxi se podobná úloha obvykle řeší pouze přibližně heuristickými algoritmy, např. genetickými algoritmy, simulovaným žíháním či spojitou Hopfieldovou sítí. Tím se (za cenu vzdání se nároku na nalezení optimálního řešení) dosahuje prakticky použitelných časů. Lze jej např. užít k optimalizaci pořadí návštěv různých zařízení z důvodu jejich revize s ohledem na dopravní náklady revizora.

Active Hopfield neural network dynamics algorithms implementing gradient descent with gradient energy function of the network and simulated annealing of graph node permutations in the form of dynamically linked libraries. The traveling salesman problem is an NP-hard discrete optimization problem, mathematically expressing and generalizing the problem of finding the shortest possible path passing through all vertices of a ranked graph. In practice, such a problem is usually solved only approximately by heuristic algorithms such as genetic algorithms, simulated annealing or continuous Hopfield networks. This achieves (at the cost of giving up the claim of finding an optimal solution) practical times. It can be used, for example, to optimize the order of visits to different facilities for the purpose of revising them with respect to the reviser's transport costs.

Traveling Salesman Problem; Hopfield Neural Network; Simulated Annealing

Traveling Salesman Problem; Hopfield Neural Network; Simulated Annealing

Ústav elektroenergetiky, FEKT, VUT v Brně, Technická 12, Brno 61600

K využití výsledku jiným subjektem je vždy nutné nabytí licence

https://www.ueen.fekt.vut.cz/problem-obchodniho-cestujiciho