Original title: Problém obchodního cestujícího s časovými okny
Translated title: Traveling salesman problem with time windows
Authors: Pavlovič, Dávid ; Šoustek, Petr (referee) ; Dvořák, Jiří (advisor)
Document type: Master’s theses
Year: 2021
Language: slo
Publisher: Vysoké učení technické v Brně. Fakulta strojního inženýrství
Abstract: [slo] [eng]
Táto práca sa zaoberá riešením problému obchodného cestujúceho s časovými oknami. Problém spočíva v tom, že obchodný cestujúci musí prejsť každým definovaným miestom práve raz, a nakoniec sa vrátiť do pôvodného miesta za čo najnižšiu cenu trasy. Časové okná v tomto probléme definujú určité časové úseky, v ktorých môže byť každé konkrétne miesto navštívené, alebo sa môže stať, že v istom časovom úseku nebude existovať cesta medzi niektorými miestami. Práca sa zaoberá prehľadom tohto problému a problémov jemu podobných. Ďalej sa zaoberá popisom rôznych metód, ktorými tento problém možno riešiť. V rámci tejto práce bola tiež vytvorená aplikácia v programovacom jazyku Python, ktorá slúži na testovanie vybraných metód riešenia. Na záver sú vyhodnotené dané experimenty a porovnaná efektivita daných stratégií. This thesis deals with the Travelling salesman problem with time windows. The problem is that the travelling salesman must pass through each defined location exactly once and finally return to the original place for the lowest possible price. The time windows in this problem are that each place can only be visited in a given time range, or it can happen that in a certain period of time there will be no path between some places. The thesis deals with an overview of this problem and problems similar to it. It also deals with the description of various methods by which this problem can be solved. As part of this thesis, an application in the Python programming language was also created, which is used to test selected methods for finding solutions. Finally, the given experiments are evaluated and the effectiveness of the given strategies is compared.
Keywords: artificial intelligence algorithms; combinatorial optimization; planning; Travelling salesman problem with time windows

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/197399

Permalink: http://www.nusl.cz/ntk/nusl-590437


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses