Usage of the extremal algebra in solving the travelling salesman problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F62690094%3A18450%2F12%3A50001880" target="_blank" >RIV/62690094:18450/12:50001880 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Usage of the extremal algebra in solving the travelling salesman problem

Popis výsledku v původním jazyce

This article compares many ways of solving the traveling salesman problem. At first classical heuristic methods and methods using graph theory are mentioned. At the first part many universal methods are described, which can be also used in other transportation problems. The traveling salesman problem is solved by using genetic algorithm in the second part of this article. This algorithm generates at the beginning the first generation, chooses five thousand parents by the roulette method, crosses these pairs and determines the next generation. This process continues with next generations until stabilization. The algorithm is demonstrated on two examples. At the final part extremal algebras, max-plus algebra and max-min algebra, are defined and illustrated by examples. Monge matrices and some their properties are described in these algebras. The optimization of the traveling salesman problem, which leads to a reduction of the computation complexity, is described for these matrices. The o

Název v anglickém jazyce

Usage of the extremal algebra in solving the travelling salesman problem

Popis výsledku anglicky

This article compares many ways of solving the traveling salesman problem. At first classical heuristic methods and methods using graph theory are mentioned. At the first part many universal methods are described, which can be also used in other transportation problems. The traveling salesman problem is solved by using genetic algorithm in the second part of this article. This algorithm generates at the beginning the first generation, chooses five thousand parents by the roulette method, crosses these pairs and determines the next generation. This process continues with next generations until stabilization. The algorithm is demonstrated on two examples. At the final part extremal algebras, max-plus algebra and max-min algebra, are defined and illustrated by examples. Monge matrices and some their properties are described in these algebras. The optimization of the traveling salesman problem, which leads to a reduction of the computation complexity, is described for these matrices. The o

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

O - Projekt operacniho programu

Rok uplatnění

2012

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

Mathematical methods in economics : proceedings of 30th international conference

ISBN

978-80-7248-779-0

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

733-738

Název nakladatele

Slezská univerzita. Obchodně podnikatelská fakulta

Místo vydání

Karviná

Místo konání akce

Karviná

Datum konání akce

11. 1. 2012

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

WRD - Celosvětová akce

Kód UT WoS článku

000316715900126