Přejít k hlavnímu obsahu

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Searching the Hyper-heuristic for the Traveling Salesman Problem with Time Windows by Genetic Programming
Rok: 2020
Druh publikace: článek ve sborníku
Název zdroje: Intelligent Systems and Applications : proceedings of the 2020 Intelligent Systems Conference (IntelliSys), Volume 1
Název nakladatele: Springer Nature Switzerland AG
Místo vydání: Cham
Strana od-do: 939-946
Tituly:
Jazyk Název Abstrakt Klíčová slova
cze Hledání hyperheuristiky pro problém obchodního cestujícího s časovými okny pomocí genetického programování Tento článek se zaměřuje na řešení problému obchodního cestujícího s časovými okny nepřímým způsobem nalezením užitečné hyperheuristiky pomocí genetického programování. Výsledná hyperheuristika představuje výpočet priority města na cestě obchodního cestujícího. Vlivy různých vlastností města (poloha v kartézském souřadnicovém prostoru, součet vzdáleností k nejbližším městům, polární úhel od začátku souřadného systému atd.), Matematické funkce (sčítání, odčítání, dělení, sinus, kosinus, tečna) a jsou testovány penalizační funkce. Trigonometrické funkce nemají žádný pozitivní vliv, nejlepších výsledků je dosaženo kartézskými souřadnicemi a součtem vzdáleností k nejbližším městům. Polární úhel poskytuje rozmanitější řešení. Výsledná hyperheuristika je dobrá na tréninkových sadách. Když jsou testovány na jiných datových sadách, najdou relativně krátké cesty, ale existují problémy s respektováním omezení ve formě časových oken. Genetické programování, hyperheuristika, problém obchodního cestujícího s časovými okny, enkodéry
eng Searching the Hyper-heuristic for the Traveling Salesman Problem with Time Windows by Genetic Programming This paper focuses on the solving constrained traveling salesman problem with time windows indirectly by finding useful hyper-heuristic via genetic programming. Resulting hyper-heuristic represents calculation of city priority along the traveling salesman path. The influences of different city properties (position in the Cartesian coordinate space, sum of distances to then nearest cities, polar angle from the beginning of the coordinate system, etc.), math functions (addition, subtraction, division, sine, cosine, tangent) and penalty functions are tested. Trigonometric functions have no positive influence, best results are achieved with Cartesian coordinates and sum of distances to the nearest cities. Polar angle gives more diverse solutions. Resulting hyperheuristics are good on training sets. When they are tested on another datasets, they find relatively short paths, but there are problems with respecting constraints in the form of time windows. Genetic Programming, Hyper-heuristics, Traveling Salesman Problem with Time Windows, Encoder