Problém obchodního cestujícího

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26220%2F23%3APR37765" target="_blank" >RIV/00216305:26220/23:PR37765 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.ueen.fekt.vut.cz/problem-obchodniho-cestujiciho" target="_blank" >https://www.ueen.fekt.vut.cz/problem-obchodniho-cestujiciho</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Problém obchodního cestujícího

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Traveling salesman problem

Popis výsledku anglicky

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.

Druh

R - Software

CEP obor

—

OECD FORD obor

20201 - Electrical and electronic engineering

Projekt

<a href="/cs/project/TK04020003" target="_blank" >TK04020003: Užití umělé inteligence při modernizaci diagnostiky systémových prvků a optimalizaci systémových činností energetického sektoru s cílem zvýšení kvality jeho řízení</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

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ů

Interní identifikační kód produktu

MODIAS3

Technické parametry

Algoritmy aktivní dynamiky Hopfieldovy neuronové sítě a iteračního procesu simulovaného žíhání řešící problém obchodního cestujícího ve formě dynamicky linkovaných knihoven integrovatelných do aplikace vytvořené v prostředí Microsoft Visual Studia. Jako programovací jazyk algoritmizace výpočtů byl užit Intel Fortran vhodný pro kódování vědecko-technických numerických výpočtů.

Ekonomické parametry

Úspory dopravních nákladů.

IČO vlastníka výsledku

00216305

Název vlastníka

Vysoké učení technické v Brně