Heuristiky pro kapacitní úlohy kurýrní služby
| Název práce: | Heuristiky pro kapacitní úlohy kurýrní služby |
|---|---|
| Autor(ka) práce: | Přibylová, Lenka |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Pelikán, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | Hlavním tématem této práce jsou statické a dynamické úlohy kurýrní služby s kapacitním omezením a jejich řešení heuristickými algoritmy. Uvažovány jsou různé varianty této úlohy, s jedním nebo více kurýry, pro více kurýrů s jediným výchozím místem nebo s různými výchozími místy pro jednotlivé kurýry. Další úpravou je zahrnutí časového limitu, ve kterém musí být všechna místa navštívena. K řešení jsou využity modifikace metody nejbližšího souseda, metody vkládací a metody výměn. Hlavním přínosem této práce je vytvoření heuristických algoritmů popsaných typů statických a dynamických úloh a jejich naprogramování v jazyce VBA (Visual Basic for Applications) v prostředí MS Excel. Výsledky výpočetních experimentů značí, že ve statických úlohách kurýrní služby s více kurýry s jedním výchozím místem vykazuje lepší výsledky modifikovaná metoda nejbližšího souseda, zatímco ve statických úlohách s více kurýry s různými výchozími místy dosahuje značně nižších hodnot účelové funkce modifikovaná vkládací metoda. Modifikovaná metoda výměn vede ke zlepšení nalezených řešení. Pro řešení dynamických úloh se v experimentech osvědčila více modifikovaná vkládací. |
| Klíčová slova: | modifikace metody výměn; modifikace vkládací metody; modifikace metody nejbližšího souseda; kurýrní problém s různými výchozími místy; heuristiky; dynamická úloha kurýrní služby; kapacitní úloha kurýrní služby s více kurýry |
| Název práce: | Heuristics for capacitated messenger problem |
|---|---|
| Autor(ka) práce: | Přibylová, Lenka |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Pelikán, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | This diploma thesis deals with static and dynamic capacitated messenger problem and its solving with heuristic algorithms. Different variations of the capacitated messenger problem were considered, with a single messenger or multiple messengers, with one depot or multiple depots in case of multiple messengers. Limited time for route realization was another modification that was considered. Modified nearest neighbour method, modified insertion method and modified exchange method were used to solve the problem. The main contribution of the thesis is deriving heuristics for described types of messenger problem and programming the algorithms in VBA (Visual Basic for Applications) in MS Excel. The results of computational experiments indicate that modified nearest neighbour method leads to better outcomes in static multiple messenger problems with a single depot, while modified insertion method is associated with lower values of objective function in static multiple messenger problem with multiple depots. Modified exchange method improves original solutions. Modified insertion method was approved for solving dynamic multiple messenger problems. |
| Klíčová slova: | modified exchange method; modified insertion method; modified nearest neighbour method; multiple messenger problem with multiple depots; heuristics; dynamic pickup and delivery problem; capacitated messenger problem |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| 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: | 4. 9. 2013 |
|---|---|
| Datum podání práce: | 2. 5. 2014 |
| Datum obhajoby: | 4. 6. 2014 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/45860/podrobnosti |