Pro gradu -tutkielma Maantiede Geoinformatiikka Tehokkuutta j?tehuoltoon ? tyhjennysreittien optimointi p??kaupunkiseudulla Tomi Aalto 2013 Ohjaaja(t): Petri Pellikka Mika Siljander HELSINGIN YLIOPISTO GEOTIETEIDEN JA MAANTIETEEN LAITOS MAANTIETEEN OSASTO PL 64 (Gustaf H?llstr?min katu 2) 00014 Helsingin yliopisto Sis?llysluettelo 1 JOHDANTO ............................................................................................................................ 1 1.1 Tutkimuksen tausta ...............................................................................................................................1 1.2 Tutkimuskysymykset ja tutkimuksen tavoitteet ....................................................................................6 1.3 Muita optimointia k?sittelevi? pro gradu -tutkielmia ............................................................................7 2 TEOREETTINEN VIITEKEHYS ........................................................................................... 8 2.1 Kuljetustalous ........................................................................................................................................8 2.2 Kuljetusteht?v?t .................................................................................................................................. 12 2.2.1 Kauppamatkustajan ongelma ........................................................................................................ 12 2.2.2 Kiinalaisen postimiehen ongelma .................................................................................................. 12 2.2.3 Ajoneuvon reititysongelma ........................................................................................................... 13 2.2.4 Muut ajoneuvon reititysongelmat ................................................................................................. 14 2.3 Kuljetusteht?vien ratkaisumenetelm?t ............................................................................................... 15 2.3.1 Tarkat menetelm?t ....................................................................................................................... 15 2.3.2 Heuristiset menetelm?t ................................................................................................................ 15 2.3.2.1 Ratkaisua rakentavat menetelm?t ......................................................................................... 16 2.3.2.2 Ratkaisua parantavat menetelm?t ......................................................................................... 17 2.3.2.3 2-vaihe-algoritmit .................................................................................................................. 18 2.3.3 Metaheuristiset menetelm?t......................................................................................................... 18 2.3.3.1 Tabuetsint? ........................................................................................................................... 19 2.3.3.2 Large Neighborhood Search (LNS) .......................................................................................... 19 2.3.3.3 Guided Local Search (GLS) ..................................................................................................... 19 2.3.3.4 Variable Neighborhood Search (VNS) ..................................................................................... 20 2.3.4 Muurahaisyhdyskuntaoptimointi (ACO) ......................................................................................... 20 3 MENETELM?T JA AINEISTOT .........................................................................................21 3.1 Digiroad ............................................................................................................................................... 23 3.2 ArcGIS Network Analyst....................................................................................................................... 23 3.2.1 Vaihe 1: Tieverkoston lis?ys ArcMap:iin.................................................................................... 24 3.2.2 Vaihe 2: Tieverkkoanalyysitason luominen .................................................................................... 24 3.2.2.1 Vehicle Routing Problem ....................................................................................................... 24 3.2.2.2 Route .................................................................................................................................... 28 3.2.3 Vaihe 3: Verkostokohteiden lis??minen ......................................................................................... 29 3.2.4 Vaihe 4: Verkostoanalyysitason asetusten m??ritteleminen .......................................................... 31 3.2.5 Vaihe 5: Analyysien suorittaminen ja tulosten esitt?minen ............................................................ 31 4 TULOKSET ...........................................................................................................................33 5 KESKUSTELU ......................................................................................................................43 6 JOHTOP??T?KSET ...........................................................................................................53 KIRJALLISUUS ........................................................................................................................55 Lyhenteet: ARP ? Arc Routing Problem, kaari reititysongelma NRP ? Node Routing Problem, noodireititys ongelma. TSP ? Travelling Salesman Problem, kauppamatkustajan ongelma. NP ?t?ydellinen ? Non-deterministic Polynomial-time, ep?deterministinen polynomiai- kainen. VRP ? Vehicle Routing Problem, ajoneuvon reititysongelma. VRPTW ? Vehicle Routing Problem with time windows, ajoneuvon reititysongelma ai- ka-ikkunoilla. SPVRPTW ? Stochastic periodic VRP with time windows and a limited number of vehi- cles, Stokastinen periodinen ajoneuvon reititysongelma aikaikkunoilla ja rajallisella kalus- tolla. UA ? Urakka-alue 1 1 Johdanto 1.1 Tutkimuksen tausta Optimointiin liittyv?t ongelmat kuuluvat useamman eri tieteenalan piirin. Niit? voidaan tarkastella esimerkiksi matematiikan, tietojenk?sittelytieteen ja maantieteen n?k?kulmasta. Jokainen tieteenala l?hestyy optimointiongelmia omasta n?k?kulmastaan. Eksaktimmat tieteet, kuten matematiikka ja tietojenk?sittelytiede, k?sittelee kysymyksi? numeerisemmin operaatiotutkimuksen kautta. Maantiede taas k?sittelee enemm?n k?yt?nn?n l?heisemmin esimerkiksi karttojen avulla. Jokaisen eri tieteenalan sis?ll? voi olla jakoa alaryhmiin. Esi- merkiksi maantieteess? erityisesti geoinformatiikka on erikoistunut optimointikysymyksiin. Geoinformatiikan ty?v?lineist? on tullut yksi keskeisimmist? elementeist? logistiseen suunnitteluun (Karadimas et al. 2008). Optimoinnilla viitataan yleens? parhaimman ratkai- sun tai toimintaperiaatteen etsimiseen ja l?yt?miseen (Br?ysy 2007:6). Tehokas hy?dyk- keiden jakelu on eritt?in t?rke??, ei ainoastaan logistiikan tuottajien taloudellisen selvi?mi- sen kannalta, vaan my?s kokonaisten alueiden talouden kilpailukyvyn kannalta (Kyt?joki et al. 2007). Optimoimalla kuljetuksia voidaan alentaa tuotteiden ja palveluiden hintaa ku- luttajille. Br?ysy on havainnollistanut (kuva 1.) artikkelissaan (2007:11) optimoinnilla saa- vutettavia hy?tyj?. Optimoinneilla voidaan tavoitella esimerkiksi kustannus-s??st?j?, ty?n tehostumista, liikenteen p??st?jen v?hentymist? (ymp?rist?n kuormittavuus) ja ty?n kuor- mittavuuden tasaamista. Lis?ksi asiakkaiden palvelutasoa voidaan kasvattaa sek? parantaa tilausten ja kaluston hallintaa. Taloudellisten etuisuuksien saavuttaminen on taas t?rke? tekij? mink? tahansa talouden, niin yksityisen kuin julkisenkin, kilpailukyvyn kannalta. 2 Kuva 1. Optimoinnilla saavutettavat hy?dyt (Br?ysy 2007:11). Julkisesti ymp?ri maailman ollaan huolissaan j?tteen m??r?n lis??ntymisest? l?nsimaisten elintapojen laajenemisen ja elintason nousun my?t? (esimerkiksi Angelelli & Speranza 2002). Yleisesti ollaan yht? mielt? siit?, ettei j?tteiden sijoittaminen kaatopaikoille ole j?r- kev??. Kaatopaikat viev?t paljon tilaa, niist? tulee haju ja melu haittoja sek? myrkyllisi? p??st?j? ilmakeh??n ja vesist?ihin. J?tteiden lajittelu ja kierr?tt?minen on ymp?rist?n kan- nalta huomattavasti parempi vaihtoehto. Suomessa kotitalouksien j?tteist? kierr?tet??n yleisesti paperia, kartonkia, bioj?tteit?, energiaj?tteit?, lasia ja metallia. Kiinteist?jen kier- r?tyst? koskevat m??r?ykset kiristyv?t jatkuvasti. Br?ysyn mukaan (2007) erilaisissa tutkimuksissa on osoitettu, ett? jo silloin jos ohjattavia ajoneuvoja on viisi, on ihmisell? vaikeuksia m??ritt?? ajoneuvoille optimaalista teht?v?- luetteloa, reitti? ja aikataulua. N?ihin seikkoihin, kierr?tyksen lis??ntymisen ja kasvavan teht?v?joukon reititt?misen hankaloitumiseen, vedoten nykyinen niin sanottu kokemuspe- r?inen reititt?misen voidaan katsoa tulleen tiens? p??h?n. Kokemusper?inen reititt?minen 3 on pohjautunut perinteisiin menetelmiin. K?yt?nn?ss? t?m? on tarkoittanut kyn??, paperia, karttaa ja jonkinlaista k?yt?nn?n kokemusta. Liiketoiminnan kehittyess? ja kasvaessa asi- akkaita on tullut lis?? ja reittien m??r? on lis??ntynyt. Ajoreitit ovat jaettu tietyll? perus- teella, esimerkiksi maantieteellisesti. Joidenkin tekij?iden perusteilla yksi alue kuuluu tiet- tyyn ajopiiriin ja toinen alue toiseen piiriin. Hiljalleen reiteille on tullut uusia asiakkaita ja niiden loogisuus sek? eheys ovat heikentyneet ja siten optimaalinen kannattavuus laskenut. Piirit (reitit) voivat olla jaettu sen mukaan kuinka kauan suorittamiseen on keskim??rin joltain ty?ntekij?lt? kulunut aikaa. Ajank?ytt? vaihtelee monesti ty?ntekij?n kokemuksen ja motivaation mukaan. Lis?ksi siihen vaikuttavat k?ytett?viss? oleva kuljetuskalusto ja sen ominaisuudet (muun muassa kapasiteetti) ja muut ulkoiset tekij?t kuten tiest? ja ruuhkai- suus. J?tekuljetusten j?rjest?minen on yksi kuntien haastavimmista operatiivisista teht?vist? (esimerkiksi Nuortio et al. 2006). Br?sy (2007:17) n?kee erityisen? ongelmana optimoinnin kokoluokan ja tarpeen p?ivitt?isten reittien m??rittelyn lis?ksi asiakaspisteiden jaottelun sopiville ker?ysp?iville. Huoli ymp?rist?n tilasta, terveyshaitoista on lis?nnyt kuntien ja kaupunkien tarvetta arvioida j?tehuollon toteutusta, kustannustehokkuutta ja ymp?rist?vai- kutuksia. Joidenkin tutkimusten mukaan j?tehuoltoon k?ytetyst? taloudellisista voimava- roista 60?80 prosenttia k?ytett?isiin ker?ys ?vaiheessa (Karadimas et al. 2008). Kuvassa 2 on esitetty reitinoptimoinnin toimintamalli. Kulloinkin k?ytett?v? optimointiarsenaali (k?y- tetyt algoritmit ja heuristiikat ja niin edelleen) riippuu paljon siit?, mitk? ovat optimoinnin tavoitteet ja millaiset tavoitteet sille on asetettu. Eri tilanteilla voi olla erilaisia tavoitteita, esimerkiksi k?ytett?viss? olevasta resursseista (ajoneuvot, toimipisteet, kuljettajien m??r?) riippuen. Tyypillisi? optimoinnin parametreja ovat optimointikriteeri (matka, aika, kustan- nukset, t?ytt?aste jne.), et?isyys- ja nopeusyksik?t, autonkuljettajien ty?vuorojen ja tauko- jen pituudet, tunti- ja ylity?korvaukset ja niin edelleen. 4 Kuva 2. Reitinoptimoinnin toimintamalli (Br?ysy 2007:9). J?tteiden m??r?n vaihtelu aiheuttaa lis?ongelmia optimointiin. J?tem??riin vaikuttavia teki- j?it? ovat muun muassa kuinka monta asukasta tuo j?tteit? tiettyyn ker?ysv?lineeseen, asukkaiden tulotaso, el?m?ntavat, ajankohta ja niin edelleen. Ajallisesta vaihtelusta mainit- takoon, ett? esimerkiksi joulukuussa j?tett? tuotetaan huomattavasti enemm?n kuin helmi- kuussa. My?s koulujen alkamisen ja loppumisen aikoihin kev??ll? ja syksyll? j?tem??r?t kasvavat. Logistiikan alalla on monia mahdollisuuksia optimointiin. Kuljetus ja jakelutoiminnan osalta ne voidaan jakaa kolmelle tasolle. Strategisen tason suunnittelussa pyrit??n sijoitta- maan varastot, varikot ja muut toimitilat tehokkaasti. Taktisella tasolla optimoidaan tarvit- tavan kuljetuskaluston kokoa ja tyyppi?. Toiminnallisen tason optimoinnissa pyrit??n te- kem??n ajoreiteist? ja aikatauluista mahdollisimman kustannustehokkaat. J?tteenkuljetuksen optimoinnin erityispiirteit? muun muassa Br?ysyn (2007:8) mukaan: - Paljon asiakaspisteit? - Rajallinen kapasiteetti - Vaihtelevat j?tem??r?t 5 - Temporaaliset ?vaihtelut: ? Vuoden aikaiset vaihtelut ? Vuosien v?liset erot (taantumat vs. suhdannehuiput) - Erilaiset ker?ysv?lineet ja ajoneuvot Erityisesti j?tehuollon reitti- ja optimointiongelmien ratkaisemiseksi on Suomessa ja muu- alla maailmalla kehitetty useita heuristisia ja meta-heuristisia algoritmeja (esimerkiksi Ky- t?joki et al. 2007). Algoritmill? tarkoitetaan Sipsterin (2006) mukaan yksiselitteisesti ku- vattua tietojenk?sittelyoperaatioiden jonoa, jotka voidaan toteuttaa mekaanisesti. Reittiop- timointi ?algoritmit pohjaavat vanhoihin reittiongelmiin, kuten niin sanottuihin kauppa- matkustajan ongelmaan ja postimiehen ongelmaan. N?iden erilaisten algoritmien v?lisi? tekij?it? on korostettu muun muassa asiakaspisteiden m??r?ll?, erilaisten vaihtuvien teki- j?iden m??r?ll? (aikaikkunat, lepoajat, useat tyhjennyspisteet ja niin edelleen) ja optimoin- tien laskentaan kuluvalla ajalla. Tyypillisess? j?tehuollon reititysongelmassa on yksi tai useampia j?tteenk?sittelylaitoksia, tietty asiakaskunta kenelt? j?tteet ker?t??n ja m??rittelem?tt?m?sti ominaisuuksiltaan sa- manlaista kuljetuskalustoa, jotka l?htev?t liikkeelle yhdelt? varikolta (Kyt?joki et al. 2007; Karadimas et al. 2008). Kuljetuskalusto l?htee varikolta tyhj?n? ja ker?? j?tteet asiakkailta. Tyhjennys tapahtuu j?tteenk?sittelylaitokselle tarvittaessa. Useimmiten tyhjennys tapahtuu kerran tai useita kertoja ty?vuoron aikana. Kuljetuskalusto palaa varikolle aina tyhj?n?. Usein erilaiset aikaikkunat otetaan huomioon, jotka koskevat muun muassa asiakkaita, j?tteenk?sittelylaitoksia ja varikkoa. My?s kuljettajien lepoajat, kuten lounas- ja kahvitauot tulisi huomioida. Benjamin ja Beasleyn (2010) artikkeli k?sittelee t?llaista ongelmaa solmu/noodi reitityson- gelmana (Node Routing Problem, NRP), kun taas Nuortio el al. (2006) n?kev?t sen enem- minkin kaari reititysongelmana (Arc Routing Problem, ARP). Jako kahteen erilliseen ryh- m??n riippuu muun muassa siit?, k?sitteleek? ongelmaa yksitt?isen? reittin? vai useampaan kertaan suoritettavana toistuvana toimenpiteen?. ARP on luonteva tapa mallintaa j?tehuol- lon tilannetta silloin, kun suurin osa tai kaikki tietyn alueen kuljetusv?lineist? pit?? tyhjen- t?? samaan aikaan. Nuortio et al. (2006) n?kev?t, ett? ARP toimii yleens? parhaiten tihe?sti asutetuilla alueilla, joilla kuljetusv?lineet sijaitsevat l?hell? toisiaan. NRP mahdollistaa puolestaan paljon tarkempaan mallintamiseen, koska siin? jokainen kuljetusv?line voidaan k?sitell? erikseen ja n?in saatava tulos on yksityiskohtaisempi. NRP soveltuu my?s pa- 6 remmin aluille, jotka ovat harvemmin asuttuja, eli kuljetusv?lineiden (asiakaspisteiden) v?linen et?isyys on pidempi. Aihetta k?sitteleviss? tieteellisiss? artikkeleissa ongelma on jaoteltu siten, ett? kotitalouksien j?tehuolto kuuluu ARP- ryhm??n ja toisaalta kaupan sek? teollisuuden sektori NRP ?ryhm??n (esimerkiksi Kyt?joki et al. 2007; Benjamin & Beasley 2010). Muista ARP:n soveltuvuuksista voidaan mainita esimerkiksi katujen auraus. 1.2 Tutkimuskysymykset ja tutkimuksen tavoitteet T?ss? pro gradu ?tutkielmassa k?sitell??n olemassa olevan, p??kaupunkiseudulla toimivan, kuljetusyrityksen ajoneuvon reititysongelmaa, jossa on tietty m??r? tyhjennett?vi? asiakas- pisteit? (j?tepisteit?) ja rajattu ajoneuvojen lukum??r?, jossa rajallinen kapasiteetti. Kulje- tustalouden kustannusrakenteen ja ymp?rist?tietoisuuden kasvun takia turhien ajokilomet- rien v?ltt?minen on nyky??n korostunut. Muuttuvat kustannukset ja p??st?t ovat sit? kor- keammat mit? enemm?n ajetaan. Lis?ksi huonosti optimoiduilla kuljetuksilla on vaikutusta my?s ty?kustannuksiin, esimerkiksi lis??ntynein? ylity?kuluina. Toisaalta se voi vaikuttaa jopa kiinteisiin kustannuksiin, jos kaluston m??r?ss? on ylimitoitusta heikon optimoinnin takia. Tutkimuksen tarkat tutkimuskysymykset ovat seuraavat: Voidaanko ohjelmallisella rei- tinoptimoinnilla saavuttaa kuljetustaloudellisia s??st?j? verrattuna nykyiseen ?kokemuspe- r?iseen? optimointiin? Ja jos voidaan niin kuinka suuria mahdolliset s??st?t voisivat olla? Mink?laisia reaalisia tekij?it? tulisi huomioida ohjelmallisessa reitinoptimoinnissa? Tutkimuskysymyksi? l?hestyt??n t?ss? tapauksessa viidell? reitill?. Todellisia ajettuja reit- tej? vertaillaan optimoituihin reitteihin. Tutkimuksessa mukana olevat j?tepisteet sijaitse- vat kaikki p??kaupunkiseudulla. Mukana olevat reitit edustavat tyypillisi? yleisten j?tepis- teiden j?tteentyhjennysreittej?. Tutkielman ensimm?isess? osassa k?yd??n l?pi aiheeseen liittyv?? viitekehyst?, esitell??n tutkimusongelma ja kysymykset sek? taustoitetaan j?tehuollon ja kuljetustalouden erityis- piirteit?. Toisessa osassa k?yd??n l?pi kuljetusteht?viin liittyv?t yleiset ongelmatyypit. Kolmannessa osassa esitell??n joukko ajoneuvon reititysongelmiin yleisesti tunnettuja ja k?ytettyj? ratkaisumenetelmi?. Nelj?nness? luvussa k?yd??n l?pi tutkimuksen empiirisess? osassa k?ytett?v?t aineistot ja menetelm?t. Tulokset esitet??n viidenness? osassa. Sit? seu- raa keskustelu, jossa analysoidaan tuloksia syv?llisemmin Tutkielman p??tt?? johtop??t?k- set -kappale, jossa vedet??n lyhyesti yhteen tutkimuksen tulokset. 7 1.3 Muita optimointia k?sittelevi? pro gradu -tutkielmia Kalle Hyyrynen k?sitteli Pro Gradu ?ty?ss??n (2008) hy?tyj?tteiden alueker?yspistever- koston optimointia p??kaupunkiseudulla. Sijaintipaikkoja optimoimalla pystytt?isiin Hyy- rysen mukaan pienent?m??n verkoston kokoa 45 ker?yspisteell? ja samalla kuitenkin kas- vattamaan ker?yspisteiden palvelupeitt?vyytt? yli 40 000 asukkaalla. Hyyrysen mukaan j?tehuollon kannalta pienempi alueker?yspisteverkosto v?hent?? ker?ysty?st? ja verkoston yll?pidosta aiheutuvia p??st?j?. Tutkimus osoitti geoinformatiikan ja paikkatiedon hy?dyl- lisyyden j?tehuollon suunnittelussa ja p??t?ksenteossa. Juha Tolvanen tutki Pro gradussaan (2007) Postin perusjakeluntoimipaikan sijainnin mal- lintamista ja optimointia. Optimointi tuotti tuloksena noin 20 prosentin tehokkuuden silloi- seen tilanteeseen verrattuna. Tutkimus osoitti, ett? paikkatiedolla ja geoinformatiikan me- netelmill? pystyt??n tukemaan Postin perusjakelun p??t?ksentekoa ja suunnitteluty?t?. Helsingin Yliopiston maantieteen laitoksen optimoinnin klassikkona voidaan todenn?k?i- sesti pit?? Jaakko Suikkasen kev??ll? 2002 julkaisemaa Pro gradu ?tutkielmaa p??kaupun- kiseudun kiireellisten sairaankuljetusyksik?iden asemapaikkojen optimointia paikkatieto- j?rjestelmien avulla. Silloista nykytilannetta vastaavalle m??r?lle asemia etsittiin optimaa- lisemmat sijaintipaikat maksimoimalla asukkaiden peitt?vyys k?ytetyll? viiden minuutin ajoajalla (Suikkanen 2002). Optimoinnissa k?ytettiin sek? GRIA- ett? TAB ?heuristiikkoja. Peitt?vyys parantui 21?23 prosenttia riippuen asemien lukum??r?st?. Tutkimus osoitti, ett? k?ytetyt menetelm?t soveltuvat hyvin normatiiviseen suunnitteluun. Teemu Tapanaisen Pro gradu ?ty? (2010) k?sittelee luonnossa liikkujan kulkukelpoisuus- analyysin parantamista tarkoilla maastotiedoilla. Kulkukelpoisuus analyysia pyrittiin ty?s- s? parantamaan kustannuspinta-analyyseill?. Se on yleisnimitys joukolle paikkatietomene- telmi?, jossa m??ritell??n rasterikartan soluille l?pikulkukustannusta kuvaavia arvoja ja lasketaan kustannuset?isyyksi? levi?misalgoritmien avulla. Tapanaisen mukaan analyysien avulla voidaan tehd? muun muassa matka-aikakarttoja, reitinoptimointeja ja k?yt?v?ana- lyysej? (2010). Tutkimuksen kulmakiven? oli uudet, tarkemmat, laserkeilatut maastotiedot. 8 2 Teoreettinen viitekehys 2.1 Kuljetustalous Kustannustekij?iden ryhmittely tarkoituksenmukaisella tavalla muodostaa autokuljetusten kustannuslaskennan rungon. Kuvassa kolme on esitetty eri kustannustekij?iden keskim??- r?iset osuudet kokonaiskustannuksista. Koska osa kustannuksista on riippumattomia siit? ajetaanko ajoneuvolla tai ei, on kustannustekij?t yleens? jaoteltu Maukosen (2012) mukaan niiden luonteensa perusteella seuraavasti: Kuljettajan ty?kustannukset: - kuljettajan palkka - v?lilliset palkkakustannukset - p?iv?rahat ja majoituskulut Muuttuvat kustannukset: - polttoainekustannukset - lis?ainekustannukset - voiteluainekustannukset (ellei sis?llytetty huoltokuluihin) - korjaus- ja huoltokustannukset - rengaskustannukset Kiinte?t kustannukset: - p??omakustannukset - vakuutukset - liikenn?imismaksut - yll?pitokustannukset - hallintokustannukset - muu ajo (ellei se jo sis?lly muuttuviin kustannuksiin) Yritt?j?riski: - sis?lt?? mahdollisen yritt?j?voiton ja verottajan osuuden siit? 9 Kuva 3. Kustannustekij?t ja niiden osuudet kuorma-autoliikenteess? marraskuussa 2011 (Tilastokes- kus 2012). Kustannusten jakaantuminen vaihtelee huomattavasti eri ajoteht?viss? ja erilaisilla ajoneu- voilla. Kustannuksien osuuksien tunteminen on avainasemassa siihen, mihin optimointi- menetelmi? kannattaa kohdistaa suurimpien kustannus-s??st?jen saavuttamiseksi. Laskel- man (Taulukko 1) l?ht?tietoina k?ytet??n sellaisia kustannustietoja, joista on v?hennetty ne arvonlis?verot, jotka my?s yritys voi v?hent?? omassa toiminnassaan (Anttila 2012). T?ll? periaatteella tehty laskelma vastaa kuljetusmaksua ilman arvonlis?veroa, joten se on lis?t- t?v? erillisen? summana varsinaisen kuljetusmaksun p??lle. Ryhdytt?ess? hinnoittelemaan tietty? kuljetusteht?v?? on ensimm?iseksi m??ritelt?v? kustannuslaskennalla ajoneuvon vuotuiset kokonaiskustannukset. N?iden kustannuksien selvitt?miseksi on laskentaa varten laadittava perusteet, jotka muodostuvat seuraavista osatekij?ist? (Anttila 2012): - ajoneuvo ja sen uushankintahinta - ajosuorite vuodessa - ajoneuvon pitoaika - polttoaineen kulutus - Lis?aineen kulutus - renkaiden kestomatka 40 % 27 % 11 % 7 % 5 % 4 % 3 % 2 % 1 % Eri kustannustekij?iden keskim??r?iset osuudet kuorma-autoliikenteen kokonaiskustannuksista Ty?kustannukset Polttoainekustannukset P??omakustannukset korjauskustannukset Vakuutukset Rengaskustannukset hallintokustannukset Yll?pitokustannukset Liikenn?imismaksut 10 - k?ytt?- ja palkkatunnit. Ajoneuvon ja sen varusteiden hankintahintoina tulee k?ytt?? aina uushankintahintaa, jotta inflaation vaikutus pystytt?isiin huomioimaan laskelmissa. Lis?ksi p??omakustannusten laskentakaavat ottavat huomioon kaluston koko pitoajan p??omakustannukset keskim??r?i- sen? vuotta kohden. Vuotuinen ajosuorite saadaan lasketuksi joko kuukauden ajokilometrim??r?n ja ajokuukau- sien tai vuotuisten ajokertojen ja kuljetuset?isyyden perusteella. J?lkimm?isess? tapaukses- sa joudutaan m??rittelem??n yhden keikan kestoaika ja t?m?n j?lkeen lasketaan kuinka monta ajokertaa suoritetaan normaaliolosuhteissa vuoden aikana. Vuotuista ajosuoritetta m??ritelt?ess? tulee huomioida ajoneuvon huolto- ja korjaust?ist? aiheutuneet seisontap?i- v?t. Ajoneuvon taloudellinen k?ytt?ik? ja pitoaika riippuvat useista eri tekij?ist? kuten esimer- kiksi suoritealasta, ajoneuvotyypist?, ajoneuvon toiminnan varmuudelle asetettavista vaa- timuksista ja niin edelleen. Ajoneuvon polttoaineen kulutus riippuu my?s useista eri tekij?ist? kuten esimerkiksi ajo- olosuhteista, kuljetuset?isyydest?, ajoneuvon kokonaismassasta, ajonopeudesta, ilmanvas- tuskertoimesta, renkaista, moottorin kunnosta, ajotavasta ja lis?laitteiden k?yt?st?. 11 Kuljetuslaji: J?tteenkuljetus Uushankintahinnat ALV = 0 % Ajoneuvo: 2-akselinen kuorma-auto Auton alusta ? 75000 Per?vaunu: Kuormatila tai vastaava ? 25000 Lis?laitteet: Takalaitanostin Per?vaunu ? 0 Lis?laitteet ja varusteet ? 8300 Kokonaismassa 18 tonnia Auton renkaat 6 a-hinta 550 ? -3300 Kantavuus 9 tonnia Pv:n renkaat 0 0 ? 0 Hy?tykuorma 6 tonnia Hinta renkaitta ? 105000 Ajosuorite (kuljetusteht?vien vaatimat ajokilometrit vuodessa) km/a 60000 Muu ajo (huolto-, kotimatka- ym. ajot) km/a 3000 Ajokilometrit yhteens? vuodessa km/a 63000 Auton k?ytt?matka koko pitoaikana km 315000 Auton alustan pitoaika vuosina a 5,0 Auton kuormatilan pitoaika vuosina a 10,0 Per?vaunun pitoaika vuosina a 0,0 Lis?laitteiden ja varusteiden pitoaika vuosin a 10,0 Polttoaineen kulutus keskim??rin l/100 km 30 Lis?aineen (AdBlue) kulutus keskim??rin l/100 km 2 Renkaiden kestomatka (uusien ja pinnotettujen keskiarvo) km 100000 Ajoneuvon k?ytt?tunnit kuljetusteht?viss? h/a 2500 Kuljettajien palkkatunnit 10 %:n apuaikalis?ll? h/a 2750 Kuljettajien keskipalkka 13,12 ?/h (sis?lt?en ilta-, y?-, ym. lis?t) ?/a 36080 V?lilliset palkkakustannukset 70 % (mm. sosiaalikulut ja lomarahat) ?/a 25256 P?iv?rahat ja majoituskulut 2800 ?/vuosi ?/a 2800 Ty?kustannukset yhteens? ?/a 64136 Ty?kustannukset k?ytt?tuntia kohti ?/h 25,65 Polttoainekustannukset, hinta 0,830 ?/litra ?/km 0,249 Lis?ainekustannukset (AdBlue) 0,800 ?/litra ?/km 0,016 Korjaus- ja huoltokustannukset 6500 ?/vuosi (pitoaikana keskim.) ?/km 0,103 Rengaskulut, pinnoitekustannus 275 ?/kpl, pinnoituskerrat 1 kpl ?/km 0,025 Muuttuvat kustannukset yhteens? ?/km 0,393 Poistot ?/a 24759 Arvonaleneminen alusta 23 % vuosittain ?/a 10458 Arvonaleneminen kuormatila 21 % vuosittain ?/a 2263 Arvonaleneminen per?vaunu 0 % vuosittain ?/a 0 Arvonaleneminen lis?laitteet 19 % vuosittain ?/a 729 Arvonaleneminen yhteens? ?/a 13450 P??oman korko (kuluineen) 6 % ?/a 3605 K?ytt?p??oman korkokulut 10 % edellisest? ?/a 361 Vakuutusmaksut (liikenne-, auto-, kuljetus- ym. vakuutusmaksut) ?/a 5500 Liikenn?imismaksut (ajoneuvoverot ja katsastusmaksut) ?/a 1300 Hallintokustannukset (kirjanpito, atk, puhelinkulut, j?senmaksut ym.) ?/a 3700 Yll?pitokustannukset (s?ilytys, puhtaanapito ja pienvarustekulut) ?/a 1700 Kiinte?t kustannukset yhteens? ?/a 29616 ?/kk 2468 Kustannukset yhteens? ennen yritt?j?riskin lis?yst? ?/a 118511 Yritt?j?riski 10 % kokonaiskustannuksista ?/a 13168 ?/km 0,219 Kokonaiskustannukset vuodessa yhteens? ?/a 131679 Tuntikustannukset k?ytt?tuntia kohti keskim??rin ?/h 52,67 Kilometrikustannukset ajosuoritetta kohti keskim??rin ?/km 2,195 Yhdistetty kustannus (esimerkki): ty?kustannukset + kiinte?t kustannukset ?/h 37,50 muuttuvat kustannukset + toimintaylij??m? ?/km +0,632 Taulukko 1. Ajoneuvokohtainen kustannuslaskelma (muokattu Anttila 2012 pohjalta). 12 2.2 Kuljetusteht?v?t 2.2.1 Kauppamatkustajan ongelma Kauppamatkustajan ongelmassa (Travelling Salesman Problem, TSP) tavoitteena on l?yt?? kustannukset minimoiva reitti (Kuva 4), kun kauppamatkustaja aloittaa kotikaupungistaan ja kulkee tasan kerran jokaisen etuk?teen m??r?tyn kaupungin l?pi palaten takaisin koti- kaupunkiinsa (Flood 1956). Varsin yksinkertaisesta teht?v?nannosta huolimatta kauppa- matkustajan ongelma kuuluu niin sanottuun NP ?t?ydellisiin (Non-deterministic Po- lynomial-time) teht?viin, mik? tarkoittaa sit?, ett? ongelman ratkaisemiseen ei l?ydy teho- kasta polynomiaikaista algoritmia, vaan ratkaisuaika kasvaa eksponentiaalisesti ongelma- kokoa kasvatettaessa (muun muassa R?is?nen 2009, De Smith et al. 2009). Kuva 4. Kauppamatkustajan ongelman esimerkkiratkaisu. 2.2.2 Kiinalaisen postimiehen ongelma Kiinalaisen postimiehen ongelma on er?s graafiteorian tunnetuimmista matemaattisista ongelmista. Siin? oletetaan, ett? kiinalaisen postinkantajan pit?? jakaa postia tietyll? alueel- la. Koska postinkantaja on laiska, haluaa h?n l?yt?? mahdollisimman lyhyen jakelureitin alueensa l?pi siten, ett? aloitus- ja lopetuspiste on sama ja jokainen katu menn??n l?pi v?- hint??n kerran (Eiselt 1995). 13 2.2.3 Ajoneuvon reititysongelma Ajoneuvon reititysongelma (Vehicle Routing Problem, VRP) on perusm??ritelm? kuljetus- ongelmille, joissa etuk?teen m??ritetyt asiakkaat sijoitetaan kuljetusreitille, siten ett? yh- dell? ajoneuvolla on yksi reitti, joka alkaa ja loppuu varastolta/varikolta (depot) (Kuva 5) (muun muassa Sahoo et al. 2005). Reitin lis?ksi ajoneuvolle on m??ritelty maksimi kapasi- teetti. Reittej? on niin monta, ett? jokaisen asiakkaan kysynt? tai tilaukset (demand/orders) ovat tyydytetty siten ett? kokonaismatkakustannus on minimoitu. Kyseisen ongelman for- muloi ensimm?isen kerran Dantzig ja Ramser (1959), kun he etsiv?t optimaalista ratkaisua bensiini? kuljettavien s?ili?autojen reititt?miseksi varastoterminaalilta suurelle joukolle huoltoasemia. Ajoneuvon reititysongelma on yksi laajimmin tutkittu kombinatorinen opti- mointiteht?v?. Se on t?rke? ongelma kuljetusten, jakelun ja logistiikan tieteenalalla. Ajo- neuvon reititysongelma luokitellaan NP ?vaikea luokan ongelmiin, ja on siten astetta vai- keampi teht?v? kuin kauppamatkustajan ongelma (R?is?nen 2009). T?llaisille ongelmille ei aina ole mahdollista l?yt?? ratkaisua riitt?v?n nopeasti, mink? vuoksi joudutaan usein tur- vautumaan approksimatiivisiin ratkaisuihin optimaalisten sijaan. Approksimatiiviset rat- kaisut saadaan yleens? tarpeeksi nopeasti ja ovat riitt?v?n hyvi? k?ytt?tarkoitukseen. On- gelman kompleksisuus johtuu siis monista eri vaihtoehdoista jotka joudutaan ottamaan huomioon. Br?ysyn mukaan: ?Monissa sovelluksissa mahdollisia ratkaisuvaihtoehtoja on enemm?n kuin atomeja maailmankaikkeudessa.? (2007:6?7). Ongelman ratkaisemiseksi on kehitetty monia algoritmeja. Heurististen algoritmien k?ytt?minen on er?s syy niiden kor- keaan lukum??r??n. Heuristiset algoritmit ovat Karadimas et al. (2008) mukaan tilap?isi?, kokeilullisia metodeja, jotka eiv?t v?ltt?m?tt? anna t?ysin optimaalista vastausta. Sen si- jaan ne antavat l?hes optimaalisia tuloksia huomattavan nopeasti. 14 Kuva 5. Ajoneuvon reititysongelman esimerkkiratkaisu. 2.2.4 Muut ajoneuvon reititysongelmat Stokastiseen ajoneuvon reititysongelmaan (Stochastic VRP) kuuluvat yksi tai useampi sa- tunnainen komponentti. N?m? liittyv?t keskeisesti k?yt?nn?n ajoneuvojen reititt?mison- gelmiin. Yleisi? esimerkkej? satunaisista tekij?ist? voivat olla esimerkiksi asukkaiden sa- tunnaiset kysynn?t, matka-ajat ja palveluajat (Dror et al. 1989; Gendreau et al. 1996). Stokastinen periodinen ajoneuvon reititysongelma aikaikkunoilla ja rajallisella kalustolla (Stochastic periodic VRP with time windows and a limited number of vehicles - SPVRPTW). J?tehuollon reititysongelmat ovat yleens? aina luonteeltaan stokastisia, koska niihin liittyy paljon ep?varmuustekij?it?. Ep?varmuustekij?it? voivat olla esimerkiksi et?i- syydet, kysynt? tai asiakkaiden olemassaolo (Nuortio et al. 2006). Periodinen ajoneuvon reititysongelma k?sittelee tilannetta, jossa optimaaliset reitit pit?? selvitt?? kaikille p?iville tietyll? ajanjaksolla. T?t? kutsutaan Nuortio et al. (2006) mukaan allokaatio reititt?miseksi (allocation-routing), koska optimaalisten reittien lis?ksi asiakkaat tulee ryhmitell? tietyille p?iville. Ajoneuvon reititysongelma aikaikkunoilla voi tarkoitta sit?, ett? osalla tai kaikilla asiakkailla tulee olla k?ytyn? tiettyn? aika, esimerkiksi 07.00 ? 12.00 v?lisen? aikana. Ai- kaikkunoita voi asettaa my?s joustaviksi, jolloin sit? voidaan rikkoa esimerkiksi tietty? sakkoa (ajallinen, rahallinen) vastaan. 15 Kirjallisuudessa ajoneuvojen m??r? asetetaan usein yhdeksi optimoinnin tavoitteeksi. K?y- t?nn?ss? kuljetusyrityksill? on k?yt?ss??n tietty ajoneuvokapasiteetti, jonka k?ytt? pyrit??n saamaan mahdollisimman tehokkaaksi. Tieteellisess? kirjallisuudessa t?ll? tarkoitetaan ajoneuvon reittiongelmaa rajoitetulla kuljetuskalustolla. 2.3 Kuljetusteht?vien ratkaisumenetelm?t 2.3.1 Tarkat menetelm?t Er?s kuljetusongelmien tarkoista ratkaisumenetelmist? on niin sanottu Branch-and-bound ? algoritmi, jonka esitti Land ja Doig (1960). Siin? kokonaisratkaisun l?yt?miseen k?yte- t??n ?haaraudu ja rajoita? ?l?hestymistapaa. B&B ?menetelm? hakee optimiratkaisua kaikkien ratkaisukandidaattien joukosta hajottamalla sen osiin yh? uudelleen ja uudelleen. T?st? seurauksena muodostuu puurakenne, jonka solmut esitt?v?t ratkaisujoukkojen osa- joukkoja. Menetelm?ss? k?ytet??n hyv?ksi l?ydettyjen optimiratkaisujen ala- ja yl?rajoja, n?iden avulla selvi??, kannattaako tietyn osajoukon tutkimista jatkaa (R?is?nen 2009). Branch-and-cut ?menetelm?t perustuvat branch-and-boundiin ja leikkaustaosjen (cutting plane) yhdist?miseen (Toth & Vigo 2002). B&C muuntaa osateht?vi?, jotka eiv?t t?yt? kokonaislukuvaatimuksia, lis??m?ll? alkuper?isten rajoitusten joukkoon leikkaustasoja. Vaikka B&C sopii hyvin vaikeiden kombinatoristen optimointiongelmien ratkaisemiseen, voi sen tehokkuus olla heikko jos jokin sen osa on huonosti suunniteltu. Naddef ja Rinaldi (2002) huomauttavat muun muassa seuraavista asioista: - leikkaustasovaiheeseen ei ole k?ytett?viss? hyv?? algoritmi? - leikkaustasovaiheen iteraatioiden lukum??r? on liian suuri - haarautumisen synnytt?m? puu kasva liian suureksi, jotta sen loppuun laskeminen olisi mahdollista j?rkev?ss? ajassa 2.3.2 Heuristiset menetelm?t Heuristiset menetelm?t ovat ratkaisumenetelmi?, jotka eiv?t v?ltt?m?tt? l?yd? optimaalista ratkaisua kuten tarkat menetelm?t. Ne ovat suunniteltu antamaan nopeasti ?kohtuullisen hyvi?? ratkaisuja. Heuristiset menetelm?t soveltuvat tilanteisiin, joissa ratkaisu pit?? l?yt?? nopeasti, optimaalisen ratkaisun hakeminen kest?? huomattavasti kauemmin kuin l?hes optimaalisen tai optimaalista ratkaisua ei v?ltt?m?tt? tarvita. Klassiset heuristiikat voidaan Kyt?joki et al. (2007) mukaan jakaa kolmeen ryhm??n. Ratkaisua rakentavat heuristiikat 16 muodostavat k?yv?n ratkaisun yleens? ahneella tavalla, mutta eiv?t sis?ll? parannusvaihet- ta. Ratkaisua parantavat heuristiikat yritt?v?t vied? soveltuvaa ratkaisua pidemm?lle suorit- tamalla per?kk?isi? asiakaskaarien tai ?solmujen vaihtoja reitin sis?ll? tai reittien v?lill?. 2- vaihe ?algoritmit jakavat ongelman asiakassolmujen klusterointiin k?yviksi reiteiksi ja varsinaisen reitin rakentamiseen. N?m? kaksi vaihetta voivat toimia iteratiivisesti tiedon v?littyess? tasolta toiselle. 2.3.2.1 Ratkaisua rakentavat menetelm?t Ratkaisua rakentavat heuristiikat aloittavat tyypillisesti tyhj?st? ratkaisusta, josta rakenne- taan kokonainen reitti lis??m?ll? siihen vaiheittain lis?? asiakkaita. Asiakkaat valitaan jon- kin kustannuksia minimoivan kriteerin perusteella siten, ett? ratkaisu ei riko mit??n ajo- neuvon kapasiteetti- tai aikaikkunarajoituksia, jolloin ratkaisu s?ilyy k?yp?n?. Kim et al. (2006) mukaan reittien rakentamisalgoritmit voidaan jakaa per?kk?isten (sequantial) ja rinnakkaisten (parallel) menetelmien ryhmiin. Ryhm?t eroavat siin?, kuinka monta reitti? rakennetaan kerrallaan. Per?kk?isess? ?menetelmiss? laajennetaan vain yht? reitti? kerral- laan, jolloin uusia asiakkaita voidaan lis?t? vain sill? hetkell? rakennettavalle reitille (Christofides et al. 1979; Solomon 1987). Rinnakkais ?menetelmiss? sen sijaan rakenne- taan useampia reittej? yht? aikaa, jolloin asiakkaan lis??miselle on enemm?n vaihtoehtoja (muun muassa Potvin & Rousseau 1993). Savings ?heuristiikka esiteltiin ensimm?isen kerran Clarken ja Wrightin (1964) artikkelissa. Se kuuluu ratkaisua rakentaviin heuristisiin algoritmeihin ja on todenn?k?isesti yksi tunne- tuimmista heuristiikoista. Algoritmi aloittaa ratkaisulla, jossa reittien ja asiakkaiden luku- m??r?t ovat yht? suuria eli jokainen asiakas palvellaan erikseen omalla ajoneuvolla. Kun mitk? tahansa kaksi reitti? yhdistet??n, tarvitaan yksi ajoneuvo v?hemm?n ja yleens? my?s kulut pienenev?t. Savings ?menetelm? hyv?ksyy vain sellaisten reittien yhdist?misen, jois- sa saavutetaan kustannuss??st?j? (savings). Mik?li tavoitteena on ajoneuvojen lukum??r?n minimointi, voidaan negatiivisiakin s??st?j? harkita. 17 Kuva 6. Savings -heuristiikka. Insertion ?heuristiikat kuuluvat my?s ratkaisuja rakentavien heuristiikkojen ryhm??n. Niis- t? tunnetuin on Christofides et al. (1979) kehitt?m? algoritmi. Ratkaisua l?hdet??n luoman lis??m?ll? yksitellen reititt?m?tt?mi? asiakkaita reitteihin, kunnes kaikki asiakkaat ovat jollain reitill?. Insertion ?heuristiikat eroavat toisistaan siin?, kuinka lis?tt?v?t asiakkaat valitaan ja mihin kohtaan asiakkaat lis?t??n reitille. Yksi suosituimmista kehikoista on cheapest insertion. Reittien teko l?htee liikkeelle lis??m?ll? kauimmaisin asiakas reittiin. T?m?n j?lkeen aloitetaan uusien asiakkaiden lis??minen, kunnes ajoneuvon kapasiteetti reitill? on t?ynn? (ja voidaan aloittaa uusi reitti) tai kunnes kaikki asiakkaat on lis?tty reitil- le. Jokaisessa lis?ysvaiheessa etsit??n aika- ja kapasiteettirajoitukset k?ypin? pit?v? asiakas, jonka lis??minen kasvattaa kustannuksia v?hiten. 2.3.2.2 Ratkaisua parantavat menetelm?t Local search ?menetelm?t muodostavat ratkaisua parantavien approksimatiivisten heuris- tiikkojen p??ryhm?n. Ne parantavat askel kerallaan olemassa olevaa ratkaisua etsim?ll? parempaa ratkaisua nykyisen ratkaisun l?heisyydest? k?ytt?m?ll? siirtogeneraatiota. Siin? naapuriratkaisut luodaan muuttamalla annetun ratkaisun yht? ominaisuutta (esimerkiksi kahta asiakasta yhdist?v? kaari) tai useamman ominaisuuden yhdistelm?? (Kyt?joki et al.: 2007:2744). Kun naapuriratkaisu l?ydet??n, sit? verrataan nykyiseen ratkaisuun. Jos se on parempi, se voidaan valita uudeksi ratkaisuksi ja etsint? jatkuu. Jos tulos ei parane, etsint? p??ttyy siihen. Naapuriratkaisujen hyv?ksymiseen uudeksi ratkaisuksi (VRP with Time Windows ?teht?viss?) on k?ytetty yleisesti kahta vaihtoehtoa: first-accept (FA) ja best- accept (BA). 18 2.3.2.3 2-vaihe-algoritmit 2-vaihe-algoritmit muodostavat heuristiikkojen luokan, jossa ongelma on jaettu kahteen tekij??n: klusterointiin ja reittien rakentamiseen. Klusteroinnissa m??ritell??n asiakkaiden jako osajoukkoihin, joista jokainen vastaa reitti?. Reittien rakentamisessa m??ritell??n asi- akkaiden j?rjestys reiteill?. N?iden kahden vaiheen v?lill? on usein my?s jonkinlainen ta- kaisinkytkent?, jonka kautta v?litet??n tietoa. 2-vaihe algoritmit pyrkiv?t parantamaan reit- ti? liitt?m?ll? kaksi kaarta kahteen muuhun kaareen ja toistamalla t?m?n kunnes parannuk- sia ei en?? saavuteta (Kyt?joki et al. 2007). 2-vaihe algoritmit voidaan R?is?sen (2009) mukaan jakaa niin sanottuihin cluster-first, route-second- ja route-first, cluster-second ? menetelmiin. Edelliseen kuuluu useita erilasia menetelmi?. Yksinkertaisimmat niist? kuu- luvat elementary clustering ?ryhm??n, joka suorittaa yhden klusteroinnin asiakassolmujen joukolle ja m??ritt?v?t reitin kullekin klusterille. T?h?n ryhm??n kuuluu muun muassa Gillett ja Millerin (1974) tunnetuksi tekem? Sweep- heuristiikka. Toinen ryhm? on trunca- ted branch-and-bound ?algoritmit. Ne luovat hyv?n reittien joukon approksimoimalla ek- saktia branch-and-bound ?menetelm??. 2.3.3 Metaheuristiset menetelm?t Metaheuristiset menetelm?t ovat sellaisia ratkaisumalleja, jotka hy?dynt?v?t useita erilaisia heuristiikoita parhaimman mahdolliseen tulokseen p??st?kseen. K?ytetyt heuristiikat ovat usein ratkaisua rakentavia tai parantavia. N?iden heuristiikkojen ongelmana on se, ett? l?yt?ess??n paikallisen optimin ne eiv?t p??se sielt? pois. Metaheuristiikat puolestaan oh- jaavat etsint?? laajemmalle ratkaisuavaruuden alueelle muun muassa sallimalla hallitusti ratkaisun huonontamisen ja jopa ei-k?ypien v?litulosten hy?dynt?misen etsint?prosessissa. Metaheuristiikkojen suurimpana ongelmana on, ettei ratkaisujen optimaalisuutta pystyt? varmistamaan (muun muassa Karadimas et al. 2008). Kuitenkin metaheuristiikat ovat osoittautuneet hyvin tehokkaiksi menetelmiksi varsinkin monimutkaisten kombinatoristen ongelmien ratkaisemisessa (Blum & Roli 2003). Metaheuristiikkojen etuna voidaan pit?? sit?, ett? ne eiv?t ole ongelmasidonnaisia, vaan ne soveltuvat hyvinkin erilaisiin ongelmiin. Lis?ksi ne pystyv?t yleens? rajoittamaan ratkaisuavaruudesta etsinn?n niille alueille, joilta l?ytyy hyvi? ratkaisuja, ja j?tt?v?t huonoja ratkaisuja sis?lt?v?t alueet tutkimatta. T?m? antaa paremman mahdollisuuden p??st? mahdollisimman l?helle optimaalista ratkaisua. Simuloitu j??hdytys (simulated annealing, SA) on yksi esimerkki metaheuristisista mene- telmist?. Se on stokastinen relaksaatiotekniikka, joka ohjaa alkuper?ist? local search ? 19 menetelm??. SA:n esitteliv?t Kirkpatric et al. (1983) ja Cerny (1985). Algoritmin toiminta j?ljittelee sulaneen metallin j?hmettymisprosessia. 2.3.3.1 Tabuetsint? Tabuetsint? (tabu search) (Glover 1996) kuuluu my?s local search ?menetelmiin ja sit? on k?ytetty useissa VRP -tutkimuksissa. Ensimm?isi? tabu search algoritmeja lukuun ottamat- ta tabuetsint? on menestynyt hyvin (esimerkiksi paremmin kuin simuloitu j??hdytys). Me- nestyksekk?it? esimerkkej? ovat esitt?neet esimerkiksi Osman (1993), Gendreau et al. (1994) ja Barbarosoglu & Ozgur (1999). Tabuetsin?ss? k?yd??n l?pi per?kk?isi? ratkaisuja samalla tavalla kuin simuloidussa j??hdytyksess?, mutta seuraava siirto tehd??n sen hetki- sen ratkaisun parhaaseen naapuriratkaisuun, vaikka se huonontaisi ratkaisua. Jotta v?ltyt- t?isiin kiert?minen samoissa ratkaisuissa, asetetaan tutkitut ratkaisut kielletyiksi erityiselle tabu-luetteloon jonkin iteraatiom??r?n (toistokerran) ajaksi (De Smith et al. 2009:409). 2.3.3.2 Large Neighborhood Search (LNS) Shaw (1997) esitteli Large neighborhood search (LNS) ?heuristiikan, joka perustuu valittu- jen asiakkaiden poistamiseen ja uudelleenaikataulutukseen k?ytt?en Constraint program- ming (CP) ?tekniikoita. CP on mallikehikko, jonka avulla voidaan esitt?? ja ratkaista laaja joukko kombinatorisia ongelmia. Muuttujien mahdollisten arvojen joukko luodaan k?yt?- m?ll? rajoitteita, kuten ehtoja ja ominaisuuksia, jotka muuttujien on toteutettava ratkaisussa. LNS ?heuristiikka perustuu asiakkaiden valitsemiseen ja poistamiseen aikataulusta ja hei- d?n lis??miseen optimikustannuksella takaisin, mik? m??ritell??n yhdeksi siirroksi. Algo- ritmi tekee samantyyppisi? siirtoja kuin local search, mutta k?ytt?? puurakenteisiin perus- tuvia etsint?menetelmi? yhdess? CP:n kanssa arvioimaan teht?v?n siirron kustannusta ja sopivuutta. Shaw (1997) k?ytt?? reitilt? poistettavien asiakkaiden valinnassa relatedness- mittaa, joka valitsee toisiinsa liittyneit? asiakkaita. T?llaisia ovat asiakkaat, jotka ovat joko maantieteellisesti l?hell? toisiaan tai jotka palvellaan samalla ajoneuvolla, mutta my?s sel- laiset asiakkaat, joiden aikaikkunat ovat samanlaisia tai joille viet?v?t kuormat ovat esi- merkiksi samanpainoisia. Poistetut asiakkaat aikataulutetaan uudelleen k?ytt?en branch- and-boundia yhdess? CP:n kanssa. Suurten laskentavaatimusten vuoksi menetelm? sopii vain ongelmiin, joissa on melko v?h?n asiakkaita per reitti (Br?ysy 2005). 2.3.3.3 Guided Local Search (GLS) Kilby et al. (1998) esittiv?t VRPTW:lle ohjattua (guided) local search (GLS) ?menetelm??. GLS on yleinen metaheuristiikka, joka valvoo local searchia ja sen toimintaa. Mik?li j??- 20 d??n kiinni paikalliseen optimiin, GLS auttaa p??sem??n sielt? pois. GLS:n toiminta perus- tuu muistiin (Voudris & Tsang 1998). Siin? kohdefunktioon lis?t??n sakkotermi sille, kuinka l?hell? etsint? on edellisen kerran kohdattua lokaalia minimi?. Heuristiikka p??see paikallisesta minimist? pois sakottamalla erityisi? ratkaisun ominaisuuksia (yleens? yht? sellaista), jotka eiv?t algoritmin mielest? kuulu l?helle optimia oleviin ratkaisuihin. 2.3.3.4 Variable Neighborhood Search (VNS) Variable Neighborhood Search (VNS) kuuluu local search ?perustaisiin metaheuristiikoi- hin, joissa systemaattisesti vaihdetaan naapuriratkaisujen joukon rakennetta (Hansen & Mladenovic 2001). VNS perustuu siihen, ett? mik?li joudutaan paikalliseen optimiin, vaih- detaan naapuriratkaisujen joukon rakennetta. 2.3.4 Muurahaisyhdyskuntaoptimointi (ACO) Muurahaisyhdyskuntaoptimointi on kehitetty tutkimalla oikeiden muurahaisten k?ytt?yty- mist?. Karadimas et al. mukaan (2008) suurin osa muurahaisten ja niiden ymp?rist?n v?li- sest? vuorovaikutuksesta perustuu muurahaisten tuottamien kemiallisten yhdisteiden hy?- dynt?miseen. Niit? yhdisteit? kutsutaan feromoneiksi. K?velless??n paikasta toiseen muu- rahaiset j?tt?v?t reitilleen feromoni -j?ljen. Muurahaiset valitsevat todenn?k?isimmin reitin, jolla on suurin feromonin m??r?. Aluksi muurahaiset valitsevat sattumanvaraisen reitin, mutta ajan my?t? muurahaiset alkavat k?ytt?m??n samaa reitti?. T?m? johtuu siit?, ett? koska kaikki muurahaiset liikkuvat samalla nopeudella, reitti joka ensimm?isen? saavuttaa pes?n on lyhin. T?m? lyhyempi reitti muodostaa feromoni -j?ljen aiemmin ja kasvattaa reitin mahdollisuuksia tulla valituksi muiden muurahaisten toimesta. T?ten hajuj?lki kas- vaa nopeammin lyhyemm?ll? reitill?, mik? lopulta johtaa siihen, ett? loputkin muurahaiset valitsevat t?m?n reitin (Kuva 7). 21 Kuva 7. Muurahaisyhdyskuntaoptimoinnin reitinvalinta prosessi. 3 Menetelm?t ja aineistot Menetelm?ksi tutkimuksen empiiriseen osuuteen valitsin ArcGIS ?ohjelmiston sis?lt?m?t verkostopohjaiset spatiaaliset analyysity?kalut. ArcGIS on yksi vaihtoehto paikkatietoj?r- jestelm? ?ohjelmistoista, joissa on reitinoptimointiin tarkoitettuja ty?kaluja. Siihen on saa- tavilla parhaiten erilaisia optimointity?kaluja. Viime aikoina my?s vapaasti levitett?v??n Quantum GIS ?pakettiin on tuotu jotain vastaavia toimintoja. Periaatteessa useat ratkai- sualgoritmit olisivat varmasti saatavilla, jos joku kehitt?isi lis?? optimointitoimintoja mui- hin vapaasti levitett?viin GIS- ohjelmistoihin. Uskoisin, ett? optimointity?kalujen kaupal- linen potentiaali on t?ll? hetkell? niin suuri, etteiv?t ne siit? syyst? ole ?freeware? ? ohjelmistoja. ArcGIS on maksullinen ja k?ytt?j?yst?v?llinen sek? lis?ksi se soveltuu hyvin t?m?n tyyppisten vektoriaineistojen analysointiin. Osa tutkimuksen datasta ker?sin GPS ?pisteist?, joita varten j?tteenkuljetusautoissa oli mukana GPS ?loggeri. GPS ?loggerin toimintaperiaate on varsin yksinkertainen: Laite voidaan asettaa tallentamaan pistetieto (koordinaattitieto) tietyll? frekvenssill?. Pisteet tal- lentuvat laitteen sis?iseen muistiin. Koordinaattij?rjestelmist? yleisin on WGS84 - j?rjestelm?. Osa pistetiedoista otettiin suoraan tyhjennyksien valvontaan ja hallinnoimiseen k?ytett?v?st? TCS ?taustaj?rjestelm?st? (Transport Control System) (Kuva 8). Tyhjennys- pisteet ovat paikannettu kuljettajien toimesta ja ne ovat yhten?iskoordinaatistossa (YKJ). Tyhjennyspisteiden ajoj?rjestys otettiin TCS:st? talteen ja sy?tettiin Excel- taulukkoon koordinaattien ja muun tiedon kanssa (Kuva 9). 22 Tyhjennysreittej? valitsin analyysiin mukaan yhteens? viisi (Taulukko 2). Niiden valinnas- sa pyrin siihen, ett? ne olisivat tarpeeksi eheit?, eli niiss? olisi mahdollisimman v?h?n muuta kuin ajoa tyhjennyspisteelt? toiselle. Muutamia reittikandidaatteja sekoittivat suun- nittelemattomat kalustorikot ja vierailut korjaamolle kesken ajoreitin. Taulukko 2. Tyhjennysreittien haivantop?iv?t ja piirien nimet. Reittinumero Nimi Mittausp?iv? 1 Kartonki UA TO 6.10.2011 2 Kartonki UA MA 24.10.2011 3 Kartonki YSH TO 27.10.2011 4 Kartonki YSH TI 11.10.2011 5 Kartonki UA KE 26.10.2011 Kuva 8. Taustaj?rjestelm?st? l?ytyv?t tyhjennyspisteiden koordinaatit. Kuva 9. Ker?yspisteiden tiedot sy?tettiin jokaiselta reitilt? taulukkoon. 23 3.1 Digiroad Digiroadin liikenneverkko koostuu liikenne-elementeist?, jotka ovat yleisen tien, kadun tai muun yhteyden keskilinjageometrian pienin yksikk?. Osa Digiroadin tietolajeista on lii- kenne-elementtien ominaisuustietoja. Liikenne-elementit ovat yleens? liittym?v?lin mittai- sia. Liikenne-elementin geometrian digitointisuunta m??ritt?? suunnan johon liikennevir- ran suuntaa verrataan. Tie- ja katuverkon keskilinja geometria on liikenne-elementtien li- s?ksi my?s lineaariseen referointiin perustuvina refrenssiketjuina. Referenssiketjut mahdol- listavat ominaisuustietojen dynaamisen segmentoinnin ja suurin osa digiroadin tietolajeista on sidottu referenssiketjuille dynaamisesti segmentoimalla. Digiroadin referenssiketjulle sidotusta dynaamisesti segmentoidusta ominaisuustiedosta k?ytet??n nimityst? segmentti (Digiroad 2011). Tieverkon ominaisuus tiedoista tutkimuksen kannalta t?rkeimpi? ovat pituus, nopeusrajoi- tus, nimi sek? osoitetiedot. Aikaa k?ytet??n tutkimuksen impedanssina, eli verkossa kul- kemisen kustannuksena. Muussa tapauksessa reitit kulkisivat liikaa pienempi? teit? pitkin. Pituuden avulla taas m??ritell??n asiakkaiden v?linen et?isyys. K??ntymism??r?ys osoittaa pakolliset, kielletyt tai estetyt k??ntymissuunnat. Se koostuu k??ntymism??r?yksen tyypis- t?, k??ntymism??r?ykseen liittyvist? alku-, v?li- ja loppuelementeist? sek? mahdollisesta vaikutusajasta. K??ntymiskielto on ajoratakohtainen eik? kaistakohtainen. K??ntymism??- r?ys on elementtien v?lill? vain, jos milt??n kaistalta ei saa k??nty? toiselle elementille (Digiroad 2011). T?ss? ty?ss? Digiroad ?aineistosta luotiin verkostoanalyyseja varten sopiva solmu-viiva ? tietokanta. Verkko rakennettiin ArcCatalogin Build Network ?toiminnolla. Verkoston luomisen yhteydess? m??riteltiin s??nn?t verkoston yhdist?vyydelle ja verkostossa kulke- miselle. 3.2 ArcGIS Network Analyst Network Analyst on laajennusosa ArcGIS ohjelmistoon. Se pit?? aktivoida erikseen, jotta se sis?lt?m?t toiminnot saa otettua k?ytt??n. Varsinaisessa verkostoanalyysiss? on viisi vaihetta, jotka k?yd??n l?pi ennen kuin varsinaisia tuloksia saadaan. 1. Tieverkoston lis?ys ArcMap:iin. 24 2. Verkostoanalyysitason luominen. 3. Verkostokohteiden lis??minen. 4. Verkostoanalyysitason asetusten m??ritteleminen. 5. Analyysien suorittaminen ja tulosten esitt?minen. 3.2.1 Vaihe 1: Tieverkoston lis?ys ArcMap:iin Network Dataset on "karttataso", joka mahdollistaa Network Analyt ty?kalujen k?yt?n. Network Dataset luotiin k?yt?ss? olleen digiroad -aineiston pohjalta ArcGIS:n ArcCatalog ?osiossa. 3.2.2 Vaihe 2: Tieverkkoanalyysitason luominen Network Analyst:iin sis?ltyy kuusi erilaista analyysitasoa: Reittitaso (Route analysis layer), L?hin piste- taso (Closest facility analysis layer), saavutettavuusalue- taso (Service area analysis layer), l?ht?- ja saapumispiste kustannusmatriisi- taso (OD cost matrix analysis layer), ajoneuvon reititysongelma- taso (Vehicle routing problem analysis layer) ja lokaa- tio-allokaatio -taso (Location-allocation analysis layer). Ajoneuvon reitiysongelma taso oli l?ht?kohtaisesti sopivin valinta t?m?n luontoiseen ongelmanratkaisuun. Vertailun vuoksi p??tin lis?ksi kokeilla miten route- toiminto soveltuu ja mink?laisia tuloksia se antaa. 3.2.2.1 Vehicle Routing Problem ArcGIS:n VRP ratkaisija toimii siten, ett? ensimm?iseksi se luo l?ht? ja kohde matriisin tilausten ja varikkojen v?lisist? lyhimmist? reiteist?. Lyhimm?n reitin m??rittelyyn k?yte- t??n Dijkstran lyhin reitti- algoritmia. Dijkstran algoritmi on tarkoitettu l?yt?m??n verkos- tossa lyhin reitti yhdest? pisteest? kaikkiin muihin pisteisiin (Dijkstra 1959). Pisteparien v?lisi? et?isyyksi? vertaillaan vuoronper??n toisiinsa. Samaista algoritmia hy?dynt?? my?s ArcGIS:n Route- toiminto. Kustannusmatriisia k?ytet??n ensimm?isen ratkaisun muodos- tamiseen lis??m?ll? tilauksia yksi kerrallaan sopivimmalle reitille. Ratkaisua parannetaan muuttelemalla tilausten j?rjestyst? jokaisella reitill? samoin kuin siirt?m?ll? ja vaihtelemal- la tilauksia reittien v?lill?. T?m? suoritetaan k?ytt?m?ll? tabuetsint? ?metaheuristiikkaa (ESRI 2012a). ArcGIS Network Analystin Vehicle Routing Problem (VRP) -ty?kalun ominaisuuksiin kuuluvat muuan muassa kapasiteetit, tavaran lastaaminen ja purkaminen, kuljettajan tauot, maantieteelliset ty?skentelyalueet ja niin edelleen. Yhteens? erilasia luokkia on 13: Orders, 25 Depots, Routes, Depot Visits, Breaks, Route Zones, Route Seed Points, Route Renewals, Specialties, Order Pairs, Point Barriers, Line Barriers, ja Polygon Barriers. VRP:n luokkien suhteet ovat havainnollistettu alla (Kuva 10). Kuva 10. VRP analyysiluokat Arc GIS:ss? (ESRI 2012b). Jokaiselle reitin tilaus (orders)- luokkaan tuotiin siihen kuuluvat tyhjennyspistetiedot Excel ?taulukosta. Pistetietoja tuodessa sai tilauksille m??ritelty? ominaisuuksia, kuten nimi, haku ja nouto- ja vientim??r?t, aika-ikkunat ja kohteessa kuluva aika. Aikaikkunan m??rit- tely olisi tarpeellista kohteissa, joissa tyhjennykset pit?? suorittaa m??ritellyn ajan puitteis- sa. Jos kohteessa k?yd??n aika-ikkunan ulkopuolella, voi vierailulle asettaa MaxViolation- Time1 ?kohdassa ajan kuinka paljon sen voi ylitt??. T?ss? tutkimuksessa en m??ritellyt kohteessa k?ytett?v?? aikaa laskelmissa, koska oletusarvoisesti jokainen reitti oli suoritettu tietyn ty?ajan puitteissa. My?sk??n tarkkoja aikaikkunoita ei n?ille tyhjennyskohteille ollut. L?ht?kohtaisesti yritykset pyrkiv?t v?ltt?m??n ylit?iden teett?mist?, jos sit? ei voida suo- raan laskuttaa korotettuna my?s asiakkaalta. Nouto- ja vientim??rien k?ytt?minen on my?s mahdollista VRP:ss?. Molemmille voidaan asettaa esimerkiksi sek? paino ett? tilavuus- m??reet. Vaihdossa ajoneuvo voi sek? purkaa ett? lastata tavaraa, jolloin molempiin kent- tiin (DeliveryQuantities ja PickupQuantities) voidaan antaa arvoja. 26 Reitin m??rittelyiss? pystyi asettamaan aloitus- ja lopetuspisteen, aloitusajat, kapasiteetit ja maksimi tilaukset, matkustus-ajat ja ?et?isyydet. Reitti tarkoittaa ArcGIS:ss? samaa kuin ajoneuvo tai kuljettaja. Ajoneuvon kapasiteetiksi reiteille kartonki UA TO ja YSH TI, m??- rittelin 27 paikkaa, joka on hieman v?hemm?n kuin mit? ajoneuvon kapasiteetti oikeasti on. Reitille UA MA, YSH TO ja UA KE kapasiteetit olivat 14, 10 ja 18. Odottamattoman ka- lustorikon takia tyhjennysreitit UA MA, YSH TO ja UA KE jouduttiin suorittamaan kapa- siteetilt??n pienemm?ll? kalustolla kuin mik? oli k?yt?ss? reiteill? UA TO ja YSH TI (huomaa aiemmat p?iv?m??r?t taulukossa 2 sivulla 21). Kapasiteetin vaihtelu johtui siit?, ett? tutkimuksessa pyrittiin mahdollisimman tarkasti saamaan vertailukelpoisia tuloksia empiirisiin tuloksiin. Asetin jokaisen suoritetun tilauksen (orders) v?hent?m??n kapasiteettia yhdell?. Tilaukset olivat t?ss? tapauksessa vierailtavat tyhjennyskohteet. K?yt?nn?ss? autossa on tietty tila- vuuskapasiteetti, mink? verran se voi ottaa tavaraa. Lis?ksi jokainen tyhjennyskohteella voi olla sen kapasiteettiin n?hden yli- tai vajaat?ytt??, joka luonnollisesti vaikuttaa auton ko- konaiskapasiteettiin. Toisin sanoen jos esimerkiksi useat tyhjennett?v?t kohteet ovat vaajaa t?ytettyj?, saadaan autoon mahtumaan useampi kohde kuin alun perin oli suunniteltu. Yli- t?ytt? ?tilanteissa kapasiteetti saattaa my?s loppua suunniteltua aikaisemmin. Siksi asetin kapasiteetin hieman alemmas kuin mit? se todellisuudessa olisi. J?teauton kapasiteettiin vaikuttavat siihen pakattavan j?tteen laatu, kokonaiskantavuus ja akseleille kohdistuvat painot. Lis?ksi pakkaaminen on sit? tehokkaampaa mit? parempi puristuskyky pakkaavalla osalla on ja kuinka monta kertaa pakkausty? toistetaan. Ajoneuvon tyhjent?misen pystyi m??rittelem??n siten, ett? kapasiteetin tultua t?yteen rei- tille m??riteltiin tyhjennys (renewal) ?piste. Kyseisen pisteen sijainti oli jokaisessa reitiss? sama. Tyhjennystapahtuman ajoitusta ei onnistunut m??rittelem??n, vaan ilmeisesti auto k?yd??n tyhjent?m?ss? vasta kun kapasiteetti on t?ysi. Todellisuudessa auto kannattaa k?yd? tyhjent?m?ss? silloin kun paikka osuus sopivasti reitille, vaikka auton kapasiteetti ei olisi viel? ihan t?ynn?. M??ritelmiin olisi hyv? saada sellainen vaihtoehto ett?, jos kapasi- teetti on ylitt?nyt tietyn m??r?n ja renewal ?piste on reitin l?heisyydess?, niin ajoneuvo k?yt?isiin tyhjent?m?ss?. Tilauksille olisi my?s voitu m??ritell? tuotto (revenue), esimer- kiksi tyhjennyksest? asiakkaalta veloitettava maksu. 27 Barriers eli este- kohtaan oli mahdollista lis?t? piste, viiva ja alue- muotoisia kieltoja rei- teille. K?ytin jokaisen reitin analyysissa samojen tiesegmenttien pistemuotoisia k?ytt?kiel- toja. Suurin osa lis??mist?ni esteist? oli matalien siltojen alikulkuja, kuten esimerkiksi Tuusulanv?yl?n siltojen alikulkuja. Muutamat niist? ovat jo surullisen kuuluisia ?rekka- leikkureita? (Kuva 11). Tuloksissa on VRP:st? ratkaisuista kaksi eri versiota (Arc GIS NA VRP v1 ja Arc GIS NA VRP v2), koska huomasin kaksi reitti? analysoituani, ett? It?- Pakilan ja Tuomarinkyl?n alikulun pystyykin ajamaan kyseisell? j?teautolla. Arc GIS NA VRP v1 ?tuloksissa kyseinen tyhjennysreitti on siis suljettu mutta v2:ssa sit? pystyy k?yt- t?m??n. Kyseisen tunnelin korkeus on nelj? metri?, joten kaikki korkeimmat kuorma-autot eiv?t sit? voi k?ytt??. Osaan reittien tuloksista t?ll? seikalla ei ollut vaikutusta, koska ky- seinen alikulku ei ollut niiden j?tteenkuljetusreittien alueella. Kuva 11. Matalat alikulut ovat ongelmallisia korkeille ajoneuvoille (Sepp?nen 2012). Route seed points ?luokka vaikutti mielenkiintoiselta, koska siin? voidaan tavallaan m??ri- tell? mill? alueelta tilaukset herkimmin otetaan tietylle reitille tai ajoneuvolle. Jos reittej? on useampia, lopputuloksena voi olla tiiviimm?t alueet reiteille. Mik? voi olla hyv? jos haluaa pit?? tietyn kuljettajan tietyll? alueella esimerkiksi siksi, ett? h?n tuntee sen alueen 28 paremmin kuin toisen. Toisaalta yritykselle voi olla helpompi hallinta alueita jos niill? on aina tietty kuljettaja tai reitti. Kim et al. (2006) artikkelissa reittien tiiviys ja p??llekk?i- syyksien v?ltt?minen oli yksi optimoinnin l?ht?kohdista. He joutuivat hylk??m??n yhden ratkaisu kandidaatin, koska siin? reitit risteiliv?t p??llekk?in sek? ty?m??r?n jako ei ollut tasapuoleinen. Route seed points ?luokan k?ytt?minen sopii mielest?ni tilanteisiin, joissa k?yt?vi? pisteit? on lukuisia, ja siksi my?s useampia ajoneuvoja tai reittej?. Silloin on var- masti j?rkev?mpi asettaa tietyt alueet tietylle kuljettajalle. Tauot olisi my?s mahdollista m??ritell?, mutta p??tin j?tt?? ne analyysin ulkopuolelle, koska suurin osa kuljettajista valitsee taukopaikan siten, ett? se on k?ytetyn reitin varrella. Eik? esimerkiksi siten, ett? tauko vietett?isiin aina tietyss? paikassa, kuten esimerkiksi va- rikolla. 3.2.2.2 Route Vertailun vuoksi p??tin kokeilla l?hesty? ongelmaa my?s ArcGIS ?ohjelmiston Network Analyst ?ty?kalun Route ?toiminnolla. Siin? voidaan m??ritt?? halutut sijainnit, mink? kautta tyhjennysreitti kulkee. Toin pys?hdyspaikat jokaiselle reitille samoista excel - taulukoista kuin VRP:ss? k?ytettiin. Olin alun perin sy?tt?nyt tyhjennyspaikat samaan tyh- jennysj?rjestykseen. Taulukossa jokaiselle pisteelle oli m??ritelty koordinaatit YKJ - koordinaatistolla. ArcMap osaa automaattisesti tehd? koordinaattimuunnokset, jos eri ai- neistojen koordinaattij?rjestelm?t eroavat toisistaan. Ensiksi tuodun aineiston koordinaatti- j?rjestelm? m??r?? my?hemmin samaan ty?tilaan tuotujen aineistojen j?rjestelm?n. Route ?toiminto ei osaa ottaa huomioon kapasiteettien ylityst?, mutta optimaalisen reitin vertai- lun kannalta se on siit? huolimatta mielenkiintoinen. Purkupaikan pystyy siin?kin m??ritte- lem??n laittamalla sen samaan v?liin, joissa purku oikeasti suoritettiin, jos ei anna toimin- non itse m??ritell? j?rjestyst? uudelleen. Jos reitti optimoidaan aivan t?ysin, eli antaa oh- jelman siirrell? pys?htymispaikkojen j?rjestyksi?, voi siit? huolimatta ensimm?isen ja vii- meisen paikan s?ilytt??. Ajoneuvon reititysongelmassa ne ovat usein m??riteltyj?, esimer- kiksi reitti alkaa ja loppuu aina ty?paikalle (varikko tai muu vastaava). Reitiss? 1 ja 2 aloi- tus paikka oli m??ritelty varikoksi, mutta lopetuspaikaksi ty?ntekij?n kodin l?heinen park- kialue. Lopuissa reiteiss? l?ht? ja paluu oli m??ritelty varikolle. 29 3.2.3 Vaihe 3: Verkostokohteiden lis??minen Jokaiselta viidelt? tyhjennysreitilt? ker?ttiin dataa siit? miten tyhjennysreitti suoritettiin k?yt?nn?ss?. Autojen mukana oli GPS ?loggeri (Ventus G.730) (Kuva 12), joka s??dettiin automaattisesti tallentamaan havaintopisteen viiden sekunnin v?lein. Tutkimuksessa todet- tiin ett? GPS:n signaalih?iri?t? oli havaittavissa joillakin alueilla (Kuva 13). Kuva 12. XY- pistedatan ker??miseen k?ytetty GPS-loggeri (Ventus G.730). Muutin Ventus G.730 ?laitteen mukana tulleella ohjelmistolla GPS -datan Excelin hyv?k- sym??n CSV ? tiedostomuotoon. Exceliss? jouduin muutamaan koordinaattien esitysfor- maatin pisteen pilkuksi, jotta ArcMap suostui tuomaan tiedoston oikein ty?tilaan. Lis?ksi tuodessa piti muistaa vaihtaa pistepilven koordinaattij?rjestelm? loggerin k?ytt?m?st? WGS84-pohjaisesta muun aineiston muotoon (KKJ3-kaista = Finland Zone 3). Pisteiden sijainti heitti silti noin 150-160 metri? (Kuva 14). Asia selvisi asettamalla, n?kym?kehyk- sen ominaisuusikkunasta (Data Frame Properties) transformaatio, jonka mukaan aineistoja siirret??n koordinaattij?rjestelm?st? toiseen. "Using" -kent?ss? m??ritettiin muunnospara- metriksi JHS154-suosituksen mukaiseksi. 30 Kuva 13. Pisteaineistossa oli my?s GPS -signaalih?iri?ist? johtuvia heittoja. Kuva 14. ArcMap:iin tuodut GPS-pisteiden siirtym? oli noin 150 metri? ennen oikeita muunnospara- metrej?. 31 3.2.4 Vaihe 4: Verkostoanalyysitason asetusten m??ritteleminen Analyysitason asetusten m??ritteleminen on paljon suoraviivaisempi ja yksinkertaisempi kuin verkostokohdeobjektien asetusten m??ritteleminen. Asetuksista valitaan mit? impe- dansseja k?ytet??n ja mit? rajoituksia noudatetaan. Rajoituksista mukana t?ss? analyysiss? olivat yksisuuntaiset kadut ja kevyenliikenteen v?yl?t. Kevyenliikenteen v?yli? joudutaan jossain tapauksissa oikeasti k?ytt?m??n, mutta VRP analyysiss? ne piti sulkea kokonaan pois k?yt?st?. Aika ja matka attribuutteina olivat minuutit ja metrit 3.2.5 Vaihe 5: Analyysien suorittaminen ja tulosten esitt?minen Viimeisess? vaiheessa ei ollut muuta teht?v?? kuin selvitt?? reitti annetuilla objekteilla ja asetuksilla. Jokaisen reitin ominaisuuksiin tuli kokonaisaika ja matka, sek? tyhjennysten lukum??r? (renewalCount). Tilaukset ja varikkopys?hdykset havainnollistettiin numeroitu- na ja j?rjestyksess? Network Analyst:n ikkunaan (Kuva 15). Lis?ksi k?ytetty reitti ja tila- ukset n?kyiv?t reittein? kartalla. Ne ovat esitetty seuraavassa kappaleessa tulos ? taulukoiden kanssa. 32 Kuva 15. Reitin ominaisuudet Total distance ?kohta kertoo reitin pituuden. 33 4 Tulokset T?ss? osiossa k?yd??n l?pi tutkimuksen empiirisen osan tulokset eri j?tteentyhjennys reitti- en osalta. Valitut reitit edustavat yrityksen tyypillisi? j?tteentyhjennys reittej?, jotka suori- tetaan niin sanotuilla nostoautoilla (Kuorma-auto, jossa on lava ja kappaletavaranosturi). J?tteentyhjennys reitti nimelt? kartonki UA (urakka-alue) TO, joka oli suoritettu 6.10 2011, saatiin GPS -mittauksella reitin pituudeksi 171 km (Kuva 16;Taulukko 3). Reitti alkoi va- rikolta (objekti 1), mutta p??ttyi kuljettajan kodin l?heisyyteen (objekti 33). VRP v1- optimoinnin j?lkeen pituus lyheni noin 16 kilometri?. Erityisesti t?ll? reitill? Torpparinm?- entien alikulun sulkemisesta oli vaikutusta optimointitulokseen, koska VRP v2 ? analyysiss?, jossa siis este oli poistettu, reitin pituus v?heni alkuper?isest? 22 kilometri?. Route- optimoinnin j?lkeen, jossa siis k?ynti j?rjestys oli sama kuin varsinaisessa empiiri- sess? mittauksessa, reitin pituus v?heni vajaat 10 kilometri?. Parhaimman tuloksen antoi siis VRP v2 ?analyysi yli 12 prosentin parannuksella GPS- mittaukseen verrattuna. Kus- tannukset ovat laskettu kertomalla kilometrim??r?t 2,195 eurolla, joka tulee kustannuslas- kenta -taulukosta (Taulukko 1). Taulukko 3. Tyhjennysreitin UA TO tulokset. Kartonki UA TO Pituus Km Erotus Km Parannus- % Kustannus ? Kustannus-ero ? GPS -mittaus 171 - - 375 0 ArcGIS NA VRP v1 155 -16 9,4 % 340 -35 ArcGIS NA VRP v2 149 -22 12,9 % 327 -48 ArcGIS NA R sama j?rjestys 161,5 -9,5 5,6 % 354 -21 34 Kuva 16. Ensimm?isen reitin (kartonki UA TO) alkuper?inen reittivalinta ja optimoitu. 35 Toinen j?tteenker?ysreitti oli kartonki UA MA, jonka empiirinen GPS- mittaus oli otettu 24. lokakuuta 2011, antoi reitin pituudeksi reilut 160 kilometri? (Kuva 17;Taulukko 4). T?m? alkoi normaalilta varikolta ja p??ttyi kuljettajan kodin l?heisyyteen (objektit 1 ja 37). T?ll? reitill? VRP v1 -optimointi antoi lis?? pituutta 2,8 kilometri?. VRP v2 ?optimointi paransi puolestaan v?hent?en alkuper?isest? mittauksesta vajaat nelj? kilometri?. Parannus j?i siis vain reiluun kahteen prosenttiin. Route- optimointi heikensi tulosta alkuper?iseen mittaukseen, lis?ten reitin pituutta melkein 18 kilometri?. T?lle keruureitille ei siis opti- moinnilla l?ydetty kovinkaan merkitt?v?? parannusta alkuper?iseen reittiin verrattuna. Eu- rom??r?iset kustannukset ovat laskettu kertomalla kilometrim??r?t 2,195 eurolla, joka tulee kustannuslaskenta -taulukosta (Taulukko 1). Taulukko 4. Tyhjennysreitin UA MA tulokset. Kartonki UA MA Pituus Km Erotus Km Parannus- % Kustannus ? Kustannus-ero ? GPS -mittaus 160,2 - - 352 0 ArcGIS NA VRP v1 163 2,8 -1,7 % 358 6 ArcGIS NA VRP v2 156,5 -3,7 2,3 % 344 -8 ArcGIS NA R sama j?rjestys 178,1 17,9 -11,2 % 391 39 36 Kuva 17. Kartonki UA MA tyhjennysreitin alkuper?inen reittivalinta ja optimoitu. 37 Pisin empiirinen mittaus oli 27 lokakuuta suoritetulla reitill? 3 (kartonki YSH TO), jonka pituudeksi tuli 190,5 kilometri? (Kuva 18; Taulukko 5). My?s t?m? reitin alku ja loppupis- te olivat samat (varikko). VRP v1 ?optimointi pidensi reitti? per?ti 5,2 kilometrill?, jolloin reitin kokonaispituudeksi muodostui reilut 195 kilometri?. VRP v2 ?optimointi onnistui kuitenkin lyhent?m??n reitti? 171,8 kilometriin, eli parannusta tuli 18,7 kilometri?. Route ? optimointi v?hensi tulosta viel? hieman VRP v2:sta enemm?n, noin 20 kilometri? eli reilut 10 prosenttia. Eurom??r?iset kustannukset ovat laskettu kertomalla kilometrim??r?t 2,195 eurolla, joka tulee kustannuslaskenta -taulukosta (Taulukko 1). Taulukko 5. Tyhjennysreitin YSH TO tulokset. Kartonki YSH TO Pituus Km Erotus Km Parannus- % Kustannus ? Kustannus-ero ? GPS -mittaus 190,5 - - 418 0 ArcGIS NA VRP v1 195,7 5,2 -2,7 % 430 -11 ArcGIS NA VRP v2 171,8 -18,7 9,8 % 377 -41 ArcGIS NA R sama j?rjestys 170,4 -20,1 10,6 % 374 -44 38 Kuva 18. Tyhjennysreitti kartonki YSH TO alkuper?inen reittivalinta ja optimoitu. 39 Tyhjennysreitit kartonki YSH TI ja kartonki UA KE sijoittautuivat maantieteellisesti laa- jimmalle alueelle. YSH TI:n empiirinen mittaustulos oli 156,8 kilometri? (Kuva 19;Taulukko 6). Optimoinnin j?lkeen molemmat VRP v1 ja VRP v2 antoivat samat tulok- set, siit? syyst?, ett? reitti suuntautunut poistetun alikulun alueelle, vaan kiersi sen kauem- paa etel?st? ja pohjoisesta. Molemmat pidensiv?t alkuper?ist? tyhjennysreitti? 7,5 kilomet- rill?. Kummankin tulokset reitit olivat identtisi?. Kunnon tuloksen reitille nelj? antoi Rou- te- optimointi, joka lyhensi reitti? melkein yhdeks?ll? kilometrill?. Eurom??r?iset kustan- nukset ovat laskettu kertomalla kilometrim??r?t 2,195 eurolla, joka tulee kustannuslaskenta -taulukosta (Taulukko 1). Taulukko 6. Tyhjennysreitti YSH TI. Kartonki YSH TI Pituus Km Erotus Km Parannus- % Kustannus ? Kustannus-ero ? GPS -mittaus 156,8 - - 344 0 ArcGIS NA VRP v1 164,3 7,5 -4,8 % 361 16 ArcGIS NA VRP v2 164,3 7,5 -4,8 % 361 16 ArcGIS NA R sama j?rjestys 148 -8,8 5,6 % 325 -19 40 Kuva 19. Kartonki YSH TI, alkuper?inen ja optimoitu p??llek?in. 41 Viimeinen optimoitu reitti (kartonki UA KE), sijoittui pitk?lti samoille sijainnille kuin edellinen tyhjennysalue, ollen kuitenkin hieman pidempi, yhteens? 175,5 kilometri? (Kuva 20;Taulukko 7). Samoin kuin nelj?nnen reitin tilanteessa, antoivat molemmat VRP ? analyysit samat pituudet reiteille, eli olivat identtiset. Kumpikin lyhensi reitti? yli 16 kilo- metri?. Siis parannusta tuli melkein 10 prosenttia. Route -optimointi paransi tulosta l?hes yht? paljon. Sill? tyhjennysreitin pituudeksi tuli 160,1 kilometri?. Parannusta muodostui siis 15,4 kilometri? GPS- mittaukseen verrattuna ja prosenteissa parannusta tuli yli 8. Eu- rom??r?iset kustannukset ovat laskettu kertomalla kilometrim??r?t 2,195 eurolla, joka tulee kustannuslaskenta -taulukosta (Taulukko 1). Taulukko 7. Tyhjennysreitti UA KE. Kartonki UA KE Pituus Km Erotus Km Parannus- % Kustannus ? Kustannus-ero ? GPS -mittaus 175,5 - - 385 0 ArcGIS NA VRP v1 158,7 -16,8 9,6 % 348 -37 ArcGIS NA VRP v2 158,7 -16,8 9,6 % 348 -37 ArcGIS NA R sama j?rjestys 160,1 -15,4 8,8 % 351 -34 42 Kuva 20. Kartonki UA KE, ajettu reitti ja optimoitu. 43 5 Keskustelu Tutkimustulokset osoittavat kuinka paljon kuljetustaloudellisia s??st?j? on tyhjennysreitti- en optimoinnilla saavutettavissa. Tutkimuksen mukaan viiden reitin optimoinnilla pituus v?heni keskim??rin noin kahdeksan prosenttia. Karadimas et al. (2008) tutkimuksessa he saavuttivat yhdell? reitill? noin 25 prosentin parannuksen samalla ArcGIS:n Network Ana- lyst- ty?kalulla. Nuortio et al. (2006) olivat omassa tutkimuksessa saaneet yksitt?isten reit- tien pituudesta v?henem??n keskim??rin 16 kilometri?. T?m? oli noin 12 prosenttia paran- nusta reittien pituudessa. Nuortio et al. (2006) totesivat tutkimuksessaan, vaihteluv?lin tyhjennysreittien kesken olevan muutamasta kilometrist? jopa aina 70 kilometriin. My?s Benjamin ja Beasley saavuttivat tabu etsint? ?metaheuristiikkaa hy?dynt?m?ll? keskim??- rin 5,6 prosentin parannuksen (2010). Osa optimointia k?sittelevist? tieteellisist? artikkeleista keskittyi enimm?kseen optimoin- tialgoritmien tekniseen kehitt?miseen. Katso esimerkiksi Kim et al. 2006 ja Lau et al. 2003. T?rkeimp?n? tuloksena n?iss? tutkimuksissa pidettiin saavutettuja alhaisia aikoja optimoin- tien laskenta-ajoissa. Angelli ja Speranza taas esitt?v?t omassa tutkimuksessaan mallin j?tteenkuljetusten operointikustannuksien arvioimiseen (2002). Mallin kehitt?minen tapah- tui vertailemalla kahta erilaista tyhjennys tekniikkaan toisiinsa. Vanhaa tapaa, jota k?ytet- tiin molemmilla esimerkkin? olevilla tutkimusalueilla (Val Tropia ja Antwerpen) ja uutta tekniikkaa. Tutkimuksessa esitellyn mallin mukaan kustannuksiin heijastuvat voimakkaasti j?tteentyhjennyksess? kuljettu matka ja toisaalta j?tteenkeruuauton itsens? tyhjent?miseen kuljettu matka (Angelli & Speranza 2003). Mielest?ni t?ss? tutkimuksessa saavutettua tulosta voi pit?? melko hyv?n?, ottaen huomi- oon, ett? tyhjennyspisteit? reiteill? oli lukum??r?lt??n v?h?n. Jos kustannuss??st?potentiaa- lia tarkastellaan kertaluonteisena suoritteena, on tuloksen merkitt?vyys suhteellisen v?h?i- nen. Yksitt?isen reitin, kuljettajan tai auton tilanteessa ei siis v?ltt?m?tt? saavuteta hyvin merkitt?vi? s??st?j?. Useamman auton ja kuukauden tai vuoden tilannetta tarkasteltaessa s??st?jen m??r? alkaa kertautua, jolloin merkitt?vyys kasvaa. T?m? kasvattaa kuljetusten suunnittelun painoarvoa yrityksiss?, jotka kuljettavat isolla volyymilla ja s??nn?llisesti. J?tehuolto logistiikan alana soveltuu erinomaisesti optimointiin, koska asiakaspisteit? ja toistoja on paljon. Jo kustannuss??st?t pelk?st??n v?hentyneen? polttoaineiden kulutuksena voivat olla huomattavia. Polttoaineiden hinnat yleens?, mutta erityisesti dieselin hinta on 44 viime vuosina noussut dramaattisesti (Tilastokeskus 2013; Taulukko 8). Hintaa on nostanut maailman markkinahintojen nousu ja Suomen valtion polttoaineisiin kohdistuneet veronko- rotukset. Diesel?ljyn vero on ?ljyalan keskusliiton mukaan l?hes 47 prosenttia (2013). Keskim??r?isesti j?tteenkuljetuksessa k?ytett?v?t kuorma-autot kuluttavat 40?50 litraa diesel- polttoainetta sadalla kilometrill?. Kun sek? polttoaineen kulutus ett? hinnat ovat korkeita, on pienikin systemaattinen s??st? kulutuksessa eritt?in merkitt?v?. Ja nimen- omaan n?ihin s??st?ihin reittioptimoinnilla pyrit??n. Taulukko 8. Dieselin hintakehitys 2005-2013 (Tilastokeskus 2013). Tyhjennysreittien eurom??r?iset kustannukset ovat laskettu k?ytetyn kustannustaulukon (Taulukko 1) perusteella. Ne eiv?t todellisuudessa aivan t?ysin vastaa t?ss? tutkimuksessa k?ytettyjen kuorma-autojen todellisia kustannuksia. Tietyt taulukkoon sy?tett?vist? tiedois- ta voidaan katsoa olevan yrityksen niin sanottua ei-julkista tietoa, kuten esimerkiksi yritt?- j?riski (voittotavoite kulujen j?lkeen). Siit? huolimatta ne antavat eritt?in realistisen ja ver- tailukelpoisen kuvan raskaankaluston todellisista kustannuksista. Tekem?ll? tapauskohtai- sia muutoksia laskentataulukon arvoihin saadaan kussakin ongelmassa k?ytetyn jokaisen ajoneuvon kustannukset. Taulukossa on otettu huomioon laajasti monia kustannustekij?it?. N?ist? mainittakoon esimerkkein? muun muassa hallinnointikustannukset ja rengaskustan- nukset. Useat kuljetusyritt?j?t eiv?t osaa ottaa huomioon laskelmissaan todellisia kustan- 0 20 40 60 80 100 120 140 160 180 20 05 /1 V IX 20 06 /I V IX 20 07 /I V IX 20 08 /I V IX 20 09 /I V IX 20 10 /I V IX 20 11 /I V IX 20 12 /I V IX 20 13 /I Diesel?ljyn hintakehitys 2005-2013 Diesel 45 nuksia ja n?in aliarvioivat kuljetustarjouksissa pyydettyjen t?iden hinnat. Pahimmassa ta- pauksessa v??rin lasketut hinnat johtavat sopimusten purkautumiseen laiminly?ntien takia ja konkurssiin. Muissa reittioptimointiin liittyviss? tutkimuksissa ei ole huomiota kiinnitet- ty kustannuksiin. Optimoinnintuloksia tarkastellessa huomio kiinnittyy siihen, kuinka paljon kuorma-auton kapasiteetti vaikuttaa tulosten parantumiseen. T?ss? tutkimuksessa optimoitujen yksitt?is- ten reittien kuljetun matkan lyheneminen vaikuttaa melko uskottavalta. Kapasiteetin vaiku- tus tuli ilmi tyhjennysreitilt? kartonki YSH TO, mink? kokonaispituus v?hentyisi l?hes 76 kilometri?, jos k?yt?ss? oleva kapasiteetti olisi ollut sama kuin UA TO reitill? ja YSH TI reitill?. Asia tuli ilmi kun ajoin optimoinnin aluksi v??rill? kapasiteettitiedoilla. Reitin ly- hentyminen johtuu siis osittain siit?, ett? v?lityhjennys- ajoa ei tule niin paljon. Autojen kapasiteettia lis?tt?ess? vastaan tulevat nopeasti ajoneuvon akseleiden kantavuusrajoitukset sek? ajettavuuteen liittyv?t vaikeudet kaupunkien kapeilla kaduilla. Tekniset ratkaisut li- s??v?t my?s kaluston rikkoutumisalttiutta. Usein t?ytyy puntaroida, kumpi on t?rke?mpi tekij?: kaluston toimintavarmuus vai optimaalisuus. Joskus optimaaliset ratkaisut saattavat osoittautua virheiksi, jos kalliit laitteet seisovat liian usein k?ytt?m?tt?min? niiden toimi- mattomuuden takia. Kuorma-autolla ajattavaksi tarkoitettavia reittej? optimoidessa t?ytyy huomioida sellaisia seikkoja mit? ei v?ltt?m?tt? tulisi heti ajatelleeksi. Er?s n?ist? tapauksista on siltojen ali- kulkujen korkeusrajoitukset (Kuva 21). Ne eiv?t vaikuta henkil?autoilla suoritettavien reit- tien optimointiin (esimerkiksi pakettiautolla suoritettava jakeluliikenne). Kuorma- autoissakin voi olla eroja. Raskaan kaluston p??llirakenteet vaikuttavat niiden maksimi korkeuteen ja leveyteen. ArcGIS:n VRP ?toiminnosta en l?yt?nyt sellaista ominaisuutta ett? esimerkiksi auton korkeus tai painorajoituksen olisi voinut asettaa. Toisaalta my?sk??n Digiroad -aineistossa ei ole otettu huomioon n?it? seikkoja. Onneksi p??kaupunkiseudulla- kaan ei ole kovinkaan montaa sellaista alikulkua, joiden k?ytt?mist? tieliikennelain ajo- neuvojen maksimi korkeus ?s??d?kset rajoittaisivat. Eriasia on ylileve?t kuljetukset, jotka tosin ovatkin harvinaisia yksitt?istapauksia ilman jatkuvaa toistoa. 46 Kuva 21. Osa Tuusulanv?yl?n alikuluista piti sulkea liian matalina pois k?ytett?vist? v?ylist?. Tutkimuksessa mahdollisia virhel?hteit? ovat kapasiteettiin liittyv?t seikat. Optimointity?- kaluihin sy?tetyt tiedot ovat parhaimmillaankin vain valistuneita arvauksia. Jos todelliset m??r?t heittelev?t siit? mit? on ajateltu, voi sill? olla huomattava vaikutus lopputulokseen. GPS- mittauksissa on my?s virhel?hteen mahdollisuus. Kaikki GPS ?mittaukset olivat hieman pidempi? kuin mit? ajettu tyhjennysreitti piirturin kiekon mukaan oli. Toisaalta johonkin lukemaan vertailu pit?? suorittaa. Piirturinkin lukema voi heitt?? ja kuljettaja voi olla merkinnyt lukemat v??rin. Virheit? on saattanut aiheuttaa my?s kuljettajan suorittamat poikkeamat ajon aikana varsi- naiselta suunnitellulta reitilt?. N?it? ovat esimerkiksi tauot tai kohteet jotka ovat tyhjennet- ty ilman ett? niit? on kuitattu ajoseurantaj?rjestelm??n (Kuva 22). Suunnittelemattomia tyhjennyksi? voivat olla esimerkiksi puhelimella ilmoitetut nopeasti suoritettavaksi tarkoi- tetut ?h?lytysteht?v?t?. Optimoiduissa reiteiss? oli toisaalta havaittavissa jonkin ver- ran ?harhailua? tyhjennyspisteiden l?heisyydess? (Kuva 23), mik? osaltaan lis?? optimoitu- jen reittien kokonaispituuksia. 47 Kuva 22. Varsinaisilla ajoreiteill? oli poikkeamia suunnitellulta reitilt?. Huomion arvoista ja mielenkiintoista tuloksissa oli my?s se, ett? YSH Ti ?tyhjennysreitill? VRP optimoinnit antoivat tuloksena pidemm?n matkan, kuin mit? alkuper?inen tyhjennys- reitti oli. Ero oli 7,5 kilometri?, joten se ei ole kovin suuri. Syy saattaa olla siin?, ett? opti- moinnissa k?ytett?v? tieverkostotaso k?ytt?? tie -hierarkian suurimpia v?yli?, jotka siis voivat olla ajallisesti nopeampia. Toisaalta taas kuljettaja on k?ytt?nyt t?ll? kertaa normaa- lia pienempi? v?yli?. 48 Kuva 23. Reittivalinta optimoinneissa ei v?ltt?m?tt? ole aina paras mahdollinen. Tyhjennysreittien optimaalisuuden kannalta yhdeksi t?rke?ksi seikaksi, kapasiteetin ohella, nousee niiden tiiviys (Kuva 24). Ajoreitin valinta ei silloin korostu niin merkitt?v?ksi teki- j?ksi. Pisteiden sijaitessa l?hekk?in toisiaan, ei niiden v?lisi? ajoreitti- vaihtoehtoja yleens? ole kovinkaan monta erilaista. Pisteiden esitt?minen kartalla GIS:n ty?v?lineill? auttaa konkreettisesti huomaamaan ep?tiiviit alueet toisin kuin pelkk?? osoitelistaa tarkastelemal- la. Optimointiohjelmien toivoisi tuovan esille t?m?n tyyppisi? kohteita, jotta niihin voisi etsi? ratkaisua muilla keinoilla. Kim et al. viittaa omassa tutkimuksessaan samaan ongel- maan (2006:3634). Heid?n k?ytt?m?ns? algoritmit antoivat hyvi? tuloksia mutta reitit eiv?t olleet tarpeeksi tiiviit?. T?m? hankaloittaisi tyhjennysten k?yt?nn?n hallinnointia. Kaikissa tilanteissa p?ivitt?isest? reitist? ei yrityksist? huolimatta saada kovinkaan tiivist? pakettia. Silloinkin ongelman havaitseminen auttaa havainnollistamaan kuinka suureksi t?llai- sen ?ongelmatapauksen? tyhjent?minen muodostuu. Mik? taas saattaa johtaa toisenlaisiin ratkaisumalleihin, kuten ker?yspisteen kapasiteetin kasvattamiseen, ja n?in harvempiin ajokertoihin. Joissain paikoissa nostos?ili?t onkin korvattu pakkaavilla konteilla, joiden kapasiteetti on huomattava s?ili?ihin verrattuna. Parhaimmillaan viisi ? kuusi kertaa vii- kossa tyhjennetyt s?ili?t on voitu korvata n?in ja uuden pakkaavan kontin tyhjennys on 49 voitu v?hent?? kerran kuukauteen. Ratkaisu on tosin kallis ja soveltuu vain tiettyihin koh- teisiin. Pakkaavan kontin (pr?ssi) tyhjent?minen tapahtuu erilaisella kalustolla kuin mist? t?ss? tutkimuksessa on kysymyksess?. Konttien kuljettaminen on Benjamin ja Beasleyn (2010:2271) mukaan ?Roll-on ? Roll-off? ?ongelma. Muutaman tieteelliset artikkelit k?sit- telev?t yksitt?isten konttien, lavojen tai hydraulisten puristimien ker?yst? (esimerkiksi De Meulemeester et al. 1997). T?ss? ongelmassa t?yden lavat kuljetetaan asiakkaalta pois tai asiakkaalle vied??n esimerkiksi tyhj? kontti. Tyypillist? t?llaiselle ongelmalle on se, ett? ajoneuvo voi kerrallaan kuljettaa vain yht? kuljetusv?linett? kerrallaan Kuva 24. Reitin tiiviyden kannalta haasteelliset alueet. 50 Tyhjennysreitit eiv?t suinkaan ole stabiileja, vaan niille tulee jatkuvasti muutoksia. Uusia kohteita tulee viikoittain. Se sotkee yhdess? kalustorikkojen kanssa reittien suunnittelua ja varsinaista toteutusta. Muutaman paikan lis?ys saattaa tehd? tyhjennyspisteilt??n harvasta ja ?kannattamattomasta? alueesta tarpeeksi tiiviin ja kannattavan. Sen lis?ksi ett? uusia tyhjennett?vi? kohteita tulee, saattaa vanhoja poistua ja olemassa olevien kohteiden tyh- jennysrytmi muuttua. Ylim??r?iset tyhjennyspyynn?t hankaloittavat my?s optimaalista reitityst?. Kohteen tyhjennyst? saatetaan harventaa tai tihent?? riippuen siit? kuinka paljon kierr?tett?v?? materiaalia syntyy. Materiaalin m??r?n kertymisess? on havaittavissa my?s kausittaista vaihtelua: Esimerkiksi joulun aikaan tai koulujen alkamisen tienoilla tavaraa tulee huomattavasti enemm?n kuin esimerkiksi alkukev??st? tai kes?lomien aikaan. T?m?n tyyppisell? kausivaihtelulla voi olla eritt?inkin huomattava vaikutus tyhjennystiheyteen (tai vuorostaan ylit?ytt??n ja kapasiteetin ennenaikaiseen t?yttymiseen). Periaatteessa opti- mointity?kalujen pit?isikin pysty? huomioimaan n?it? muutoksia jatkuvasti ja optimoi- maan reititykset uudestaan niiden mukaan. Ohjelmallisen reittioptimoinnin parhaita puolia ovat sen kyky tehd? reitityksi? suurillekin m??rille reittipisteit? niill? parametreilla ja tiedoilla joita halutaan hy?dynnett?v?n. Koke- musper?inen reititt?minen hy?tyy pitk?st? k?yt?nn?n tietotaidosta, joita siin? voidaan hy?- dynt?? tehokkaasti. Nopeasti muuttuvissa tilanteissa ihmisen ongelmanratkaisukyky on my?s parhaimmillaan verrattuna tietokoneisiin. Toisaalta ihminen on usein tapojensa orja ja ajautuu helposti tutuille ?raiteille? tehdess??n samoja toistuvia asioita. T?ss?kin mieless? tuttu lyhyeksi mielletty reitti saattaa olla todellisuudella pidempi kuin esimerkiksi navi- gaattorin ehdottama oikeasti nopeampi ja lyhyempi reitti. Toisaalta ihminen voi kokemuk- sesta tiet??, ett? jotain reitti? voi hy?dynt?? ?oikotien?? vaikka se ei virallinen tieosuus olisikaan (huoltoajolle sallitut reitit). Muuttuvia tekij?it? voivat olla esimerkiksi: tiety?t, ruuhkat, kalustorikot, keskeytykset ja muut poikkeavat tyhjennysrytmit. Toisaalta kaksi reitti? pisteelt? toiselle saattavat optimointij?rjestelm?lle n?ytt?yty? samanlaisina (Kuva 25). Niiss? on suurin piirtein sama matka, samat nopeusrajoitukset ja sama m??r? k??nn?k- si?. Todellisuudessa kuljettaja ei miss??n nimess? k?ytt?isi toista niist? reiteist? esimerkik- si tiell? olevien hidasteiden takia. 51 Kuva 25. Kumpi reiteist? (sininen vai keltaiset pisteet) 2 pisteelt? 3 pisteelle on oikeasti parempi? Ruuhkaisuus ja ep?edullisten ajoreittien tuntemus on er?s esimerkki, josta kokemusper?i- sess? reititt?misess? on suurta hy?ty?. Ihminen tiet?? mihin aikaan, miss? ja mihin suun- taan ruuhkat ovat pahimmillaan ja voi halutessaan muuntaa tekemist??n sen mukaan. Toi- saalta reittioptimointiohjelmiin varmasti saisi jotenkin m??ritelty? jonkinlaisen yleisp?te- v?n ruuhkaisuushidastus ?elementin. Esimerkiksi vaikka siten, ett? kaikkien v?ylien mak- siminopeus laskisi tietyll? aikav?lill? normaalista nopeudesta. Toinen vaihtoehto voisi ol- la ?sakottaa? suurempien v?ylien nopeuksia enemm?n ja pienempien katujen nopeudet s?ilytt?? ennallaan, tai pienent?? niit? v?hemm?n kuin suurien. Usein kuljettajat pyrkiv?t aloittamaan p?iv?n sellaisesta suunnasta jonne ruuhkaa ei ole. Ruuhkaisuus on esimerkki 52 sellaisista ajallisista tekij?ist?, jotka hankaloittavat kilometrim??riin perustuvaa vertailua. Ruuhkaan juuttuessaan kilometrej? ei tule enemp??, mutta aikaa sen sijaan kuluu huomat- tavasti enemm?n. Reittien suunnittelussa tulee ottaa huomioon my?s asiakaspalvelu ?n?k?kulman. Mit? laa- jemmin useammat alueet katetaan, sit? todenn?k?isemmin ja nopeammin asiakas saa poik- keustilanteissa palvelua. Uusien asiakkaiden lis??minen reiteille my?s helpottuu, jos reitte- j? ei ole suunniteltu niin tiukoiksi, ett? uusien asiakkaiden lis??minen hankaloituu. Kaiken kaikkiaan noin 10 prosentin s??st? kustannuksissa on vuositasolla eritt?in merkit- t?v?. Viel? jos sen yhdist?? esimerkiksi yleisesti taloudelliseen ajotyyliin, voivat s??st?t kasvaa vuositasolla kymmeniin tuhansiin euroihin yrityksen koosta, kaluston lukum??r?st? ja tyypist? riippuen. Kustannuss??st?jen lis?ksi v?hentynyt ajaminen vaikuttaa tietysti my?s liikenteest? aiheutuvien p??st?jen v?hentymiseen. Ilmansaasteiden lis?ksi v?hentyy my?s melusaaste, jota kuorma-autot aiheuttavat huomattavasti henkil?autoja enemm?n. Reittioptimoinnin osana t?rke?ksi tekij?ksi nousee tyhjennysten aikatauluttaminen eli t?i- den niin sanottu skedulointi. J?rkev?ll? ty?njaolla voidaan parantaa entisest??n tyhjennys- reittien tiiviytt? ja v?ltt?? turhia ajokilometrej? ja maksimoida ajank?ytt?? kannattavam- maksi. Valitettavasti aina aikatauluja ei voida muuttaa, vaan ne annetaan jostain sellaiselta taholta, jonka intresseiss? ei ole optimaalinen, j?rkev? ja ekologinen reititys. J?tehuollon reitinoptimoinnin malleihin olisi siis ensiarvoisen t?rke?? saada tuotua n?it? edell? mainittuja seikkoja mukaan. Toisin sanoen, oikean toimintaymp?rist?n dynamiikan implementointi nykyisiin malleihin. Toisaalta se toisi lis?? muuttujia jo ennalta vaikeasti ratkaistaviin ongelmiin. Silti nykyisi? malleja olisi hyv? saada parannettua tuomalla koke- musper?isen reitityksen parhaita ominaisuuksia mukaan niihin. 53 6 Johtop??t?kset Tyhjennysreittien optimoinnilla voidaan saavuttaa kerrannaisvaikutusten kanssa merkitt?- vi? vuotuisia kustannuss??st?j? verrattuna kokemusper?iseen reititt?miseen. Niiden lis?ksi my?s ymp?rist?hy?dyt voivat olla merkitt?vi? v?hentyneiden ajokilometrien my?t?. Perin- teinen kokemusper?inen reititt?minen on (ollut) tehokas keino reittien optimointiin, jos reittej? ja ajoneuvoja on v?h?n. Kokemusper?inen reititt?minen vaatii kuljettajalta ja suun- nittelijalta toimialueen tuntemusta. Ohjelmistoavusteinen suunnittelun merkitys korostuu mit? enemm?n asiakaspisteit? ja kalustoa on. Silti siihen pit?isi saada lis?? kokemusperus- teisen reitityksen ominaisuuksia. Malleja pit?isi parantaa vastaamaan dynaamisen toimin- taymp?rist?n haasteisiin. Ajosuunnittelun eli aikatauluttamisen merkitys korostuu hyvin suureksi. Oikealla ja sopi- valla aikataulutuksella tyhjennyspisteet jaetaan oikeille p?iville ja mahdollisimman tiivii- siin alueisiin. Kapasiteetissa otettaisiin huomioon kuitenkin joustovaraa. Autoon j?tett?isiin siis aina laskennallisesti hieman varaa mahdollisiin ylit?ytt?ihin. Kapasiteettia on vaikeaa m??ritt??, koska tyhjennett?vien s?ili?iden tavaran koostumusta ja m??r?? on vaikea enna- koida. Kapasiteetti vaihtelee autojen ominaisuuksista riippuen. Lis?ksi jatkuvasti kehite- t??n uuden tyyppisi? ratkaisuja kuorma-autoihin. Ne voivat lis?t? tai v?hent?? kapasiteettia nykyisest?. Esimerkiksi ?hybridi-pakkaajissa? akkujen viem? tila on poissa kokonaiskan- tavuudesta ja kapasiteetista. Toisaalta ajoneuvojen fyysisell? koolla on taipumus ajansaa- tossa kasvaa. Tyhjennys olisi j?rkevint? suorittaa niin ett? reitti aloitetaan kauimmaisista pisteist?, jotta jos kapasiteetti tulee t?yteen, olisivat j?ljelle j??neet pisteet mahdollisimman l?hell? tyhjennyspaikkaa. Toisaalta ajoneuvo kannattaa tyhjent?? aina kun kuormaa on kyydiss? ?tarpeeksi? ja tyhjennyspaikka sopivasti ajoreitin l?heisyydess?. Reittien tiiviys parantaa niiden optimaalisuutta. Yksitt?isten pisteiden hakeminen kaukaa varsinaisen ydin ajoalueen ulkopuolelta on kallista ? niin ajassa, kilometreiss? kuin rahassa mitattuna. Maantieteellisesti kompaktein tyhjennysalue on usein my?s optimaalisin. Toi- saalta joskus tyhjennysrytmien takia voidaan kohde joutua ajamaan kaukaakin sen p?iv?n niin sanotusta optimaalisesta ajo-alueesta. Esimerkiksi jos on m??ritelty, ett? kohde tulee tyhjent?? kolme kertaa viikossa ja p?iv?t eiv?t saa olla per?kk?isi?, ainoa vaihtoehto on ajaa ne maanantaisin, keskiviikkoisin ja perjantaisin. Toiset alueet ovat kaupunkirakenteen takia v?ljempi? kuin toiset (muun muassa asumistyypin ja yritysten sijoittumisen takia). Tiiviystarkastelulla voidaan kohdistaa markkinointi ja asiakashankinta toimet sellaisille 54 alueille joilla tyhjennyspisteit? on lukum??r?isesti v?h?n. N?in on mahdollista parantaa reitin kannattavuutta. Ymp?rist?huolto on toimialana maantieteellisesti vahvasti segmen- toitunut varsinkin p??kaupunkiseudulla. T?m? johtuu juuri siit?, ett? tuotto perustuu vo- lyymiin ja toisaalta kulujen minimointiin. Kaiken kaikkiaan yrityksen toimintojen optimoinnilla on t?rke? tekij? sen kilpailukyvyn ja p?rj??misen kannalta. Markkinat muuttuvat koko ajan ja palveluiden, kuten kuljetuspalve- luiden kilpailuttaminen yleistyy jatkuvasti. 55 Kirjallisuus Angelli, E & MG. Speranza (2002). The application of a vehicle routing model to a waste- collection problem: two case studies. Journal of the Operational Research Society (2002) 53, 944?952. Anttila, M. (2012). Kuljetuskustannustaulukko. Henkil?kohtainen s?hk?postiviesti 25.4.2012. Barbarosoglu, G. & D. Ozgur (1999). A Tabu Search Algorithm for the Vehicle Routing Problem. Computers & Operations Research Vol. 26, Issue 3, 255?270. Benjamin A. M. & J. E. Beasley (2010). Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facili- ties. Computer and Operation Research 37 (12): 2270?2280. Blum, C. & A. Roli (2003). Metaheuristics in Combinatorial Optimization: Overwiev and Conceptual Comparison. ACM Computing Surveys Vol. 35, Issue 3, 268?308. Br?ysy, O. (2007). Optimoinnin hy?dyt kunnallisissa kuljetuksissa ja palveluissa. . Jyv?skyl?n yliopisto. Br?ysy, O. & M. Gendreau (2005). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science Vol. 39, Issue 1, 104?118. Cerny, V. (1985). A Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications Vol. 45, 41?51. Christofides, N., Mingozzi, A.& P. Toth (1979). Teoksessa Christofides, N., Mingozzi, A., Toth P & C. Sandi (toim). The Vehicle routing problem. Combinatorial Optimiza- tion. 315?338 s. Chichester, Wiley. Clarke G. & J. W. Wright (1964). Scheduling of Vehicles from a Central Depot to a Num- ber of Delivery Points. Operation Research vol. 12 Issue 4, 568?581. 56 Dantzig, G.B. & J. H. Ramser (1959). The truck dispatching problem. Management sci- ence 1959 vol 6. 80?91. De Meulemeester, L., G. Laporte, F. V. Louveaux & F. Semet (1997). Optimal sequencing of skip collections and deliveries. Journal of Operation Research Society 48, 57?64. De Smith J. M., Goodchild F. M. & P. A. Longley. (2009). Geospatial Analysis A Com- prehensive Guide To Principles, Techniques and Software Tools. s.560. Troubador Publishing Ltd, Great Britain. Digiroad (2011). Digiroad tietolajien kuvaus versio 2.0. Liikennevirasto. 9.5.2011. < http://www.digiroad.fi/aineisto/fi_FI/aineisto/_files/84098414620708735/default/D igiroad_tietolajien_kuvaus_20.pdf>. Dijkstra, E. (1959). A Note on Two Problems in Connection with Graphs. Numerische Mathematik Vol. 1, 269?271. Dror, M., Laporte G. & P. Trudeau (1989). Vehicle routing with stochastic demands: properties and solutions frameworks. Transportation Science 23, 161?175. Eiselt, H. A. (1995). Arc routing problems, Part I: The Chinese postman problem. Opera- tions Research vol. 43, no. 2 (Mar/Apr 1995), 231. Esri (2012a). ArcGIS Desktop Help: Algorithms used by Network Analyst. . 17.4.2012. Environmental Systems Research Institute, Redlands, California. Esri (2012b). ArcGIS Desktop Help: Relationships between network analysis classes in the vehicle routing problem. . 17.4.2012. Environmental Systems Research Institute, Redlands, California. Flood, M. M. (1956). The Travelling-salesman problem. Operations Research 4 , 61?75. Gendreau, M., Hertz, A. & G. Laporte (1994). A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science Vol. 40, Issue 10, 1276?1290. 57 Gendreau, M., Laporte G. & R. Seguin (1996). Stochastic vehicle routing. European Jour- nal of Operational Research 88, 3?12. Gillett, B. & L. Miller (1974). A heuristic algorithm for the vehicle dispatch problem. Op- eration Reseach 22, 340?390. Glover, F. (1996). Ejection Chains, Reference Structures and Alternating Path Methods for Traveling Salesman Problems. Discrete Applied Mathematics Vol. 65, Issue 1-3, 223?253. Hansen, P. & N. Mladenovic (2001). Variable Neighborhood Search: Principles and Ap- plications. European Journal of Operational Research Vol. 130, Issue 3, 449?467. Hyyrynen, K. (2008). Hy?tyj?tteiden alueker?yspisteverkoston optimointi p??kaupunki- seudulla. Pro-gradu ?tutkielma. Helsingin Yliopisto, Maantieteen laitos. Kim, B., Kim, S. & S. Sahoo (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research 33, 3624?3642. Kirkpatrick, S., C. D. Gelatt & M. P. Vecchi (1983). Optimization by Simulated Annealing. Science Vol. 220, Issue 4598, 671?680. Kyt?joki, J., Nuortio T., Br?ysy, O. & M. Gendreau (2007). An Efficient variable neigh- borhood search heuristic for very large scale vehicle routing problems. Computers & Operation Research 34 (2007), 2743?2757. Land, A. H. & A. G. Doig (1960). An automatic Method of Solving Discrete Programming Problems. Econometrica vol. 28, Issue 3, 497?520. Lau, H., Sim, M. & K. Teo (2003). Vehicle routing problem with time windows and a lim- ited number of vehicles. European Journal of Operational Research 148 (2003), 559?569. Maukonen, M. (2012). Kuljetustalouden perusteita. Tavaraliikenteen yritt?kurssi ? kurssikansio. SKAL Kustannus Oy, Helsinki. Naddef, D. & G. Rinaldi (2002). Teoksessa Toth, P. & D. Vigo (toim.) Branch-and-cut algorithms for the capacitated VRP. The Vehicle Routing Problem. SIAM Mono- graphs on Discrete Mathematics and Applications, 53?84 s. Philadelphia. 58 Karadimas, N., Doukas, N., Kolokathi, M. & G. Defteraiou (2008). Routing Optimization Heuristics Algorithms for Urban Solid Waste Transportation Management. Journal WSEAS Transactions on Computers archive Volume 7 Issue 12, 2022?2031. Nuortio, T., J. Kyt?joki, H. Niska, & O. Br?ysy. (2006). Improved route planning and scheduling of waste collection and transport. Expert Systems with Applications Vol. 30 Issue 2, 223?232. Osman, I. H. (1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research Vol. 41, Issue 1-4, 421?451. Potvin, J. & J. Rousseau (1993). A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operation Re- search 66, 331?340. R?is?nen, I (2009). Kuljetusteht?v?t, niiden ratkaisumenetelm?t ja soveltaminen k?yt?nn?n laivakuljetusten optimointiin. Diplomity?. s. 127. Teknillinen korkeakoulu, Fysii- kan laitos. Sahoo, S., Kim, S. & B. Kim (2005). Routing Optimization for Waste Management. Inter- faces Vol. 35, No 1, 24?36. Shaw, P. (1997). A New Local Search Algorithm Providing High Quality Solutions to Ve- hicle Routing Problems. Working paper, Department of Computer Science, Univer- sity of Strathclyde, Glasgow, Scotland. Sipster, M. (2006). Introduction to the theory of computation. s. 456. Thomson Course Technology, Boston. Solomon, M. (1987). Algorithms for the vehicle routing and scheduling problem with time windows. Operations Research 35(2), 254?265. Suikkanen, J. (2002). P??kaupunkiseudun kiireellisten sairaankuljetusyksik?iden asema- paikkojen optimointi paikkatietoj?rjestelmien avulla. Pro-gradu ?tutkielma. 70 s. Helsingin Yliopisto, Maantieteen laitos. 59 Tilastokeskus (2012). Tilasto: Kuorma-autoliikenteen kustannusindeksi [verkkojulkaisu]. ISSN=1796-3745. marraskuu 2011. Helsinki: Tilastokeskus [viitattu: 12.5.2012]. Tilastokeskus (2013). Tilasto: Energian hinnat [verkkojulkaisu]. ISSN=1799-7984. Hel- sinki: Tilastokeskus [viitattu: 21.5.2013]. Saantitapa: Tapanainen, T. (2010). Luonnossaliikkujan kulkukelpoisuusanalyysin parantaminen tar- koilla maastotiedoilla. Pro-gradu ?tutkielma. 56 s. Helsingin Yliopisto, Geotietei- den ja maantieteen laitos. Tolvanen, J. (2007). Postin perusjakelun jakelutoimipaikan sijainnin mallintaminen ja op- timointi. Pro-gradu ?tutkielma. 120 s. Helsingin Yliopisto, Maantieteen laitos. Toth. P. & D. Vigo (2002). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. 363 s. Society for Industrial and Applied Mathe- matics, Philadelphia. Sepp?nen, T. (2012). Rekkaleikkurista tehd??n n?kyv?mpi. Vartti 25.4.2012. Voudouris, C. & E. Tsang (1998). Guided local search. European Journal of Operational Research Vol. 113, Issue 2, 80?119. ?ljyalan keskusliitto (2013). ?ljytuotteiden valmisteverotus. 20.5.2013. .