Mendelova univerzita v Brně Agronomická fakulta Ústav techniky a automobilové dopravy
Optimalizace svozové trasy odpadu Bakalářská práce
Schválil:
Vypracoval:
Doc. RND. Stanislav Bartoň, CSc.
Milan Konečný Brno 2012
PROHLÁŠENÍ Prohlašuji, že jsem diplomovou práci na téma Optimalizace svozové trasy odpadu vypracoval samostatně a použil jen pramenů, které cituji a uvádím v přiloženém seznamu literatury. Diplomová práce je školním dílem a může být použita ke komerčním účelům jen se souhlasem vedoucího diplomové práce a děkana Agronomické fakulty Mendelovy univerzity v Brně.
dne ………………………………………. podpis diplomanta ……………………….
PODĚKOVÁNÍ
Rád bych poděkoval vedoucímu bakalářské práce Doc. RNDr. Stanislavu Bartoňovi, CSc. za jeho přístup, cenné rady, trpělivost a připomínky které mi velice pomohly při zpracování mé bakalářské práce.
ABSTRAKT V bakalářské práci je teoreticky popsána a prakticky vypočtena optimalizace svozové trasy odpadu pro vybranou městskou část za pomoci matematického programu MAPLE. Okrajově je v práci zmíněná příslušná legislativa spojená s odpady, svozem odpadů a jejich uložením. Jsou zde zmíněny současné přístupy k separaci, nejčastěji separované druhy odpadů a způsob svozu těchto odpadů v současných podmínkách. Dále se zabýváme druhy sběrů odpadů, jejich charakteristikami a orientačními náklady u každého z nich. Detailně je v bakalářské práci zachycen postup výpočtu optimalizace svozové trasy odpadu. Je zde vysvětlen problém obchodního cestujícího, který je pro uvažovaný výpočet trasy zásadní a jsou zde navrhnuty a vysvětleny možné způsoby řešení tohoto problému se zaměřením na vybraný způsob výpočtu pomocí programu Maple. Klíčová slova: Separace odpadů, svoz odpadů, optimalizace svozové trasy odpadu, problém obchodního cestujícího
ABSTRACT This text is focused on theoreticall and practicall calculation of optimization route for collecting waste for the selected part of the city with the help of mathematical program MAPLE. Marginally, there are basics of legislation for waste separation. Marginally in the work is mentioned of relevant legislation related to waste management, waste removal and placement. There are currently discussed approaches to separation, usually separated waste streams and method of collection of waste in the current conditions. We also deal with waste collection types, their characteristics and indicative costs for each of them. Detail is captured in the thesis optimization procedure to calculate the route collecting waste. It is explained here traveling salesman problem, which is under consideration for the calculation of the critical path and are designed and explained possible ways to address this problem by focusing on the selected method of calculation using Maple. Keywords: Separation of waste, trash removal, route optimization collecting waste, the traveling salesman problem
1
ÚVOD- LITERÁRNÍ PŘEHLED................................................................... 8 1.1 Proč separovat odpady .............................................................................. 8 1.1.1 Značky na obalech odpadů ...................................................................................... 9
1.2 Druhy separovaných odpadů ................................................................... 10 1.2.1 1.2.2 1.2.3 1.2.4 1.2.5
2 3
Separace skla ......................................................................................................... 11 Separace PET lahví ............................................................................................... 11 Možnosti využití recyklátu z PET lahví ................................................................ 12 Separace papíru ..................................................................................................... 12 Separace textilu ..................................................................................................... 13
LEGISLATIVA ODPADOVÉHO HOSPODÁŘSTVÍ ................................ 13 STÁVAJÍCÍ STAV SVOZU ODPADŮ ....................................................... 14 3.1 Způsob svozu........................................................................................... 14 3.2 Podrobnosti o systému nakládání s odpady ............................................ 15 3.2.1 Sběr nápojových kartonů ....................................................................................... 16
4
DRUHY SBĚRŮ........................................................................................... 17 4.1 Sběr ve směsi s jinou komoditou ............................................................ 17 4.1.1 Charakteristika systému ......................................................................................... 17 4.1.2 Orientační náklady ................................................................................................. 17
4.2 Sběr do samostatných nádob ................................................................... 18 4.2.1 Charakteristika systému ......................................................................................... 18 4.2.2 Orientační náklady ................................................................................................. 19
4.3 Sběr pytlový ............................................................................................ 19 4.3.1 Charakteristika systému ......................................................................................... 19 4.3.2 Orientační náklady ................................................................................................. 20
4.4
Sběr školní .............................................................................................. 20
4.4.1 Charakteristika systému ......................................................................................... 21 4.4.2 Orientační náklady ................................................................................................. 21
4.5 4.6
Možnosti zpracování nápojových kartonů ............................................. 21 Operátor .................................................................................................. 22
4.6.1 Informační a materiálová podpora ........................................................................... 23
5 6
SVOZOVÁ TRASA ..................................................................................... 23 OPTIMALIZACE SVOZOVÉ TRASY ODPADU ..................................... 24 6.1 Teorie – problém obchodního cestujícího.................................................. 24 6.2 Obtížnost .................................................................................................... 24 6.3 Ilp formulace .............................................................................................. 25
6.4 Možné způsoby řešení ................................................................................ 25 6.5 Zvolená metoda pro řešení problému........................................................ 25 7 OPTIMALIZACE SVOZOVÉ TRASY ODPADU POMOCÍ MATEMATICKÉHO PROGRAMU MAPLE ............................................ 26 7.1 Základní popis programu MAPLE ............................................................ 26 7.2 Optimalizace svozové trasy odpadu v programu MAPLE ....................... 28 8 ZÁVĚR ......................................................................................................... 41 9 SEZNAM POUŽITÉ LITERATURY.......................................................... 42 10 SEZNAM TABULEK A OBRÁZKŮ ......................................................... 44 11 PŘÍLOHA ..................................................................................................... 45
1 ÚVOD – LITERÁRNÍ PŘEHLED V dnešní moderní době, kdy vzniká stále větší množství odpadů se stalo velmi důležitým tématem jejich účinné zpracování. Vzhledem k velkému objemu vytvořených odpadů vzniká problém s jejich účinným shromažďováním a nakládáním. V první kapitole se věnuji především separaci odpadů a legislativní opoře v zákoně. Následuje kapitola, ve které se věnuji stávajícímu způsobu svozu odpadů a osvětluji, proč jsem vybral svozovou trasu PET lahví na území městské části Brno – Sever. V třetí a čtvrté kapitole se věnuji teoreticky a prakticky optimalizaci svozové trasy odpadu včetně vysvětlení jednotlivých kroků výpočtu.
1.1 Proč separovat odpady Způsoby nakládání s odpady dle vlivu na životní prostředí mají toto pořadí: 1. Omezování vzniku (minimalizace) odpadů - už při nákupu rozhodujeme, kolik odpadů vyprodukujeme 2. Třídění a recyklace odpadů - pokud se odpad smíchá, není možné ho již dále roztřídit a zpracovat, proto je nutné třídit odpady již v domácnostech 3. Odstraňování odpadů - odpady, které nemůžeme již dále využít se zneškodňují (např. skládkováním) Každý z nás vyhodí za rok asi 150 - 200 kg odpadů. Pokud však odpady už doma třídíme a dáváme je do barevných kontejnerů, umožníme tak recyklaci více než třetiny tohoto množství. Za rok tak můžeme vytřídit až 30 kg papíru, 25 kg plastů, 15 kg skla. Pokud se budou jednotlivé druhy odpadů správně třídit, umožní se tak jejich další zpracování. Odpady, které budou vhozeny do správných nádob - do barevného kontejneru, odveze velké svozové auto na dotřiďovací linku. Odtud putují do zpracovatelských firem, kde z odpadů vznikají nové výrobky - tento proces se nazývá recyklace odpadu. Při recyklaci jsou zpracovány odpady na nové materiály. Je důležité dodržovat pravidla třídění odpadů.
8
1.1.1 Značky na obalech odpadů Každý obal je vyroben z nějakého materiálu a někdy je velmi obtížné poznat, z čeho je obal vyroben. Proto jsou na obalech různé značky, které nás informují, jak máme s takovým obalem po použití naložit.
Šipky s číslem nebo zkratkou nás informují o materiálu, z něhož je obal vyroben. Podle nich poznáme, do kterého kontejneru máme obal později vyhodit. V tabulce jsou nejčastější kódy: Tabulka č. 1: Tabulka materiálů a jejich písmenných a číselných kódů Materiál
Písmenný kód
Číselný kód
Papír
PAP
22
Vlnitá lepenka
PAP
20
Hladká lepenka
PAP
21
Bílé sklo
GL
70
Zelené sklo
GL
71
Hnědé sklo
GL
72
Ocel
FE
40
Hliník
ALU
41
Dřevo
FOR
50
Polyethylentereftalát
PET
1
Polypropylén
PP
5
Polystyrén
PS
6
Polyetylén (rozvětvený)
LDPE
4
Polyetylén (lineární)
HDPE
2
Kombinovaný obal
C/
obal je vyroben z více materiálů a ten za lomítkem převládá
Nápojový karton
C/PAP
81 a 84 kombinovaný obal, kde převládá papír
9
Panáček s košem znamená, že použitý obal máme hodit do příslušné nádoby na odpad. Pokud se jedná o obaly od chemických výrobků, přečtěte si informace od výrobce, zda obal nevyžaduje specifický způsob nakládání. Pokud obsahuje nějaké nebezpečné látky, odnáší se do sběrny nebezpečných odpadů nebo na sběrné dvory. Bližší informace se dozvíte na vašem obecním nebo městském úřadu.
Zelený bod znamená, že je za obal zaplaceno do systému EKO-KOM, jenž zajišťuje sběr a využití obalových odpadů. Pokud si koupíte obal, na kterém je značka ZELENÝ BOD znamená to, že výrobce zaplatil za jeho recyklaci. Takže, až vypijete limonádu nebo dojíte sušenky, odhoďte jejich obaly do barevného kontejneru.
1.2 Druhy separovaných odpadů Mezinárodní norma zatím nebyla přijata. Značně se shoduje užívání zelené, bílé, žluté a černé barvy. Částečně také modré, červené, hnědé a stříbrné. Fialová byla zvolena Institutem informačního designu podle celkové analýzy. Užití jednotlivých tónů částečně vychází z koncepce, při níž má barva kontejneru souvislost s barvou suroviny. Tabulka č. 2: Rozdělení separovaných odpadů podle barvy Bílá
Nebarevné sklo
Zelená
Barevné sklo
Modrá
Papír
Žlutá
Umělé hmoty
Červená
Nebezpečný odpad (baterie, léky, ...)
Stříbrná
Nápojové plechovky
Hnědá
Organický odpad
Černá
Zbytkový smíšený odpad
Fialová
Slovy popsaný zvláštní druh odpadu např. textil apod. 10
Třídění odpadu je natolik závažný problém, že není možné spoléhat pouze na informační možnosti barevného řešení kontejnerů. Je nezbytné použít také nápis v česko-anglické verzi doplněný grafickým
1.2.1 Separace skla Obalové sklo se používá především u průmyslových výrobců potravinářského zboží, ale odpad z něj většinou učiní až drobní spotřebitelé, kteří spotřebují obsah obalu a potom se jej musejí zbavit. Jedním z úspěchů moderního přístupu k recyklaci a ekologické ekonomii je recyklace skleněných obalů. Skleněné obaly jsou výjimečné svými vlastnostmi a jako jeden z mála materiálů je můžeme stoprocentně recyklovat. V praxi můžeme ze skleněných obalů, jako druhotné suroviny vyrobit znovu skleněný obalový materiál se stejnými vlastnostmi. Jednou z důležitých vlastností je zdravotní nezávadnost.
1.2.2 Separace PET lahví V roce 2001 byl ve městě Brně zahájen systém separovaného sběru PET lahví. Ke sběru a shromáždění těchto PET lahví se používají speciální kontejnery, které byly pořízeny z Fondu životního prostředí města Brna. Hlavním podmětem k zavedení separovaného sběru byly především požadavky Evropské Unie. Důležitými faktory, které rozhodly pro tento systém separace jsou vytřídění PET lahví pro látkovou recyklaci, soustavný tlak veřejnosti požadující separaci a snížení podílu PET lahví, jakou součásti zbytkového komunálního odpadu. Svozy z jednotlivých stanovišť zajišťují speciální svozová vozidla s lineárním stlačením pro svoz vyseparovaných složek. PET lahve jsou dopraveny na místo, kde dojde k třídění a následně se prodají odběratelům. V současné době je tento způsob pro město Brno realizován společností SAKO Brno, a. s.
11
V rámci systému separace PET lahví může občan odkládat sešlápnuté PET láhve nejen na 47-mi sběrných střediscích odpadu, ale i na dalších 76 stanovištích kontejnerů, umístěných u vybraných supermarketů a veřejně přístupných místech, jejichž počet se bude i nadále zvyšovat.
1.2.3 Možnosti využití recyklátu z PET lahví Produkt následné recyklace PET lahví slouží jako polyesterová stříž na výplň do zimních bund a sportovního oblečení, výplň spacích pytlů, k výrobě polyesterových koberců, technických tkanin, vláken pro textilní výrobky atd. Recyklovaný PET má však v zahraničí a zejména v USA daleko širší použití, například k výrobě obuvi, nábytku, pracovních rukavic, klobouků, kufrů, kancelářských výrobků, pohonných pásů, ve zdravotnictví, k výrobě lepidel, ve stavebnictví atd. s pokrokem techniky a technologie se objevují stále nová využití.
1.2.4 Separace papíru Základním a těžko postradatelným obalovým materiálem pro balení výrobků jsou papírové a lepenkové materiály a obaly. Důležitou vlastností papírových a lepenkových obalů je jejich dobrá recyklovatelnost. Sběrový papír byl vždy využíván, jako důležitá surovina a nikdy s ním nebylo zacházeno, jako s odpadem. Množství takto shromažďovaného papíru se stále zvyšuje úměrně vzrůstajícím požadavkům společnosti na množství papíru, který je v dnešní době považován za jednu z dobře recyklovatelných surovin. Zajímavým faktorem je, že recyklovatelnost papíru je vysoká a náklady na recyklovaní papíru jsou výrazně levnější než je použití dřeva, jako základní suroviny. Při použití sběrového papíru je třeba vzít v úvahu, že není možné tento papír recyklovat nekonečně, protože dochází k opotřebování papírenských vláken. Za posledních pět let vzrostla spotřeba papíru ze 767 000 tun na 926 000 tun, což je o 21 %. Ještě vyšší byl nárůst ve využití sběrového papíru a to o 40 %, z 261 000 tun 12
na 366 000 tun v roce 2000. V současné době je procento recyklace papíru v České republice kolem 45 %, průměr zemí Evropské unie je asi 50 %. Z toho obalový materiál na bázi lepenky a papíru tvoří zhruba 43% všeho vyráběného papíru a lepenek. Při výrobě těchto balících materiálů se spotřebuje největší množství sběrového papíru. Data poskytnutá Evropskou konfederací papírenského průmyslu dokumentují, že při výrobě vlnité lepenky se může jednat o spotřebu vláken ze sběrového papíru až 89,9%. Druhé odvětví, které zaznamenává velkou spotřebu recyklovaných vláken je výroba hygienických a toaletních papírů s 63.8% podílu recyklovaného materiálu. V České Republice používáme sběrový papír především, jako hlavní surovinu pro výrobu materiálů na vlnité lepenky. Spotřeba sběrového papíru do ostatních druhů papírů je výrazně menší. Jednou ze základních vlastností papírenského průmyslu je důraz kladený na využití obnovitelných zdrojů z hlediska recyklovatelnosti, kde zastává papírenský průmysl první místo. Pro papírenský průmysl je tedy signifikantní vysoká míra ekologické efektivity a udržitelnosti.
1.2.5 Separace textilu Občané města Brna mají možnost odkládat použitý textilní materiál do kontejnerů, které jsou speciálně určeny pro sběr oděvů a textilních materiálů. Sběr, svoz a třídění textilu ve městě Brně provádí společnost E + B textil s. r. o.
2 LEGISLATIVA ODPADOVÉHO HOSPODÁŘSTVÍ Zákon č. 185/2001 Sb., o odpadech a o změně některých dalších zákonů, v platném znění. Zákon č. 383/2008 Sb., kterým se mění zákon č. 185/2001 Sb., o odpadech a o změně některých dalších zákonů, ve znění pozdějších předpisů, zákon č. 283/1991 Sb., o Policii České republiky, ve znění pozdějších předpisů, a zákon č. 56/2001 Sb., o podmínkách provozu vozidel na pozemních komunikacích a o změně zákona č. 168/1999 Sb., o pojištění odpovědnosti za škodu způsobenou provozem vozidla a o změně některých
13
souvisejících zákonů (zákon o pojištění odpovědnosti z provozu vozidla), ve znění pozdějších předpisů. Zákon č. 9/2009 Sb., kterým se mění zákon č. 156/1988 Sb., o hnojivech, a další související zákony. Těmi jsou i zákon č. 185/2001 Sb., o odpadech, a zákon č. 334/1992 Sb., o ochraně zemědělského původního fondu. Zákon přináší zásadní změnu v posuzování výkopových zemin a hlušin a sedimentů z vodních toků a nádrží a stanoví kvalitativní limity, při jejichž splnění se na tyto látky zákon o odpadech nevztahuje. Zákon rovněž nově upravuje možnost využití sedimentů z rybníků, vodních nádrží a vodních toků na zemědělské půdě. •
Vyhláška
Ministerstva
životního
prostředí č.
376/2001
Sb.,
o hodnocení
nebezpečných vlastností odpadů, v platném znění. •
Vyhláška Ministerstva životního prostředí č. 381/2001 Sb., kterou se stanoví Katalog odpadů, Seznam nebezpečných odpadů a seznamy odpadů a států pro účely vývozu, dovozu a tranzitu odpadů a postup při udělování souhlasu k vývozu, dovozu a tranzitu odpadů (Katalog odpadů), v platném znění. Příloha č.1, příloha č.2 , příloha č.3, příloha č.4
•
Vyhláška Ministerstva životního prostředí č. 382/2001 Sb., o podmínkách použití upravených kalů na zemědělské půdě, v platném znění.
•
Vyhláška Ministerstva životního prostředí č. 383/2001 Sb., o podrobnostech nakládání s odpady, v platném znění.
•
Vyhláška Ministerstva životního prostředí č. 237/2002 Sb., o podrobnostech způsobu provedení zpětného odběru některých výrobků, v platném znění.
3 STÁVAJÍCÍ STAV SVOZU ODPADŮ
3.1 Způsob svozu V roce 1999 byla společnost SAKO Brno a. s. pověřena převzetím povinnosti nakládání s komunálním odpadem v rámci celého Statutárního města Brna. Společnost SAKO s. r. o.
14
je plně ve vlastnictví města Brna. Svoz odpadu zajišťuje druhá divize, která sídlí na ulici Černovická 15 v Brně Komárově. Pro zajištění svozu SKO se používají vozidla s lineárním stlačováním (značek Mercedes, Renault a Iveco). V areálu divize svozu je také umístěna myčka svozových vozidel a nově vůz-myčka, který je určen k čištění svozových nádob. Jednou ze základních marketingových strategií, kterou společnost prosazuje pro zvýšení konkurenceschopnosti je častá obměna, obnova a modernizace vozového parku. Podnikatelské subjekty mají možnost výběru, v jakém intervalu jim budou sběrné nádoby vyváženy. V současnosti volí z následujících možností 1–5× týdně, 1× za 14 dní a při potřebě jednorázového svozu je možno si dohodnout individuální přistavení kontejneru. Společnost SAKO, a. s. nabízí pro ukládání odpadu různé typy nádob. Jedná se o plastové nádoby 60 l, 110 l, 120 l, 140 l, 240 l, 1 100 l a velkoobjemové kontejnery 7 m3, 10 m3. K dispozici jsou speciální nádoby na svoz plastů, skla a papíru. Všechny typy těchto nádob je možno od společnosti pronajmout nebo zakoupit. Důležitým prvkem je bezplatná výměna poškozené nebo zničené nádoby.
3.2 Podrobnosti o systému nakládání s odpady Podrobnosti o systému nakládání s odpady na území města Brna upravuje vyhláška statutárního města Brna č. 6/2005 o nakládání s komunálním a stavebním odpadem na území statutárního města Brna (vyhláška o odpadech) ve znění pozdějších změn a doplňků. Část komunálního odpadu, která vzniká po vytřídění využitelných složek odpadu, objemných odpadů a nebezpečného odpadu, mohou občané ukládat do nádob speciálně určených pro zbytkový odpad. Množství těchto nádob a jejich objem pro jednotlivé nemovitosti se stanoví dle produkce zbytkového odpadu a četnosti svozu. Žádosti o změny má v kompetenci Odbor životního prostředí Magistrátu města Brna. Jako doporučená produkce zbytkového odpadu je uváděn údaj 4l/osobu/den.
15
Zavedení tohoto systému nakládání s odpadem při 100% majetkové účasti Statutárního města Brna, přináší městu jako původci odpadu výhody spočívající v přímé kontrole společnosti, operativnosti a přehledu nad finančními prostředky.
3.2.1 Sběr nápojových kartonů V roce 2002 výrobci nápojových kartonů ve spolupráci s EKO-KOM, a.s. iniciovali nový projekt, jehož cílem bylo zajistit třídění, sběr a lepší využívání nápojových kartonů v celé ČR. Nápojové kartony jsou jedním z nejvíce rozšířených spotřebitelských obalů. Občas se objevují jako příměs v tříděném sběru, zvláště ve sběrovém papíru, část však jako běžná součást komunálního odpadu končí bez dalšího využití na skládkách. Od roku 2003 je zajištěno materiálové využití nápojových kartonů zpracovateli v ČR a od roku 2007 jsou, vzhledem k neustále rostoucímu množství vytříděných nápojových kartonů, do recyklace zapojeny i zahraniční subjekty. Společnost EKO-KOM, a.s. zajišťuje zpětný odběr a materiálové využití i pro tento druh obalu a úpravce odpadů i obce motivuje k předávání této suroviny konečným zpracovatelům. Pro podporu sběru nápojových kartonů zavedla společnost EKO-KOM, a.s. odměnu za zajištění využití odpadů z obalů z nápojových kartonů. Na tuto odměnu má nárok obec, která zajistí sběr odpadů z nápojových kartonů a jejich předání konečnému zpracovateli prostřednictvím např. svozové firmy nebo dotřiďovací linky. Systém sběru nápojových kartonů je vždy vázán na technickou úroveň následného dotřídění a úpravy nápojových kartonů pro konečného zpracovatele. Záleží na tom, je-li úpravce vybaven dopravníkovou třídící linkou nebo pouze ručním dotřiďováním na ploše bez dopravníku. Technická vybavenost úpravce limituje možnosti použitých způsobů sběru nápojových kartonů.
16
4 DRUHY SBĚRŮ
4.1 Sběr ve směsi s jinou komoditou Filozofií této metody je především úspora nákladů při pořizování nádob (třídí se do již existujících nádob), nádoby se pouze označí tak, aby bylo jasné, že je možné do nich odkládat nápojové kartony. Úspora nákladů je dále při svozu nádob, není třeba zvláštního svozu, nápojové kartony jsou sváženy spolu s majoritní komoditou. Nutnost zvýšení četnosti svozu sběrných nádob po zavedení sběru nápojových kartonů touto metodou nebyla prokázána. Nejvyšší náklady jsou až následně při dotřiďování odpadů, kdy se nápojové kartony vytřídí ze směsi na dotřiďovací lince. Systém je vhodný zejména pro menší obce, které mohou velmi efektivně rozšířit účinnost a využití systému třídění odpadů v obci.
4.1.1 Charakteristika systému Jedná se o systémy s nižší výtěžností sběru, okolo 0,20 kg/os/rok. Vzhledem k rozpočítávání množství není jednoznačně určitelné, kolik která obec nápojového kartonu skutečně sebrala. Tento způsob sběru může být částí veřejnosti negativně vnímán, neboť v občanech vyvolává pocit, že odpady jsou směšovány. Proto je třeba dbát na důkladnou informovanost obyvatelstva.
4.1.2 Orientační náklady Pořízení nádob: 0,0 Kč Označení nádob: 0,0 Kč, EKO-KOM, a.s., poskytuje samolepky na nádoby zdarma Svoz nádob: Náklady lze obtížně stanovit, jedná se o příslušný podíl ze svozu majoritní komodity. Lze je považovat za zanedbatelné. Dotřídění: Náklady jsou opět obtížně stanovitelné, záleží na technologii a organizaci dotřídění. V případě, že pro třídění nápojových kartonů je stanoven konkrétní člověk 17
(podle současných zkušeností není nezbytný), jsou náklady dány mzdovými náklady včetně příslušných odvodů a příslušným podílem na energiích a amortizaci zařízení. Náklady na dopravu ke zpracování: Tyto náklady jsou stanoveny zvoleným způsobem dopravy. Při maximální hospodárnosti (přepravovaná hmotnost x zvolený dopravní prostředek) se náklady pohybují mezi 300 až 700 Kč/t. V rámci připravovaného systému přepravy nápojových kartonů ke zpracování od podzimu roku 2008 budou přepravní náklady v režii Operátora.
4.2 Sběr do samostatných nádob Filozofií této metody je především zachování a rozšíření stávajícího nádobového systému. To znamená, že ke stávajícím sběrným nádobám se přidá další příslušně označená nádoba tak, aby bylo zřejmé, že je určená pro sběr nápojových kartonů. Úspora nákladů je zejména při dotřiďování, neboť komodita obsahuje velmi malé množství nečistot a je možné ji dotřiďovat na technologicky jednoduchém zařízení. Nádoby se instalují podle stávajícího systému v obci, je možné použít nádoby se spodním i horním výsypem. Stejně tak je možné použít nádoby různých objemů, od 120 do 1500 litrů. V případě použití nádob větších objemů je třeba počítat s delší dobou plnění a možným znehodnocováním obsahu, zejména nežádoucími příměsemi. Dále je třeba zvláštního svozu, u nádob 1100 l frekvence svozu 1x za 2 týdny až měsíc, u nádob s menším objemem 1x týdně až 1x za 14 dní.
4.2.1 Charakteristika systému Systémy s vysokou výtěžností sběru, i přes 0,30 kg/os/rok. Vzhledem k přesnému počtu nádob je vždy zřejmé, kolik která obec nápojového kartonu skutečně sebrala. Tento způsob sběru je pozitivně vnímán, občané dobře reagují na zvláštní nádobu. Systém je vhodný zejména do větších měst - v závislosti na vyšším výskytu nápojových kartonů. Při použití nádob o větším objemu hrozí znehodnocování suroviny, protože se prodlužuje doba mezi svozy a přibývá nežádoucích příměsí.
18
4.2.2 Orientační náklady Pořízení nádob: 700 Kč/ks - 7500 Kč/ks - podle typu použitých nádob Označení nádob: 0,0 Kč, EKO-KOM, a.s., poskytuje samolepky na nádoby zdarma Svoz nádob: Náklady závisí na typu použitých nádob, použité svozové technice, počtu pracovníků, délce svozové trasy apod. Dotřídění: Náklady na dotřídění jsou velmi nízké, záleží na technologické vybavenosti firmy, spolu s lisováním se pohybují okolo 800 Kč/t, při dostatečném množství sebraného materiálu. Náklady na dopravu ke zpracování: Tyto náklady jsou stanoveny zvoleným způsobem dopravy. Při maximální hospodárnosti (přepravovaná hmotnost x zvolený dopravní prostředek) se náklady pohybují mezi 300 - 700 Kč/t. V rámci připravovaného systému přepravy nápojových kartonů ke zpracování od podzimu roku 2008 budou přepravní náklady v režii Operátora.
4.3 Sběr pytlový Filozofií této metody je především zachování výhod nádobového systému při snížení nákladů na nádobu (cena jednoho pytle o objemu 120 l je max. 3,0 Kč, což je 130 x méně než nádoba 240 l). Pytle pro sběr nápojových kartonů poskytuje obcím společnost EKOKOM, a.s. zdarma. Další úspora nákladů je patrná při dotřiďování, neboť komodita obsahuje velmi malé množství nečistot. Systém sběru se upravuje podle místních podmínek. Nejběžnější systém je dokládání pytlů k hnízdům na tříděný odpad, a pravidelný svoz (1x za týden až 1x za měsíc). Svoz je možné realizovat vozidlem s nízkými provozními náklady, např. pick-up, dodávka, AVIA.
4.3.1 Charakteristika systému Systémy s vysokou výtěžností sběru, až okolo 0,30 kg/os/rok. Vzhledem k přesnému počtu pytlů je vždy zřejmé, kolik která obec nápojového kartonu skutečně sebrala. Tento způsob sběru je vnímán rozporuplně, občané občas odmítají mít pytle v domácnosti z důvodu 19
nedostatku místa. Velmi záleží na distribuci pytlů, při velkých docházkových vzdálenostech na distribuční místa zájem o třídění do pytlů významně klesá, při delších frekvencí svozu hrozí hromadění nepořádku na sběrných místech. Systém sběru je velmi variabilní, dá se velmi dobře přizpůsobit místním podmínkám, je dobře použitelný do menších obcí, ale úspěšně je provozován i v městech okolo 50 000 obyvatel.
4.3.2 Orientační náklady Pořízení pytlů: 3,0 Kč/ks (80 - 120l), v současné době poskytuje EKO-KOM, a.s. obcím pytle zdarma. Označení nádob: 0,0 Kč Svoz nádob: Náklady závisí na počtu sběrných míst, použité svozové technice, počtu pracovníků, délce svozové trasy apod. Dotřídění: Náklady na dotřídění jsou velmi nízké, záleží na technologické vybavenosti firmy, spolu s lisováním se pohybují okolo 800 Kč/t, při dostatečném množství sebraného materiálu. Náklady na dopravu ke zpracování: Tyto náklady jsou stanoveny zvoleným způsobem dopravy. Při maximální hospodárnosti (přepravovaná hmotnost x zvolený dopravní prostředek) se náklady pohybují mezi 300 - 700 Kč/t. V rámci připravovaného systému přepravy nápojových kartonů ke zpracování od podzimu roku 2008 budou přepravní náklady v režii Operátora.
4.4 Sběr školní Filozofií této metody je využití přirozené soutěživosti dětí a příspěvek k výchově obyvatelstva k třídění odpadů. Náklady jsou přitom velmi nízké. Další úspora nákladů je patrná při dotřiďování, neboť komodita neobsahuje nečistoty. Svoz je možné realizovat vozidlem s nízkými provozními náklady, např. pick-up, dodávka, AVIA.
20
4.4.1 Charakteristika systému Systémy s proměnlivou výtěžností sběru, okolo 0,20 kg/os/rok. Tento způsob sběru je vnímán rozporuplně, ne všechny školy jsou k třídění dostatečně motivované, diskuzi vyvolává tzv. vytváření negativního návyku (zcela pravdivé tvrzení, že škola není místem pro odkládání odpadů), přesto je tento způsob sběru použitelný jako součást environmentální výchovy.
4.4.2 Orientační náklady Pořízení nádob: 0,0 Kč/ks při použití krabice od banánů Označení nádob: 0,0 Kč Svoz nádob: Náklady závisí na počtu sběrných míst, použité svozové technice, počtu pracovníků, délce svozové trasy apod. Dotřídění: Náklady na dotřídění jsou velmi nízké, záleží na technologické vybavenosti firmy, spolu s lisováním se pohybují okolo 800 Kč/t při dostatečném množství sebraného materiálu. Náklady na dopravu ke zpracování: Tyto náklady jsou stanoveny zvoleným způsobem dopravy. Při maximální hospodárnosti (přepravovaná hmotnost x zvolený dopravní prostředek) se náklady pohybují mezi 300 - 700 Kč/t. V rámci připravovaného systému přepravy nápojových kartonů ke zpracování od podzimu roku 2008 budou přepravní náklady v režii Operátora.
4.5 Možnosti zpracování nápojových kartonů Pro úspěšné předání nápojových kartonů ke zpracování je nezbytné dodržet podmínky zpracovatelů. V ČR v současné době zpracovávají nápojové kartony následující zpracovatelé: Brněnské papírny s.p., Tišnov Flexibuild, s.r.o., provoz Hrušovany u Brna.
21
4.6 Operátor V rámci systému přepravy nápojových kartonů ke zpracování vznikl roku 2008 institut Operátora. Celý tento institut je zaměřen na zajištění pravidelného zásobování zpracovatelů nápojových kartonů a na přepravu těchto kartonů od úpravců až ke zpracovatelům. Výsledkem zavedení tohoto institutu je snižování nákladů na přepravu a výrazné zkrácení doby pro skladování upravených nápojových kartonů. Institut Operátora je smluvním partnerem společnosti EKO-KOM, a. s. a zajišťuje přepravu upravených nápojových kartonů za podmínek, které jsou určeny zpracovateli a přepravu od úpravců ke konečným zpracovatelům. Operátor bude provádět úpravu nápojových kartonů nesplňujících podmínky zpracovatelů a v případech kdy je k tomu oprávněn bude zajišťovat skladování upravených nápojových kartonů. S touto eventualitou se počítá zejména v případě odstávek zpracovatelů a naplnění zpracovatelských kapacit. Jedním z úkolů Operátora je komunikace s jednotlivými zpracovateli nápojových kartonů, zjištění aktuálního stavu kapacity zpracovatelského podniku a rozhodnutí o tom, kterému zpracovateli budou předány nápojové kartony od úpravců. Součástí práce Operátora bude zpracovávat objednávky od jednotlivých úpravců na zajištění přepravy ke zpracovateli a ty pak bude zpracovávat podle určeného pořadí. Operátor bude součásti komunikace mezi zpracovatelem a úpravce a to především v případě nedostatečné kvality dodávek a v případech reklamačního řízení. Kvůli možnosti zpětné kontroly a lepší orientaci v systému bude vydávat doklad o bezchybné dodávce. Tento doklad je důležitý pro pozdější vydání odměny úpravci. Pokud dodávka není v pořádku a doklad pro úpravce nebyl vystaven, tak má úpravce možnost chybu opravit a doklad pro něj může být znovu vystaven. Bude však oprávněn požadovat za tuto úpravu od úpravce náhradu, a to ve výši skutečně vynaložených nákladů spojených s dodatečnou úpravou. Operátor může k zajištění dopravy použít vlastní dopravní prostředky, externích přepravců nebo prostředků úpravce. Jeho hlavní povinností je zvážit, který z nabízených způsobů dopravy je pro něj ekonomicky nejvýhodnější. Vyplacení odměny za dodání požadované kvality nápojových kartonů vydává firma EKO- KOM, a. s. na základě dříve zmiňovaných dokladů na základě informací od Operátora a zpracovatelů.
22
4.6.1 Informační a materiálová podpora Společnost EKO-KOM, a.s. nabízí obcím zdarma pro sběr nápojových kartonů informační materiály, letáky pro veřejnost, samolepky na sběrné nádoby a pytle pro sběr nápojových kartonů, a to prostřednictvím regionálních manažerů.
5 SVOZOVÁ TRASA Povinností města je určit místa, kde se budou nacházet jednotlivé sběrny a výkupny druhotných surovin, sběrné vaky (nemocnice, školy a školky), sběrné nádoby na zbytkový odpad, sběrná místa odpadů, aby občané věděli, na která místa mohou ukládat složky komunálního odpadu (KO). Množství a objem kontejnerů na dané adrese se stanovují podle počtu osob bydlících na dané adrese a u velkoobjemových kontejnerů se zvažují podmínky veřejného prostranství. Při hledání vhodné svozové trasy jsem se rozhodnul pro využití již existujících tras pro svoz odpadu ve městě Brně, které využívá společnost SAKO. Jako výchozí body pro pozdější výpočet bylo vybráno umístění kontejnerů pro PET láhve na území městské části Brno – sever. Město Brno je rozděleno do padesáti oblastí svozu komunálního odpadu nebo jeho jednotlivých složek. Svoz odpadů řídí centrální dispečink firmy SAKO, který stanovuje pouze seznam ulic, ze kterých má být odpad svezen, ale neupravuje pro posádku vozu pořadí, ve kterém mají svážet kontejnery na jednotlivých ulicích. Vozy jsou vybaveny mobilní jednotkou, která pomocí systému GPS přenáší polohovou informaci o vozu do centra dispečinku, kde se údaje zpracovávají pomocí softwarového programu Lupus Trans. Data získaná pomocí programu slouží ke kontrole vozidel, řešení nečekaných situací a poruch nebo jako podklady pro knihu jízd.
23
6 OPTIMALIZACE SVOZOVÉ TRASY ODPADU
6.1 Teorie – problém obchodního cestujícího Problém obchodního cestujícího je obtížný optimalizační problém. Matematicky vyjadřuje úlohu nalezení, co nejkratší cesty mezi body, které jsou zadány na mapě. Problém můžeme definovat pomocí grafů, kde jednotlivá místa, která musíme navštívit odpovídají vrcholům a délka cesty mezi těmito místy odpovídají kladně ohodnoceným, v tomto případě orientovaným, hranám úplného grafu. Potom trasa mezi všemi místy se rovná nalezení Hamiltonovské kružnice a optimální trasa se rovná nejkratší možné Hamiltonovské kružnici.
6.2 Obtížnost Optimalizační verze problému obchodního cestujícího patří mezi tzv. NP-těžké úlohy, tzn. v obecném případě není známo ani jak pro každý vstup nalézt přesné řešení v rozumném čase a dokonce ani, zda vůbec může existovat algoritmus, který takové řešení najde v čase úměrném nějaké mocnině počtu uzlů. Že
jde
o nedeterministicky
polynomiální
problém
je
patrné
z
toho,
že nedeterministický počítač, umožňující v každém kroku rozvětvit výpočet na libovolný počet větví, by mohl začít v některém „městě“, rozdělit propočet délky trasy na tolik větví, kolik z města vede silnic, a v každém z cílových měst postupovat stejně – s výjimkou tras vedoucích do již navštívených měst. Tak by prohledal všechny možné trasy v n výpočetních krocích, pokud počet měst činí n, a rozvětvil by se maximálně do (n − 1)! větví. V praxi se podobná úloha obvykle řeší pouze přibližně (heuristickými algoritmy, např. genetickými algoritmy, atd.). Tím se (za cenu vzdání se nároku na nalezení přesného řešení) dosahuje prakticky použitelných časů. Heuristické algoritmy obecně nijak negarantují, jak moc se získaný výsledek liší od optimální cesty, pro metrický problém obchodního cestujícího však existují prakticky 24
použitelné (polynomiální) algoritmy, které toto dovedou (např. Christofidův algoritmus najde cestu, která je nejhůře o polovinu delší).
6.3 Ilp formulace Pomocí celočíselného lineárního programování lze problém asymetrického obchodního cestujícího (tzn. hrany A → B a B → A nemusejí mít stejnou váhu) formulovat jako:
n n min ∑∑ xij • Sij , při respektování podmínky: i =1 j =1
n
n
∑∑ x i =1 j =1
ij
= n, i, j ∈ {1,K, n} , kde
xij ∈ {0,1} udává, zda je spojnice o délce S ij , spojující itý a jtý bod použita nebo ne.
6.4 Možné způsoby řešení Tradiční postupy NP řešení jsou následující
•
Hrubou silou – tato technika vyžaduje výpočet všech možných řešení, dokud nedojdeme k nejlepšímu výsledku. Funguje jen při relativně malých problémech.
•
Nalezení speciálních případů pro daný problém, pro které existují lepší heuristické metody řešení.
•
Nalezení přibližného řešení – většinou za použití heuristických nebo meta-heuristických algoritmů, které naleznou řešení blízké optimálnímu, ale nejde dokázat, že se jedná o řešení optimální.
6.5 Zvolená metoda pro řešení problému Rozhodli jsme se pro řešení problému za pomoci heuristických algoritmů. Nejprve jsme z mapy odečetli jednotlivé souřadnice míst, na kterých jsou umístěny nádoby pro sběr a přepočetli je na souřadnice [x, y]. Z nich jsme vypočetli matici vzdušných vzdáleností.
25
Určili jsme vždy dva nejblíže umístěné volné body a spojili jsme je úsečkou, dokud nevznikla lomená čára, spojující všechny body. Poté jsme hledali nejkratší trasu vždy pro šest po sobě následujících bodů. Po nalezení trasy a jejím zobrazení jsme zjistili, že se trasa v některých místech kříží. Provedli jsme úpravy, které křížení omezují, a poté jsme převedli vzdušnou trasu na matici reálného prostředí za použití údajů o vzdálenosti jednotlivých ulic ve skutečném prostředí (Tabulka č. 1 Adresy ulic, kde jsou umístěny svozové nádoby a jejich vzdálenosti, str. 26). Po této úpravě jsem získali optimální trasu svozu odpadu.
7 OPTIMALIZACE SVOZOVÉ TRASY ODPADU POMOCÍ MATEMATICKÉHO PROGRAMU MAPLE
7.1 Základní popis programu MAPLE
MAPLE je program pro řešení matematických problémů. Stejně tak jako matematik, MAPLE ovládá pravidla algebry a matematické analýzy, které se učí ve škole. MAPLE například ví, jak řešit rovnice, zjednodušovat výrazy, vykreslovat grafy a počítat derivace či integrály. MAPLE pracuje přímo se symboly, kterými jsou rovnice tvořeny, což znamená, že zachovává obecnost, dokud nepotřebujeme číselnou odpověď. MAPLE neumí jenom vykreslovat dvojrozměrné či trojrozměrné grafy, ale také v něm lze tvořit pokročilejší grafiku, jako animace, pole vektorů, parametrické křivky nebo dynamické systémy.
26
Tabulka č. 3: Polohy a vzájemné vzdálenosti svozových nádob v kilometrech Ulice
# Bodu
Jedovnická
1
Barvy
2
7,9
Bieblova
3
4,7 1,9
Černopolní
4
8,1 3,4 1,9
Dusíkova
5
9,1 1,4 3,4 4,5
Fillova
6
4,6
Halasovo nám.
7
4
Jana Svobody
8
6,5 3,3 2,1 1,2 4,0 4,3 2,9
Janouškova
9
7,4 1,8 0,5 2,0 2,5 2,0 1,2 2,4
Kaloudova
10
5,9 1,9 1,8 2,6 2,6 2,7 1,7 1,5 2,3
Loosova
11
4,8 0,8 1,3 2,4 1,0 0,9 1,6 4,4 2,5 3,2
Majdalenky
12
8,8 1,1 3,1 4,2 0,2 1,5 1,9 4,3 2,6 2,8 1,5
Marie Majerové 13
1
2 7
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2,2 6,8 7,7 8,8 7,8 6,0 7,9 5,3 10,1 7,9 7,7 6,8 6,6 8,3 5,7 10,8 8,2 5,1 8,8 10,3 6,6 6,7 1,1 2,2 1,3 2,3 2,2 0,5 1,8 2,4 3,2 1,4 1,0 2,0 2,0 1,0 5,8 2,7 1,6 2,9 5,5 1,5
1
3,4 1,0 2,4 1,0 3,2 1,8 1,9 2,9 1,3 1,2 1,1 2,6 2,0 1,9 3,2 0,8 1,9 1,9 3,7 3,1 4,0 3,6 3,0 1,3 2,0 2,5 4,1 4,2 2,5 2,6 1,9 3,1 1,7 6,3 3,2 2,4 2,8 6,6 0,5 2,2 2,2 4,2 2,9 3,1 2,2 0,2 1,9 1,6 4,1 1,7 2,5 1,8 1,9 3,4 2,6 2,0 3,7
1,3 2,4 1,0
1,4 4,1 1,0 3,0 0,6 1,2 1,9 1,6 3,6 0,7 3,3 3,7 2,2 2,9 1,1 4,0 3,2
0,85 0,9 1,9 1,4 1,1
3,0 1,3 1,9 1,6 2,0 0,7 0,4 2,4 0,7 1,4 4,1 1,0 1,7 0,8 4,4 2,4 2,3 1,7 4,7 4,3 2,5 2,7 0,9 3,9 1,8 6,4 3,3 1,6 3,9 6,6 1,1 1,8 2,4 2,6 0,9 1,1 1,6 1,5 0,9 4,8 1,6 1,7 1,2 5,0 1,6 3,1 2,8 1,0 1,5 0,9 2,2 0,8 4,9 2,5 0,2 2,3 5,2 2,2 1,5 2,2 1,9 3,8 0,9 3,6 3,9 2,5 3,1 1,3 4,2 3,5 2,0 1,8 3,8 1,5 2,7 2,5 1,6 3,0 1,9 2,7 3,9
7,1 1,2 1,4 2,5 1,9 1,7 0,7 2,3 0,9 1,0 2,1 2,1
0,5 1,7 1,2 1,0 4,2 1,1 1,0 1,3 4,5 2,2
Merhautova
14
3,9 1,9 0,7 0,9 2,5 2,1 1,1 2,6 0,9 1,2 2,5 2,0 0,3
Nováčkova
15
6,4 2,6 1,7 2,1 3,3 4,0 2,1 0,7 1,8 0,9 4,4 3,5 1,8 2,0
Okružní
16
7,9 1,7 2,0 2,9 1,7 0,5 0,7 3,5 1,5 2,3 0,9 1,5 1,2 1,0 2,9
Provazníkova
17
Síčka
18
10,9 3,2 5,2 6,3 2,3 3,9 4,0 6,5 4,7 4,9 3,9 2,5 4,2 3,9 5,9 4,0 4,8
Šrámkova
19
7,8 0,8 2,1 3,2 1,4 2,1 0,9 3,3 1,6 2,2 2,9 1,6 1,0 0,8 2,8 1,6 1,7 3,7
Tomkovo nám.
20
3,8 1,7 1,4 1,7 2,4 2,6 1,7 1,3 2,1 0,2 3,1 2,8 1,0 1,5 0,8 2,2 0,7 4,9 2,4
Třískalova
21
7,9 1,7 2,0 2,9 1,9 0,7 0,7 3,4 1,5 1,9 1,3 1,7 1,2 1,0 2,8 0,3 2,6 4,2 1,5 2,1
Útěchovská
22
7,9 3,5 3,9 5,0 1,9 4,0 4,0 6,7 5,0 5,0 4,2 2,5 2,5 3,9 5,9 4,0 4,8 0,3 4,0 5,4 5,2
Volejníkova
23
7,5 2,7 1,3 0,6 3,3 2,2 2,4 1,1 1,4 1,9 3,5 3,5 1,8 1,9 1,2 2,5 1,1 5,6 2,5 1,7 2,2 5,9
4
23
2,0 1,6 0,9 5,0 1,5 1,3 1,7 4,4 2,1 3,5 1,3 5,6 2,6 0,8 3,2 5,9 1,5 2,6 4,0 1,5 2,2 0,4 4,2 2,6
1,6 0,8 1,2 2,3 3,3 1,5 2,0 0,9 0,8 3,7 2,9 1,2 1,3 1,1 2,8
27
4,9 1,9 0,5 2,5 5,3 1,5 3,7 5,2 4,4 0,5 6,0 2,1 1,7 4,0 2,9 3,0 5,1 2,1 4,5 2,6 6,2
7.2 Optimalizace svozové trasy odpadu v programu MAPLE Start Maple, zpřístupnění knihoven příkazů, které budou zapotřebí pro řešení problému restart; with(LinearAlgebra): with(plots): with(combinat): with(ExcelTools): Načteme soubor vytvořený Excelem, který obsahuje vzájemné vzdálenosti jednotlivých bodů a jejich názvy a GPS souřadnice, výsledek ulož do matice M M:=Import("Dist_Real2.xls"); Určíme počet zpracovávaných bodů - N N:=op(2,[op(2,M)][1])-1; Přečteme první sloupec matice M a uložíme jej do proměnné GPS GPS:=[seq([M[i,1]],i=2..N+1)]: Údaje v proměnné GPS rozložme na úhlové stupně, minuty a sekundy, pro zeměpisnou šířku i délku, opět uložíme do GPS. GPS:=map(u->sscanf(u[],"%d°%d'%f\"N, %d°%d'%f"),GPS): Nyní hodnoty v proměnné GPS přepočteme na hodnoty v radiánech, výsledek opět uložíme do GPS GPS:=map(u->evalf(Pi/180*[(u[1]+u[2]/60+u[3]/3600), (u[4]+u[5]/60+u[6]/3600)]),GPS): Do proměnné Poloha načteme názvy jednotlivých lokalit Poloha:=[seq(M[i,2],i=2..N+1)]: Načteme matici R_Dist reálných - silničních vzájemných vzdáleností jednotlivých lokalit. Tato matice není symetrická, protože cesta z jednoho bodu do druhého a zpět nemusí být po stejné trase z důvodů jednosměrného provozu. Jednotlivé vzájemné vzdálenosti byly určeny pomocí funkce Plánovač trasy na internetové adresy www.mapy.cz. Hodnota matice na řádku i a sloupci j tak reprezentuje reálnou silniční vzdálenost z bodu i do bodu j. Z výše uvedených důvodů může být tato vzdálenost různá od vzdálenosti z bodu j do bodu
28
i. Protože nemá smysl měřit vzdálenost z bodu i do bodu i, byly prvky hlavní diagonály nahrazeny nekonečnem, aby neovlivňovaly průběh optimalizace trasy. R_Dist:=subs(-1.0=infinity,convert(map(u->round(u*10)*0.1, M[2..N+1,3..N+2]),Matrix)); Nyní vypočteme průměrnou hodnotu zeměpisné šířky a délky. Jde o hodnoty, které byly v části přepočet označeny jako [φ0,ψ0]. Tyto hodnoty uložíme jako GPSc. GPSc:=add(u,u=GPS)/N; Do proměnné GPSd uložíme odchylky od průměrné hodnoty. Tyto hodnoty odpovídají proměnným [df, dl] z části přepočet. GPSd:=map(u->u-GPSc,GPS): Pro výpočet lokálních souřadnic je nutné zadat střední Zemský poloměr R:=6372.796; Lokální souřadnice přepočtené podle vztahu z předchozího Maple worksheetu jsou uloženy do proměnné XY. XY:=map(u->[R*cos(GPSc[1])*u[2],R*u[1]],GPSd);
Výsledek je možné znázornit graficky P1:=plot(XY,style=point,symbol=diagonalcross,symbolsize=15, color=blue,labels=["X [km]","Y[km]"], labelfont=[HELVETICA,BOLD,18]): P2:=textplot(zip((u,v)->[u[],v],XY,Poloha),align=above): P3:=textplot([seq([XY[i][],convert(i,string)],i=1..N)], align=below,font=[HELVETICA,15],color=blue): display({P1,P2,P3});
29
Obrázek č. 1: Polohy jednotlivých sběrných míst Pro první návrh svozové trasy použijeme matici A_Dist, která obsahuje přímé vzdušné vzdálenosti mezi jednotlivými body. Prvky této matice je možné spočítat z lokálních souřadnic XY. Výpočet provedeme s přesností na dvě desetinná místa. Protože jde o vzdušné vzdálenosti je tato matice symetrická. Na hlavní diagonálu matice vložíme hodnotu nekonečno. A_Dist:=Matrix(1..N,1..N); for i from 1 to N do for j from i to N do S:=evalf(sqrt((XY[i][1]-XY[j][1])^2 +(XY[i][2]-XY[j][2])^2),4); S:=round(S*100)*0.01; A_Dist[i,j]:=S; A_Dist[j,i]:=S; end do; end do: for i from 1 to N do A_Dist[i,i]:=infinity; end do: Protože v průběhu výpočtů se bude obsah matice měnit, uložíme její kopii do matice A_Dist0.
30
A_Dist0:=subs(Float(infinity)=infinity,evalf(A_Dist)); Kontrolu správnosti polohy jednotlivých bodů a jejich vzájemných vzdáleností je možné provést výpočtem rozdílu reálných a vzdušných vzdáleností. Nejmenší možný rozdíl může být 0. Záporné hodnoty znamenají, že v určení polohy nebo silniční vzdálenosti odpovídajících bodů je chyba. dd:=Matrix(map(u->round(u*10)*0.1,evalm(R_Dist-A_Dist))): dd:=subs(Float(undefined)=infinity,evalm(dd)): Podobně je zajímavé znázornění, kolikrát je delší silniční vzdálenost mezi jednotlivými body než vzdušná vzdálenost. Protože nás budou zajímat maximální hodnoty prvků matice, dosadíme za prvky hlavní diagonály nuly. dr:=zip((u,v)->subs(Float(undefined)=0, round(u/v*10)*0.1),R_Dist,A_Dist); Nyní je možné nalézt body, které mají nejvyšší podíl silniční a vzdušné vzdálenosti. Vytvoříme proměnnou diflist, která obsahuje hodnoty z matice dr, a najdeme body, které odpovídají nejvyšší hodnotě. diflist:=[{map(u->u[],convert(dr,listlist))[]}[]];
maxd:=diflist[-1]; DifList:=[]: for i from 1 to N do for j from 1 to N do if maxd=dr[i,j] then DifList:=[DifList[],[i,j]]; end if; end do; end do: map(u->print(cat(Poloha[u[1]]," -> ",Poloha[u[2]], ", vzduchem = ",convert(A_Dist[u[]],string), "km, po zemi = ",convert(R_Dist[u[]],string), "km, rozdil = ",convert(R_Dist[u[]], A_Dist[u[]],string),"km")),DifList);
31
Obrázek č. 2: Znázornění silniční trasy Z přiloženého obrázku je zřejmé, že silniční trasa mezi lokalitou Šrámkova a Halasovo náměstí je skutečně 4.2 krát delší než vzdušná. Navíc je výrazně delší než trasa v obráceném směru, protože ta umožňuje využít jednosměrnou ulici Heleny Malířové. Nalezení optimální vzdušné trasy Pořadí průjezdu jednotlivými body bude uloženo v proměnné Road.
Program najde
v matici A_Dist nejnižší hodnotu, tedy dva body, které mají k sobě nejblíže a číslo řádku a sloupce které udávají polohu tohoto prvku uloží do proměnné Road jako uspořádanou dvojici. První položka označuje místo odjezdu, druhá místo příjezdu. Protože po této trase již není nutné projíždět a to ani v protisměru v matici A_Dist se vyplní všechny hodnoty na řádku i a sloupci j hodnotou nekonečno. Tento postup se opakuje, dokud není matice A_Dist zcela vyplněna hodnotou nekonečno.
32
Zároveň se vytváří množina bodů odjezdu Dep, která obsahuje místa odjezdu a množina bodů příjezdu Arr. Pokud je Thru což je průnik těchto dvou množin neprázdný, pak to znamená, že dvě trasy přesunu na sebe navázaly a je dvě uspořádané dvojice je možné na sebe navázat. Ze dvou dvojic tak vznikne jedna trojice a průnik množin Dep a Arr bude opět prázdný. Navázání dalších tras je pak pouhé zobecnění tohoto postupu. Proměnná Road pak bude obsahovat uspořádanou N-tici bodů, uspořádaných podle pořadí průjezdu. Road:=[]: for n from 1 to N-1 do; Min:=infinity: for i from 1 to N do; for j from 1 to N do; if A_Dist[i,j]<=Min then Min:=A_Dist[i,j]; Pos:=[i,j]; end if: end do: end do: Road:=[Road[],Pos]; A_Dist[Pos[]]:=infinity; A_Dist[Pos[2],Pos[1]]:=infinity; for i from 1 to N do; A_Dist[Pos[1],i]:=infinity; end do: for i from 1 to N do; A_Dist[i,Pos[2]]:=infinity; end do: Dep:={map(u->u[1],Road)[]}; Arr:={map(u->u[-1],Road)[]}; Thru:=Dep intersect Arr; while Thru<>{} do; Road2:=select(has,Road,Thru[-1]); if Road2[1][-1]=Road2[2][1] then; Road3:=[Road2[1][],Road2[-1][2..-1][]]; else Road3:=[Road2[-1][1..-2][],Road2[1][]]; end if; Del:=[Road3[1],Road3[-1]]; A_Dist[Del[]]:=infinity; A_Dist[Del[2],Del[1]]:=infinity; Road:=[subs(map(u->u=NULL,Road2),Road)[],Road3]; Dep:={map(u->u[1],Road)[]}; Arr:={map(u->u[-1],Road)[]}; Thru:=Dep intersect Arr; end do; sort(map(u->u[],Road)); end do: end do: Zobrazení pořadí průjezdu Road:=Road[];
33
Celou trasu je nutné uzavřít, na poslední místo Road přidáme výchozí místo. Road:=[Road[],Road[1]];
Je nutný návrat k původní hodnotě matice A_Dist. A_Dist:=subs(Float(infinity)=infinity,A_Dist0): Délku trasy L0 zjistíme sečtením odpovídajících položek matice A_Dist0. L0:=add(u,u=[seq(A_Dist0[Road[i],Road[i+1]],i=1..N)]); Výsledek je možné znázornit graficky P4:=plot(map(u->map(v->XY[v],u),Road), color=green,thickness=3): display({P1,P2,P3,P4});
Obrázek č. 3: Prvotní návrh trasy
34
Jak je vidět na první pohled, je návrh trasy značně nedokonalý. Proto provedeme výpočet délky úseku, který bude tvořen n+2 body pro všechny možné permutace vnitřních n-bodů. Pokud bude délka tohoto úseku kratší, než původní délka, bude původní pořadí prvků nahrazeno pořadím novým. Permutace postupně projdou všechny uspořádané n+2tice, počínaje 1. až n+2.bodem z proměnné Road, následuje 2. až n+3. bod atd., až do okamžiku, kdy koncový bod vybrané n+2tice je totožný s poledním bodem proměnné Road. Protože krajní body se na této permutaci plně neúčastní je proměnná Road po ukončení cyklu přerovnána, samozřejmě za dodržení pořadí průjezdu, tak aby i krajní body byly plně do výčtu permutací zahrnuty. Výpočet běží tak dlouho, dokud se pořadí prvků nemění a to ani při změně výchozího bodu proměnné Road. Celý tento postup je obsahem procedury Permute, která má tři vstupní parametry. Prvním parametrem je n- počet prvků zahrnutých do permutací, druhým je seznam pořadí průjezdných bodů a třetím je matice jednotlivých vzdáleností. V průběhu výpočtu se zobrazuje aktuální délka trasy a pořadí průjezdních bodů. Permute:=proc(n,Tr,M_D) global L0; local Go1, Go2, tr, k, p1, d1, Min, m1; Go1:=true; Go2:=true; tr:=Tr; while Go1 do; Go1:=false; for k from 2 to N-n do; p1:=map(u->[tr[k-1], u[],tr[k+n+1]],permute(tr[k..k+n])); d1:=map(u-add(v, v=[seq(M_D[u[i],u[i+1]],i=1..n+2)]),p1): Min:=min(d1): if Min < d1[1] then m1:=zip((u,v)->`if`(u=Min,v,NULL),d1,p1)[1]; tr:=[tr[1..k-2][],m1[],tr[k+n+2..-1][]]; L0:=add(u,u=[seq(M_D[tr[i],tr[i+1]],i=1..N)]); Go1:=true; print('L0'=L0); print(`New Road`=tr); end if: end do: if Go1 then print(`Repeated loop, road reordered`); else if Go2 then print(`Road reordered`); Go2:=false; 35
Go1:=true; end if; end if; tr:=[tr[n+1..-1][],tr[2..n+1][]]; end do: tr; end proc: Nyní použijeme proceduru Permute pro sedm prvků, návrh trasy Road a matici vzdušných vzdáleností A_Dist. Road:=Permute(7,Road,A_Dist);
Z výpočtu je zřejmé, že se v průběhu 11-ti změn podařilo trasu zkrátit z 23.79km na 20.70 km, tedy přibližně o 13%. Výsledek je možné znázornit graficky P5:=plot(map(u->map(v->XY[v],u),Road), color=violet,thickness=3): Display ({P1,P2,P3,P5});
36
Obrázek č. 4: Křížení trasy jeho řešení Z obrázku je zřejmé, že trasa sama sebe kříží. Zkusíme proto body za křížením přerovnat. Jde o trasu mezi body 9 a 20. Zkusíme je proto do trasy vložit v obráceném pořadí a výsledek opět optimalizovat pomocí procedury Permute. PR:=[5,15]: Ra:=Road[PR[1]..PR[2]]; Rb:=[seq(Ra[-i],i=1..PR[2]-PR[1]+1)]; Road:=[Road[1..PR[1]-1][],Rb[],Road[PR[2]+1..-1][]];
L0:=add(u,u=[seq(A_Dist0[Road[i],Road[i+1]],i=1..N)]); Road:=Permute(7,Road,A_Dist);
Jak je vidět, k další změně trasy již nedošlo. Je proto možné konstatovat, že optimální vzdušná trasa má délku 19.86km. Výsledek je možné znázornit graficky. 37
P6:=plot(map(u->map(v->XY[v],u),Road),color=brown, thickness=3): Display ({P1,P2,P3,P6});
Obrázek č. 5: Optimální vzdušná trasa Na závěr je možné optimální pořadí průjezdů pro vzdušnou trasu použít jako vstupní parametr pro silniční trasu. Tato změna se provede pouze zadáním matice silničních vzdáleností R_Dist do procedury Permute. L0:=add(u,u=[seq(R_Dist[Road[i],Road[i+1]],i=1.. N)]); Road:=Permute(7,Road,R_Dist);
L0; Optimální silniční trasa tedy měří 28.1km a je znázorněna na následujícím obrázku. PF:=plot(map(u->map(v->XY[v],u),Road),color=red, thickness=3): Display ({P1,P2,P3,PF}); 38
Obrázek č. 6: Silniční trasa pohybu vozidla Jak je zřejmé, silniční trasa se mírně liší od trasy vzdušné. Křížení trasy v okolí bodů 22 a 18 (= Útěchovská a Síčka) je způsobeno jednosměrnou ulicí, která výrazně prodlužuje trasu v protisměru.
Vzhledem k tomu, že sběrné vozidlo vyjíždí z lokality Jedovnická a opět se do ní navrací, přerovnáme optimální trasu tak, aby tímto bodem začínala. i0:=seq(`if`(Road[i]=1,i,NULL),i=1..N); Road:=[Road[i0..-1][],Road[2..i0][]];
Pořadí jednotlivých lokalit tedy je: ROAD:=map(u->Poloha[u],Road);
39
Délka jednotlivých jízdních úseku je: LD:=[seq(R_Dist[Road[i],Road[i+1]],i=1..N)];
Finální itinerář optimální svozové trasy je tedy možné psát ve tvaru: Itinerary:=cat(ROAD[1],seq([" -> ",convert(LD[i],string), "km -> ",ROAD[i+1]][],i=1..N)): Itinerary:=StringTools[SubstituteAll](Itinerary," ."," 0.");
40
8 ZÁVĚR
Práce popisuje důležitost a druhy separovaného odpadu, seznamuje s oporou v zákoně. Podrobněji se v práci věnujeme způsobu svozu odpadů a jeho organizaci. V druhé části se práce se zabývá optimalizací svozové trasy odpadu pro městskou část Brno – sever. Jde o obdobu problému obchodního cestujícího, který je pro řešení uvažovaného problému stěžejní. Řešení optimální trasy je založeno právě na teorii výpočtu tohoto problému. Součástí této práce je záznam provedených početních úkolů v matematickém programu MAPLE včetně popisu kroků, které jsme při výpočtu učinili a nalezení optimální svozové trasy odpadu. Je názorně předvedeno, jak je trasa postupně optimalizována a jak jednotlivé kroky řešení zkracují celkovou svozovou trasu. Aplikace výsledků této práce v praktickém životě tak může vést ke snížení provozních nákladů firmy provozující svoz odpadů.
41
9 SEZNAM POUŽITÉ LITERATURY
1. BARTOŇ, S. Algorithm of General Calculation of Nonlinear Parmaters using LSQ method. In 5th International Congress on Industrial Applied Mathematics. Sydney: UoT Sydney, 2003, s. 98. 2. GANDER, W. -- BARTOŇ, S. Least Squares Fit with Piecewise Functions. In: GANDER, W. -- HŘEBÍČEK, J. Solving problems in Scientific Computing using Maple and Matlab. 4. vyd. 1. Heidelberg: Springer, 2004. s. 433--450. ISBN 3-540-21127-6. 3. BARTOŇ, S. Zerkalnye krivye. In: GANDER, W. -- HŘEBÍČEK, J. Rešenie zadač v naučnych vyčislenijach s primeneniem Maple i MATLAB. Minsk: Vassamedia, 2005. s. 121--134. ISBN 985-6642-06-X. 4. David L. Applegate, Robert E. Bixby, Vašek Chvátal, William J. Cook, The Traveling Salesman Problem: a Computational Study (Princeton Series in Applied Mathematics), Princeton University Press, ISBN-10: 0691129932, ISBN-13: 978-0691129938. 5. E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys, The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization (Wiley Series in Discrete Mathematics & Optimization), Wiley; 1 edition (September 1985), ISBN-10: 0471904139, ISBN-13: 978-0471904137. 6. G. Gutin, A. P. Punnen, The Traveling Salesman Problem and Its Variations (Combinatorial Optimization), Springer; 1 edition (May 18, 2007), ISBN-10: 0387444599, ISBN-13: 978-0387444598. 7. Federico Greco, Traveling Salesman Problem, InTech, ISBN 978-953-7619-10-7 8. Frank Garyan, Chapman and Hall/CRC; 1 edition (November 28, 2001), ISBN-10: 1584882328, ISBN-13: 978-1584882329. 9. Douglas B. Meade, S. J. Michael May, C-K. Cheung, G. E. Keough, Getting Started with Maple, Wiley; 3rd edition (March 23, 2009), ISBN-10: 0470455543, ISBN-13: 9780470455548. 10. Frank Y. Wang, Physics with MAPLE: The Computer Algebra Resource for Mathematical Methods in Physics, Wiley-VCH; 1 edition (April 18, 2006), ISBN-10: 3527406409, ISBN-13: 978-3527406401. 11. Inna Shingareva, Carlos Lizzáraga-Celaya, Maple and Mathematica: a Problem Solving Approach for Mathematics, Springer; 2nd ed. edition (September 29, 2009), ISBN-10: 3211994319, ISBN-13: 978-3211994313.
42
12. Francis Wright, Computing with Maple (Chapman Hall/CRC Mathematics Series), Chapman and Hall/CRC; 1 edition (September 27, 2001), ISBN-10: 1584882360, ISBN13: 978-1584882367. 13. André Heck, Introduction to Maple, Springer; 3 edition (April 8, 2003), ISBN-10: 0387002308, ISBN-13: 978-0387002309. 14. Martha L. Abell, James P. Braselton, Maple By Example, Third Edition, Academic Press; 3 edition (April 4, 2005), ISBN-10: 0120885263, ISBN-13: 978-0120885268 15. Daniel V. Schroeder, An Introduction to Thermal Physics, Addison Wesley; 1 edition (August 28, 1999), ISBN-10: 0201380277, ISBN-13: 978-0201380279. 16. http://valis.cs.uiuc.edu/~sariel/research/CG/applets/tsp/TspAlg.html, Kreimer Natasha 17. http://mat.gsia.cmu.edu/orclass/integer/node10.html, Michael A. Trick 18. Weisstein, Eric W. "Traveling Salesman Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TravelingSalesmanProblem.html 19. http://en.wikipedia.org/wiki/Travelling_salesman_problem 20. http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/, University of Heidelberg 21. Ministerstvo životního prostředí, http://www.mzp.cz/ 22. Zákon č. 185/2001 Sb., o odpadech ve znění pozdějších předpisů 23. http://www.sako.cz/informace/, Sako Brno, a. s. 24. Dokumenty řízení města Brna v oblasti odpadů, http://www.brno.cz/informace/vysledekhledani/?tx_indexedsearch[sword]=odpady&x=0&y=0
25. Google Map API, http://code.google.com/intl/cs/apis/maps/ 26. http://www.volny.cz/jtuhacek/school/paa_tsp/index.htm, Problém obchodního cestujícího, Jiří Tuháček 27. http://www.onic.cz/university/36nan/sem2/sem2.html, Problém obchodního cestujícího, Oldřich Nič 28. http://charon.hkfree.org/~coudek/alg/, Problém obchodního cestujícího, Pavel Dejmek
43
10 SEZNAM TABULEK a OBRÁZKŮ Tabulka č. 4: Tabulka materiálů a jejich písmenných a číselných kódů Tabulka č. 5: Rozdělení separovaných odpadů podle barvy Tabulka č. 6: Adresy ulic, kde jsou umístěny svozové nádoby a jejich vzdálenosti
Obrázek č. 1: Matice vzdušné vzdálenosti mezi jednotlivými body Obrázek č. 2: Znázornění silniční trasy Obrázek č. 3: Prvotní návrh trasy Obrázek č. 4: Křížení trasy jeho řešení Obrázek č. 5: Optimální vzdušná trasa Obrázek č. 6: Silniční trasa pohybu vozidla
44
11 PŘÍLOHA
Tato bakalářská práce je uložena v elektronické podobě na CD nosiči, včetně výpočtů provedených v prostředí MAPLE 13.
45
