Usage of the extremal algebra in solving the travelling salesman problem
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Usage of the extremal algebra in solving the travelling salesman problem
Original language description
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
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
O - Projekt operacniho programu
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Mathematical methods in economics : proceedings of 30th international conference
ISBN
978-80-7248-779-0
ISSN
—
e-ISSN
—
Number of pages
6
Pages from-to
733-738
Publisher name
Slezská univerzita. Obchodně podnikatelská fakulta
Place of publication
Karviná
Event location
Karviná
Event date
Jan 11, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000316715900126