Vybrané heuristiky pro TSP: Komparativní studie
| Název práce: | Vybrané heuristiky pro TSP: Komparativní studie |
|---|---|
| Autor(ka) práce: | Hrobař, Petr |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Černý, Michal |
| Oponenti práce: | Fábry, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | V této práci jsme studovali klasickou heuristiku TSP, nejbližšího souseda, ve dvoumodifikacích. Následne jsme se pokusili overit hypotézu, zda je možné tyto modifikaceaplikovat na skutecných datech a dosáhnout lepších výsledku (tj. méne vzdálenýchod optima), než užitím moderních heuristik z casopisecké literatury. Jako druhoustanovenou hypotézu jsme si stanovili, zda je možné nejbližšího souseda, v námistudovaných modifikacích, aplikovat na nove naformulované instance typu TSP-D.Merení byla provedena na datech z TSP library na 28 náhodne zvolených instancícha na umele generovaných instancích typu TSP-D. Na základe našich merení se námpodarilo první hypotézu prokázat. Tedy je možné v námi studovaných modifikacíchdosáhnout hodnot méne vzdálených od optima (s nárustem výpocetního casu). Druhouhypotézu o využitelnosti na instancích typu TSP-D se nám prokázat nepodarilo.Nakonec byl proveden návrh nové heuristické metody. |
| Klíčová slova: | TSP; nejbližší soused; 2-opt; (sub)optimum; TSP knihovna |
| Název práce: | Selected heuristics for TSP: a Comparative study |
|---|---|
| Autor(ka) práce: | Hrobař, Petr |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Černý, Michal |
| Oponenti práce: | Fábry, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | This thesis studies classical heuristic for TSP nearest neighbor in two modifications.Then we have set hypotheses, whether these modifications can be applied to realtesting data and achieve better results than by using modern heuristics from literature.As the second hypothesis, we wanted to verify whether it is possible to applythese modifications on newly defined TSP-D instances. Computations were executedon TSP library data on 28 randomly selected instances and on generated TSP-Dinstances. The conclusion is that the first hypotheses was proved. Modifications thatwe studied can generate better solutions (with the growth of computational time).Second Hypotheses regarding the application on TSP-D instances was not proved.Furthermore, we propose a new heuristic method. |
| Klíčová slova: | TSP; (sub)optimum; TSP library; nearest neighbor; 2-opt |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Typ studijního programu: | Bakalářský studijní program |
| Přidělovaná hodnost: | Bc. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 19. 2. 2019 |
|---|---|
| Datum podání práce: | 6. 5. 2019 |
| Datum obhajoby: | 17. 6. 2019 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/68753/podrobnosti |