Original title:
Optimální plánování rozvozu pomocí dopravních prostředků
Translated title:
Vehicle Routing Problem
Authors:
Kafka, Ondřej ; Branda, Martin (advisor) ; Hanzák, Tomáš (referee) Document type: Master’s theses
Year:
2013
Language:
cze Abstract:
[cze][eng] Práce se zabývá optimalizačními problémy, které vznikají při plánování rozvozu pomocí dopravních prostředků. Tyto problémy lze často formulovat jednoduše jako úlohy celočíselného programování, ale málokdy je možné je řešit přímo technikami celočíselného programování. Proto je třeba zkoumat také schopnosti heuristických algoritmů. Hlavním zaměřením práce je rozvozní problém s časovými okny. Pro tento problém byl navržen a implementován algoritmus tabu prohledávání. Algoritmus využívá celočíselné programování při řešení dělícího problému za účelem nalezení optimálního rozdělení všech zákazníků do přípustných tras nalezených během vyhledávacího procesu. V numerické studii jsou porovnány výsledky postupů klasického celočíselného programování, jednoduché vkládací heuristiky a navrženého algoritmu tabu prohledávání.The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study.
Keywords:
heuristics; integer programming; tabu search; traveling salesman problem; vehicle routing problem; celočíselné programování; heuristiky; problém obchodního cestujícího; rozvozní problém; tabu prohledávání
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/55285