Vehicle Routing Problem, do českého jazyka překládaný jako víceokruhový dopravní problém patří mezi skupinu logistických úloh, které se věnuje operační výzkum. Tyto úlohy jsou sice řešitelné metodami celočíselného programování, avšak jen pro úlohy malého rozsahu. Proto se místo tzv. exaktních metod používají heuristické algoritmy. V této práci bude cílem naprogramovat aplikací pro řešení VRP založenou na Particle Swarm optimalizaci. PSO je jednou z nejnovějších heuristik a její ideje jsou inspirovány chováním letících ptáků. Základem pro rozdělení zákazníků do sektorů obsluhovaných jedním vozidlem bude dělení do kruhových výsečí, tzv. Wheel algoritmus. Nejdůležitější části metodiky budou detailně popsány, resp. prezentovány jejich kódy a digramy tříd definované ve vývojovém prostředí IntelliJ IDEA a jazyku Java. K posouzení kvality vytvořené aplikace budou provedeny výpočty v Solomonových testovacích úlohách. Experimentální část umožní vybrat vhodné vstupní parametry algoritmu.
Anotace v angličtině
Vehicle Routing Problem belongs to the group of logistical problems devoted to operational research. Although these tasks are solvable by integer programming methods, they are only solvable for small-dimensional problems. Therefore, heuristic algorithms are used instead of so-called exact methods. In this work, the goal will be to programme an application for VRP solutions based on Particle Swarm optimization. PSO is one of the newest heuristics and its ideas are inspired by the behaviour of flying birds. The Wheel algorithm, which is based on dividing customers into arc slide sectors and serving these sector customers with one vehicle. The most important parts of the methodology will be described in detail or presented with their codes and class diagrams as defined in the IntelliJ IDEA development environment and Java language. To assess the quality of the application created, calculations will be performed on Solomon testing problems. This experimental part will also allow you to select the appropriate settings for the algorithm's input parameters.
Klíčová slova
víceokruhový dopravní problém, problém obchodního cestujícího, optimalizace hejnem částic
Vehicle Routing Problem, do českého jazyka překládaný jako víceokruhový dopravní problém patří mezi skupinu logistických úloh, které se věnuje operační výzkum. Tyto úlohy jsou sice řešitelné metodami celočíselného programování, avšak jen pro úlohy malého rozsahu. Proto se místo tzv. exaktních metod používají heuristické algoritmy. V této práci bude cílem naprogramovat aplikací pro řešení VRP založenou na Particle Swarm optimalizaci. PSO je jednou z nejnovějších heuristik a její ideje jsou inspirovány chováním letících ptáků. Základem pro rozdělení zákazníků do sektorů obsluhovaných jedním vozidlem bude dělení do kruhových výsečí, tzv. Wheel algoritmus. Nejdůležitější části metodiky budou detailně popsány, resp. prezentovány jejich kódy a digramy tříd definované ve vývojovém prostředí IntelliJ IDEA a jazyku Java. K posouzení kvality vytvořené aplikace budou provedeny výpočty v Solomonových testovacích úlohách. Experimentální část umožní vybrat vhodné vstupní parametry algoritmu.
Anotace v angličtině
Vehicle Routing Problem belongs to the group of logistical problems devoted to operational research. Although these tasks are solvable by integer programming methods, they are only solvable for small-dimensional problems. Therefore, heuristic algorithms are used instead of so-called exact methods. In this work, the goal will be to programme an application for VRP solutions based on Particle Swarm optimization. PSO is one of the newest heuristics and its ideas are inspired by the behaviour of flying birds. The Wheel algorithm, which is based on dividing customers into arc slide sectors and serving these sector customers with one vehicle. The most important parts of the methodology will be described in detail or presented with their codes and class diagrams as defined in the IntelliJ IDEA development environment and Java language. To assess the quality of the application created, calculations will be performed on Solomon testing problems. This experimental part will also allow you to select the appropriate settings for the algorithm's input parameters.
Klíčová slova
víceokruhový dopravní problém, problém obchodního cestujícího, optimalizace hejnem částic
Při plánování rozvozu zboží z centrálních skladů vzníká logistická úloha VRP (Vehicle routing problem). Je třeba naplánovat nakládku zboží na vozidla a naplánovat rozvozní trasy s minimálními náklady. Tato úloha úzce souvisí s úlohou pro optimalizaci nakládky BPP (Bin Packing Problem) a okružní úlohou Travelling Salesman Problem (TSP).
Cílem práce je prostudovat různé přístupy pro řešení úlohy a naprogramovat řešení pro úlohu s více depy. Pro hledání řešení bude použita heuristika Particle Swarm Optimization. Důraz bude kladen na analýzu dopadů dělení zákazníků do sektorů na výslednou cenu dopravy a výpočetní náročnost. Pro dělení budou použity algoritmy Polar Region Partitioning, Rectangular Region Partitioning a metody shlukování. Zvolené optimalizační kritérium bude zahrnovat penalizaci nedodržení časových oken pro nakládku a vykládku zboží. Vytvořená aplikace umožní načítání dat s polohou zákazníků, vypočet matice vzdáleností a export výsledků (grafické znázornění linek, výčet vrcholů alokovaných na jednotlivé linky, doba jízdy).
V práci budou popsány veškeré aplikované metody a bude vysvětleno uživatelské prostředí aplikace.
Zásady pro vypracování
Při plánování rozvozu zboží z centrálních skladů vzníká logistická úloha VRP (Vehicle routing problem). Je třeba naplánovat nakládku zboží na vozidla a naplánovat rozvozní trasy s minimálními náklady. Tato úloha úzce souvisí s úlohou pro optimalizaci nakládky BPP (Bin Packing Problem) a okružní úlohou Travelling Salesman Problem (TSP).
Cílem práce je prostudovat různé přístupy pro řešení úlohy a naprogramovat řešení pro úlohu s více depy. Pro hledání řešení bude použita heuristika Particle Swarm Optimization. Důraz bude kladen na analýzu dopadů dělení zákazníků do sektorů na výslednou cenu dopravy a výpočetní náročnost. Pro dělení budou použity algoritmy Polar Region Partitioning, Rectangular Region Partitioning a metody shlukování. Zvolené optimalizační kritérium bude zahrnovat penalizaci nedodržení časových oken pro nakládku a vykládku zboží. Vytvořená aplikace umožní načítání dat s polohou zákazníků, vypočet matice vzdáleností a export výsledků (grafické znázornění linek, výčet vrcholů alokovaných na jednotlivé linky, doba jízdy).
V práci budou popsány veškeré aplikované metody a bude vysvětleno uživatelské prostředí aplikace.
Seznam doporučené literatury
*BELMECHERI, Farah, Christian PRINS, Farouk YALAOUI, Lionel AMODEO. Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. J Intell Manuf 24, 2013, s. 775-789.
*SIMCHI-LEVI, David, Xin ChEN, Julien BRAMEL. The logic of logistics: theory, algorithms, and applications for logistics management. Third edition. New York: Springer, 2014. 447 s. ISBN 9781461491484.
Seznam doporučené literatury
*BELMECHERI, Farah, Christian PRINS, Farouk YALAOUI, Lionel AMODEO. Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. J Intell Manuf 24, 2013, s. 775-789.
*SIMCHI-LEVI, David, Xin ChEN, Julien BRAMEL. The logic of logistics: theory, algorithms, and applications for logistics management. Third edition. New York: Springer, 2014. 447 s. ISBN 9781461491484.
Přílohy volně vložené
CD ROM
Přílohy vázané v práci
grafy, schémata, tabulky
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Předložená závěrečná práce se věnuje řešení logistické úlohy Vehicle Routing Problem (VRP). Aplikace je realizována v jazyku JAVA s využitím vývojového prostředí IntelliJ IDEA. Vytvořená aplikace umožňuje, dle vedoucího práce, načtení a zadávání vstupních údajů: souřadnic bodů, časových oken pro doručení objednávky, velikosti objednávek. Text práce hodnotil vedoucí jako velmi přehlendý a je vhodně prokládán obrázky. I při prezentaci dilpomové práce reagoval student výborně na připomínky a dotazy vedoucího, oponenta i členů komise. Dle oponenta byly cíle práce naplněny v plném rozsahu. Práce je zpracována přehledně.