Aplikace speciálních metaheuristických metod na řešení okružního dopravního problému

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21220%2F14%3A00224136" target="_blank" >RIV/68407700:21220/14:00224136 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Aplikace speciálních metaheuristických metod na řešení okružního dopravního problému

Popis výsledku v původním jazyce

Cílem tohoto příspěvku je popsat vytvořenou metaheuristickou metodu, která slouží k rychlému a snadnému nalezení optimálního řešení (tj. nejkratší trasy) v okružním dopravním problému (úloze obchodního cestujícího). Metoda vychází z empirických pozorování a statistického vyhodnocování vzájemných vzdáleností mezi množinou bodů, pro které se hledá řešení okružního dopravního problému. Na základě empirických pozorování byla stanovena hypotéza říkající, že existuje kritická vzdálenost, kterou vzdálenosti cest ležících na optimální trase nepřekročí. Existence kritické vzdálenosti tak představuje kritérium výběru v metaheuristickém algoritmu, který přiřazuje cestám s délkou větší než kritickou nižší pravděpodobnost výskytu v optimálním řešení, což umožňuje nalézt výsledek při nižším počtu kroků. Byla prokázána funkčnost metody.

Název v anglickém jazyce

Aplication of special metaheuristic methods for the traveling salesman problem solving

Popis výsledku anglicky

The aim of this paper is to describe metaheuristic methods created to the quick and easy finding of the optimal solution (the shortest route) in Traveling Salesman Problem. The method is based on empirical observations and statistical evaluation of the distances among the set of points for which the solution of the Traveling Salesman Problem is looking for. On the basis of these observations, this hypothesis has been established - there is a critical distance which cannot be exceeded by the distances ofthe paths lying on the optimal route. The existence of a critical distance then functions as a selection criterion in metaheuristic algorithm that assigns to paths with a length greater than the critical one, lower probability of occurrence in the optimal solution. This enables to find the result in a lower number of steps. The functionality of our approach has been proven.

Druh

D - Stať ve sborníku

CEP obor

AH - Ekonomie

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2014

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ů

Název statě ve sborníku

5. mezinárodní Masarykova konference pro doktorandy a mladé vědecké pracovníky

ISBN

978-80-87952-07-8

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

259-268

Název nakladatele

MAGNANIMITAS

Místo vydání

Hradec Králové

Místo konání akce

Hradec Králové

Datum konání akce

15. 12. 2014

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—