Dokumentace k semestrální práci z předmětu PT
Vypracovali: Eva Turnerová (A08B0176P) Martin Dlouhý (A08B0268P)
• Zadání Zadání: Firma „Mistr Paleta, syn a vnuci“ rozváží palety po celé České republice. Počet odběrných míst v závislosti na ekonomickém cyklu kolísá mezi hodnotou 500 a 2000 a jedná se o větší sídla v ČR. Velikost sídla je důležitá vzhledem k množství palet, které může sídlo odebírat. Palety jsou z mateřské firmy rozváženy nákladními auty, každé auto může převézt maximálně šest palet. Firma si vzhledem k ekonomickému vývoji velmi hlídá dopravní náklady a zároveň čas, za který dokáže auto rozvést všechny palety a vrátit se zpět do podniku, používá tedy všechny využitelné dopravní cesty (z každého sídla vede minimálně 200 různých cest do jiných sídel). Při evidování cest jsou tedy důležité dvě hodnoty: čas, za jak dlouho dojede nákladní auto z jednoho sídla do druhého, a zároveň kilometrická vzdálenost sídel cestou spojených (odpovídá nákladům na přepravu). Není předem jasné, jestli jsou pro konkrétní náklad důležitější časové nebo přepravní náklady, jejich váha se může pro každý vyslaný náklad měnit. Vykládání jedné palety trvá přibližně 30 minut, každé sídlo může přijmout jednu až šest palet denně dle své velikosti. Sídla jsou schopná náklad s paletami přijímat obecně pouze v čase mezi osmou hodinou ranní a osmou hodinou večerní, přičemž platí, že v době oběda; tj. mezi jedenáctou a druhou hodinou odpolední; je schopnost sídel přijímat palety minimální. Dále platí, že pro každé sídlo je definován čas, kdy je schopné náklad s paletami přijmout; tento čas je souvislá denní doba o délce maximálně 90 minut (vykládací okénko), která může být na žádost dodavatele posunuta maximálně o půl hodiny. Základním požadavkem firmy „Mistr Paleta, syn a vnuci“ je optimalizovat rozvoz palet tak, aby byly dodrženy časy vykládky a zároveň byly respektovány ve zvoleném poměru minimální časové a kilometrické náklady na dopravu. Vytvoření funkčního programu: 1) Připravte rozumná vstupní data (sídla cesty, mezi nimi a ohodnocení) a uložte je ve vhodném formátu. 2) Zvolte a implementujte vhodnou datovou strukturu (y) pro reprezentaci vstupních dat, důsledně uvažujte paměťovou náročnost algoritmů pro následné vyhledávání optimálních cest 3) Zvolte vhodné algoritmy a proveďte následující simulaci (respektujte základní požadavek optimalizace rozvozu). Průběh simulace zapisujte na obrazovku a do souboru. Simulaci umožněte kdykoliv přerušit. 4) Vytvořte prostředí pro snadnou obsluhu programu (nemusí být grafické), ošetřete vstupy, umožněte zadání požadavku na rozvoz z klávesnice. 5) Umožněte sledování aktuální polohy nákladního vozu a aktuálního stavu obsluhy daného sídla. 6) Vypracujte statistiky rozvozu palet za jednotlivé dny, vhodně je uložte do souboru. 7) Vytvořte dokumentační komentáře ve zdrojovém textu a vygenerujte programovou dokumentaci (javadoc). 8) Vytvořte kvalitní, dále rozšiřitelný kód.
V rámci dokumentace: 1) 2) 3) 4) 5)
Připojte zadání Popište analýzu systému Popište návrh programu (jednoduchý UML diagram) Vytvořte uživatelskou dokumentaci Zhodnoťte celou práci, vyhodnoťte práci.
•
Analýza 1) Reprezentace měst a jejich spojení se sousedy Nejdříve jsme se museli nějak vymyslet kam uložit města a čím je reprezentovat. Nakonec jsme se rozhodli, že města uložíme do datové struktury, ve které budeme mít uloženo: počet objednaných palet, kdy chce město doručit objednávku a sousedi tohoto města. Když jsme toto vytvořily, nastal problém číslo dvě. Jak nejlépe reprezentovat graf. Nakonec jsme se rozhodli pro matici sousednosti, kde velikost matice je udána počtem měst a na jednotlivých indexech matice je buď 0 anebo číslo větší než nula reprezentující vzdálenost. Dále máme ještě jednu matici, která je skoro stejná jako naše matice sousednosti, ale jsou v ní uloženy časy mezi jednotlivými městy. 2) Průchod matice sousednosti Po vytvoření dvou matic, které nám reprezentovaly cestu mezi městy (graf). Jsme se rozhodovaly, jaký algoritmus bude nejlepší použít pro procházení matic. Nakonec jsme se rozhodly pro Dijkstrův algoritmus a to ze dvou důvodů. Prvním důvodem byla časová náročnost, která je menší než u FloydWarshallova algoritmu (O( ݊ଷ ) ). Dijkstrův algoritmus má časovou náročnost O(݊ଶ ). A druhý důvod je předchozí známost toho algoritmu. Velká nevýhoda toho algoritmu ale je, že pokud hledáme nejkratší cestu v grafu pro jednotlivá auta, musíme opakovaně procházet matici. 3) Simulace, přidělení objednávek a naplánování trasy Jedním z nejtěžších bodů vůbec byla samotná simulace a objednávky během dne. Simulace měla být diskrétní, což se nám nakonec podařilo. 4asový interval jsme po domluvě nadiskretizovaly po 30 minutách, což nám přišlo optimální z hlediska výpisů a informací o objednávkách a vykládkách aut. Po té, co si město objedná určitý počet palet ( od 1 do 6), se pokoušíme zjistit, zda tuto objednávku splníme do 20:00 pokud ne, zamítáme ji. Jednotlivým autům přiřazujeme objednávky než „vyjedou“. Trasu jim přiřazujeme do pole pomocí Dijkstrova algoritmu. Města, které mají objednáno a jsou přiřazená nějakým autům, obarvíme, aby nedošlo k případnému dovozu jedné objednávky více auty. 4) Objednávky měst během dne Nejdříve jsme si musely navrhnout křivku, která by reprezentovala pravděpodobnost přijetí objednávek během dne. Po té co jsme ji navrhnuly, vyvstal další problém. A to jak vyřešit samotné objednávky během dne. Vycházel jsem z diskrétní funkce ܨሺ = )ݔ300. logሺ1 − )ݖ, kde z je náhodně vygenerované číslo. Pokud toto číslo, překročí hodnotu 900 (což se může klidně stát) nastaví se F (x) na 900 (střední doba mezi jednotlivými objednávkami). Z pomocí této funkce a naší navržené křivky jsme pak mohly zjistit, kdy chce dané město doručit objednávku.
5) Rozdání objednávek Určitému autu přiřadíme objednávku a zjišťujeme, pokud je auto plné může vyjet. Pokud auto pojme ještě nějaké palety hledáme v seznamu měst, které si doposud objednaly. Posuzujeme, zda-li auto další objednávku ještě stihne a jestli objednávku ještě stihne splnit do dané doby, kterou si určí město. Auta ukládáme do spojového seznamu a pro každé auto je vytvořena datová struktura, do které se ukládají informace o autě ( stav, přes co jede, kolik palet veze, kam jede … ) 6) Simulační kalendář Protože výstupem souboru je chronologicky seřazená posloupnost informací o autech co se v daném okamžiku děje. Začátek simulace je v 6 hodin ráno, kdy si určitý počet měst objedná palety. Z důvodu diskrétní simulace se každá provedená akce provádí po půl hodinách. Každé auto, které v daný okamžik něco dělá, se vypisuje do souboru. Simulace končí právě, když se všechna města dostaví zpět do startu.
• Závěr Náš program měl simulovat rozvoz palet po určité síti měst, která se buďto vygeneruje sama anebo je zadána ve vstupním souboru. Celá simulace je diskrétní, což znamená, že úkony jsou provedeny v časových intervalech během dne. Problém bylo vymyslet simulaci a rozdělání objednávek. Rozdělení objednávek nám při první kontrole semestrální práce nefungovalo jak mělo ale simulace fungovala. Nyní už funguje tak, jak má.
