Tato práce se zabývá matematickými problémy z oblasti dopravní logistiky, jejichž řešení vedou na NP-těžké úlohy.
Konkrétně jsou studovány Problém naplnění zásobníků, Problém obchodního cestujícího a Problém rozvozní úlohy.
Nalezení minima, respektive alespoň jeho kvalitní aproximace pomocí heuristických algoritmů umožňuje minimalizovat náklady při distribuci zboží z centrálních skladů ke koncovým zákazníkům.
Anotace v angličtině
This diploma thesis describes problems of logistic that theirs result passes to NP-hard problems.
Specifically studies problems are Bin Packing Problem, Traveling Salesman problem and Vehicle Routing Problem.
To finding minimum or at least a good approximation that uses heuristic algorithms allows minimalizing costs of distributing goods from central warehouse to the end customers.
Klíčová slova
Problém naplnění zásobníků, Problém obchodního cestujícího, Problém rozvozní úlohy
Klíčová slova v angličtině
Bin Packing Problem, Traveling Salesman Problem, Vehicle Routing Problem
Rozsah průvodní práce
60 s. (80 529)
Jazyk
CZ
Anotace
Tato práce se zabývá matematickými problémy z oblasti dopravní logistiky, jejichž řešení vedou na NP-těžké úlohy.
Konkrétně jsou studovány Problém naplnění zásobníků, Problém obchodního cestujícího a Problém rozvozní úlohy.
Nalezení minima, respektive alespoň jeho kvalitní aproximace pomocí heuristických algoritmů umožňuje minimalizovat náklady při distribuci zboží z centrálních skladů ke koncovým zákazníkům.
Anotace v angličtině
This diploma thesis describes problems of logistic that theirs result passes to NP-hard problems.
Specifically studies problems are Bin Packing Problem, Traveling Salesman problem and Vehicle Routing Problem.
To finding minimum or at least a good approximation that uses heuristic algorithms allows minimalizing costs of distributing goods from central warehouse to the end customers.
Klíčová slova
Problém naplnění zásobníků, Problém obchodního cestujícího, Problém rozvozní úlohy
Klíčová slova v angličtině
Bin Packing Problem, Traveling Salesman Problem, Vehicle Routing Problem
Zásady pro vypracování
Dnešní doba je charakteristická obrovskou nabídkou zboží na trhu a proto se dostává logistika do popředí zájmu většiny společností. Cílem práce bude vytvořit aplikaci s řešení významné logistické úlohou, zvanou Vehicle Routing Problem (VRP). Tato úloha má za cíl mimimalizaci nákladů spojených s přepravou zboží z firemního skladu k zákazníkům. S VRP úzce souvisí úloha naplňování zásobníku (Bin Packing Problem - BPP) a problém obchodního cestujícího (Traveling Salesman Problem - TSP). Všechny tyto problémy mají společnou tu vlastnost, že obecně nelze nalézt jejich optimální řešení. Nicméně existují různé heuristické algoritmy. Konkrétně budou naprogramovány metody First-Fit, First-Fit Decreasing, Best-Fit, Best-Fit Decreasing pro úlohu BPP. U úlohy VRP budou do programu implementovány metody Polar Region Partitioning, Rectangular Region Partitioning. Pro řešení TSP může být využita aplikace pro Google maps, viz http://www.tsp.gatech.edu/maps/index.html resp. může být naprogramován např. algoritmus 2-opt. Aplikace bude obsahovat výsledky simulací, které budou demonstrovat, jak použité metody umožní co nejoptimálněji umísťovat náklad o různé velikosti např. do nákladních automobilů a jak vhodně přidělit zákazníky k jednotlivým automobilům při co nejmenší ujeté vzdálenosti.
Zásady pro vypracování
Dnešní doba je charakteristická obrovskou nabídkou zboží na trhu a proto se dostává logistika do popředí zájmu většiny společností. Cílem práce bude vytvořit aplikaci s řešení významné logistické úlohou, zvanou Vehicle Routing Problem (VRP). Tato úloha má za cíl mimimalizaci nákladů spojených s přepravou zboží z firemního skladu k zákazníkům. S VRP úzce souvisí úloha naplňování zásobníku (Bin Packing Problem - BPP) a problém obchodního cestujícího (Traveling Salesman Problem - TSP). Všechny tyto problémy mají společnou tu vlastnost, že obecně nelze nalézt jejich optimální řešení. Nicméně existují různé heuristické algoritmy. Konkrétně budou naprogramovány metody First-Fit, First-Fit Decreasing, Best-Fit, Best-Fit Decreasing pro úlohu BPP. U úlohy VRP budou do programu implementovány metody Polar Region Partitioning, Rectangular Region Partitioning. Pro řešení TSP může být využita aplikace pro Google maps, viz http://www.tsp.gatech.edu/maps/index.html resp. může být naprogramován např. algoritmus 2-opt. Aplikace bude obsahovat výsledky simulací, které budou demonstrovat, jak použité metody umožní co nejoptimálněji umísťovat náklad o různé velikosti např. do nákladních automobilů a jak vhodně přidělit zákazníky k jednotlivým automobilům při co nejmenší ujeté vzdálenosti.
Seznam doporučené literatury
Simchi-Levi D., Bramel J., Chen X.: The Logic of Logistics, Springer-Verlag, New York, (2004)
Garey M. R., Graham R. L., Johnson D.S., Yao A.: Resource constrained scheduling as generalized bin packing, J. Combinatorial Theory Ser. A, 21 (1976)
Baker B. S.: A New Proof for the First-Fit Decreasing Bin Packing Algorithm. J. Algorithms 6 (1985)
Seznam doporučené literatury
Simchi-Levi D., Bramel J., Chen X.: The Logic of Logistics, Springer-Verlag, New York, (2004)
Garey M. R., Graham R. L., Johnson D.S., Yao A.: Resource constrained scheduling as generalized bin packing, J. Combinatorial Theory Ser. A, 21 (1976)
Baker B. S.: A New Proof for the First-Fit Decreasing Bin Packing Algorithm. J. Algorithms 6 (1985)
Přílohy volně vložené
1 CD
Přílohy vázané v práci
-
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Cílem diplomové práce byl návrh a vytvoření aplikace pro řešení logistické úlohy Vehicle Routing Problem (VRP). Cílem této logistické úlohy je minimalizace nákladů na přepravu zboží z distribučního skladu k zákazníkovi. Autor splnil cíle práce. Prokázal solidní znalosti problému logistiky a teorie grafů, které dokázal ve vytvořené aplikaci použít. Výsledná aplikace je funkční a použitelná v praxi. Student zodpověděl všechny připomínky a dotazy členů komise.