Original title:
Problém optimalizácie trás s maximalizáciou úžitku
Translated title:
The team orienteering problem with utility maximisation
Authors:
Chocholáček, Ján ; Pelikán, Jan (advisor) ; Fábry, Jan (referee) Document type: Master’s theses
Year:
2014
Language:
slo Publisher:
Vysoká škola ekonomická v Praze Abstract:
[slo][cze][eng] Problém optimalizácie trás patrí medzi novšie problémy z oblasti diskrétneho programovania. Jeho formulácia vychádza zo športovej disciplíny, zvanej orientačný beh. V úvode práce je popísaná formulácia problému a jeho matematický model. Rozšírením tejto úlohy je problém tímovej optimalizácie trás, ktorému sa venujú ďalšie kapitoly teoretickej časti. Na riešenie problému bol publikovaný väčší počet heuristík, pričom táto práca podrobne rozoberá dve z nich, konkrétne heuristiku autorov Chao a kolektív a heuristiku autorov Souffriau a kolektív, nazvanú heuristika opakovaného spájania ciest. Praktická časť sa zaoberá aplikáciou problému tímovej optimalizácie trás na reálnu úlohu, návštevu 23 atrakcií v meste New York, počas rôzneho počtu dní. Riešenie úlohy je získané pomocou optimalizačného programu Lingo 90 a heuristiky autorov Chao a kolektív. Výpočet heuristiky bol implementovaný v jazyku Visual Basic for Aplication. Na záver práce sú získané riešenia navzájom porovnané.Problém optimalizace tras patří mezi novější problémy z oblasti diskrétního programování. Jeho formulace vychází ze sportovní discipliny, zvané orientační běh. V úvodu práce je popsaná formulace problému a jeho matematický model. Rozšířením této úlohy je problém týmové optimalizace tras, kterému se věnují další kapitoly teoretické části. Na řešení problému byl publikovaný větší počet heuristik, přičemž tato práce podrobně rozebírá dvě z nich, konkrétně heuristiku autorů Chao a kolektiv a heuristiku autorů Souffriau a kolektiv, nazvanou heuristika opakovaného spájení cest. Praktická část se zaobírá aplikací problému týmové optimalizace tras na reálnou úlohu, návštěvu 23 atrakcí v městě New York, během různého počtu dní. Řešení úlohy je získané pomocí optimalizačního programu Lingo 90 a heuristiky autorů Chao a kolektiv. Výpočet heuristiky byl implementovaný v jazyku Visual Basic for Application. Na závěr práce jsou získané řešení navzájem porovnána.The orienteering problem is one of the newer problems in the field of discrete programming. The formulation of this problem originates from a sport discipline, called orienteering. In the beginning of this thesis a formulation and mathematical model for this problem are introduced. The extension of the problem is the team orienteering problem, described in the next chapters of theoretical part. Many heuristics were published for this problem. While the heuristic of Chao et al. and a path relinking approach are described in detail in this thesis. Practical part deals with the team orienteering problem applied to a real task, specifically a visiting of 23 attractions in the New York in different number of days. The solution is found by optimization program Lingo 90 and by heuristic of Chao el al. Heuristic algorithm was implemented in programming language Visual Basic for Application. A comparison of the results is described at the end of the practical part.
Keywords:
A path relinking approach for the team orienteering problem; heuristic by Chao et al.; The orienteering problem; The team orienteering problem; Visual Basic for Application; heuristika autorů Chao a kolektiv; heuristika opakovaného spájení cest; problém optimalizace tras; problém týmové optimalizace tras; Visual Basic for Application
Institution: University of Economics, Prague
(web)
Document availability information: Available in the digital repository of the University of Economics, Prague. Original record: http://www.vse.cz/vskp/eid/46144