VRP:tä sovitettaessa GA:lle ratkaistavaksi muutama algoritmin yksityiskohta on huomioi-tava. Optimointiongelman näkökulmasta olennaisimmat asiat ovat sovellettava tietoraken-ne, rajoitteiden huomiointi ja fitness-arvon laskeminen.
3.1.1 Tietorakenne
GA käsittelee populaatiota, joka koostuu yksilöistä. Nämä esittävät ratkaisuja optiomoin-tiongelmalle kromosomina. Tämä on perinteisesti binäärikoodattu luvuilla 0 ja 1. Luvussa 2.2.4 todetaan, että binäärikoodattu kromosomi ei sovellu hyvin TSP:n kaltaisille ongel-mille. Täten se ei myöskään sovellu VRP:lle, koska VRP on TSP:n yleistys. Sovelletaan siis reaalikoodattua kromosomia, jota ehdotetaan Luvuissa 2.2.4 ja 2.2.5.
Tutkitaan Taulukossa 3.1 esitettyä tietorakennetta esimerkkiratkaisun avulla. Ajoneuvo aloittaa vasemmalta – varastosolmusta 0. Se kulkee asiakkaan 1 luo, jonka jälkeen se jatkaa matkaa asiakkaan 2 luo ja niin edelleen. Kyseisessä tietorakenteessa piilee muu-tama ongelma. Ajoneuvot aloittavat ja lopettavat varastossa; mistä tiedetään, milloin ajo-neuvo palaa takaisin varastoon, vai onko kyseesä vain yhden ajoajo-neuvon reitti? Palaako ajoneuvo edes takaisin varastosolmuun 0? Nazifet al.esittävät tutkimuksessa [1] saman-kaltaista tietorakennetta ilman varastosolmuja, jossa ajoneuvojen reitit päätetään ajoneu-vojen kapasiteettien maksimoinnilla. Tällainen tietorakenne on yksinkertainen ja siten te-hokas CVRP:lle, mutta sen käyttö sellaisenaan saattaa tuottaa ongelmia muiden rajoittei-den, kuten maksimiajanTmax ja aikaikkunoiden [ei, li], kanssa. Jos jokin reitti on
kapa-siteettia lukuun ottamatta ideaalinen (eli ei ristiriitoja aikaikkunoiden kanssa), siihen yhä lisätään asiakkaita, koska kapasiteetteja ei ole vielä käytetty optimaalisesti. Seurauksena lisättyjen asiakkaiden aikaikkunat saattavat rikkoutua. Tätä voi tapahtua hyvin usein, jos asiakkaita on paljon, jolloin GA ei pysty etenemään ollenkaan.
Taulukko 3.1.Ensimmäinen versio sovellettavasta tietorakenteesta, jota populaation yk-silöt käyttävät.
0 1 2 3 4 5 6 7 8 9
Taulukossa 3.2 esitetään tietorakenne, joka eroaa Taulukon 3.1 tietorakenteesta siten, et-tä ajoneuvojen reitit erotellaan toisistaan varastosolmun 0 avulla. Tällaista tietorakennetta on käyttänyt Hosseinabadiet al.tutkimuksessa [29], jossa selvitetään OVRP:n ratkaise-mista heidän ehdottamaa gravitaatioemulointiin perustuvaa lokaalihakualgoritmia (Gra-vitational emulation local search) käyttäen. Tällainen tietorakenne soveltuu hyvin – yhtä VRP:n laajennusta lukuun ottamatta (MDVRP). Miten voimme tietää, mitä varastosolmuja sovelletaan, jos varastosolmu 0 toimii vain erottimena? Reittejä ilmenee myös yksi män kuin varastosolmuja, mikä voi aiheuttaa ongelmia, jos erilaisia varastoja on enem-män kuin yksi. Korjataan tietorakennetta vielä sen verran, että esitetyt ongelmat voidaan ratkaista.
Taulukko 3.2.Toinen versio sovellettavasta tietorakenteesta, jota populaation yksilöt käyt-tävät.
1 2 3 0 4 5 6 0 7 8 9
Taulukon 3.3 esittämä tietorakenne on lopputulos Taulukon 3.2 vastineesta, jossa varas-tosolmu 0 on lisätty myös ensimmäisen reitin alkuun. Kun ratkaisua luetaan vasemmalta oikealle olettaen, että ajoneuvon reitti päättyy seuraavan varastosolmun kohdalla, tieto-rakenteesta selviää, mitä varastosolmuja eri ajoneuvot käyttävät reiteillään. Tätä tietora-kennetta käytetään työn loppuun saakka. Seuraavaksi käsitellään valittuun tietorakentee-seen liittyviä ongelmia sekä toimenpiteitä, joilla tietorakenteen mukana tulleet ongelmat ratkaistaan.
Taulukko 3.3.Lopullinen versio sovellettavasta tietorakenteesta, jota populaation yksilöt käyttävät. Alempi ratkaisu havainnollistaa varastosolmujavdi ∈VD, jotka ovat olennaisia VRP:n laajennuksessa MDVRP.
0 1 2 3 0 4 5 6 0 7 8 9
vd1 1 2 3 vd2 4 5 6 vd3 7 8 9
Tietorakenteessa oletetaan, että ratkaisu alkaa varastosolmulla. Tutkitaan ratkaisua, jota kuvitetaan Taulukossa 3.4. Se on kelvoton, koska se alkaa asiakassolmulla: miten ensim-mäiset asiakassolmut kartoitetaan ajoneuvon reitiksi, ja mistä varastosolmusta kyseinen ajoneuvo aloittaa? Tämä ongelma korjataan takaamalla, että varastosolmu pysyy aina ensimmäisenä ratkaisussa. Alustusvaiheessa satunnaisesti luotuihin yksilöihin kohdiste-taan kahden alleelin välinen vaihto siten, että ensimmäinen järjestyksessä havaittu varas-tosolmu vaihdetaan ratkaisun ensimmäisen solmun kanssa, jos tämä ei ole varastosol-mu. Muokkausoperaatioissa, kuten risteytys- ja mutaatio-operaatioissa, jätetään ensim-mäinen solmu huomiotta, jotta varastosolmu jää aina ensimmäiseksi.
Taulukko 3.4.Sovellettavan tietorakenteen esittämä ongelma, jossa ratkaisun ensimmäi-nen solmu ei ole varasto.
1 2 3 vd1 4 5 vd2 6 7 vd3 8 9
Tutkitaan Taulukon 3.5 esittämää ratkaisua. Miten ratkaisua pitäisi tulkita, jos siinä esiin-tyy useita varastosolmuja peräkkäin? Ajoneuvot aloittavat ja lopettavat niissä varastoissa, joista ne ovat reittinsä aloittaneet. Toisin sanoen ne eivät poikkea varastoissa matkan var-rella. Taulukon 3.5 esittämä ratkaisu voidaan tulkita siten, että varastosolmustavd1 aloitta-va ajoneuvo ei oikeastaan kulje minnekään. Samanlainen käsittely tehdään ajoneuvolle, joka aloittaa varastosolmustavd2. Sillä välin varastosolmusta vd3 aloittava ajoneuvo käy kaikkien asiakkaiden 1–9 luona ja palaa varastoonvd3. Tulkitsemalla ratkaisu näin käy il-mi, että vain yksi ajoneuvo kohdistetaan jokaiseen asiakkaan luo. Ongelmalle on siis koh-distettu 3 ajoneuvoa, joista vain yhtä on tarvittu. Ongelmalle asetetut rajoitteet saattavat tehdä tällaisesta ratkaisusta kelvottoman. Tätä ilmiötä tutkitaan Luvussa 3.2.3.
Taulukko 3.5. Sovellettavan tietorakenteen esittämä ongelma, jossa varastosolmuja il-menee ratkaisussa peräkkäin.
vd1 vd2 vd3 1 2 3 4 5 6 7 8 9
Taulukko 3.6 kuvittaa ratkaisua, jossa viimeinen solmu on varasto. Tilanne on periaattees-sa periaattees-samankaltainen Taulukon 3.5 ratkaisun kansperiaattees-sa. Ratkaisun viimeisen solmun jälkeen viimeistä reittiä kulkeva ajoneuvo palaa takaisiin siihen varastoon, mistä se on aloittanut – tässä tapauksessavd3. Täten kyseessä oleva ajoneuvo ei kulje minnekään, minkä vuoksi sitä ei käytetä itse ratkaisussa.
Taulukko 3.6.Sovellettavan tietorakenteen esittämä ongelma, jossa ratkaisun viimeinen solmu on varasto.
vd1 1 2 3 4 vd2 5 6 7 8 9 vd3
Asiakkaat voidaan jakaa kahteen eri luokkaan: pakollisiin ja vaihtoehtoisiin. Tämä on olen-naista VRPP:n tapauksessa. Kaikki pakolliset asiakkaat lisätään ratkaisuun. Kysymyksek-si nousee vaihtoehtoisten aKysymyksek-siakkaiden tila. Kaikkia vaihtoehtoiKysymyksek-sia aKysymyksek-siakkaita ei voida aina lisätä, koska kaikkien asiakkaiden palveleminen ei ole aina mahdollista tiukkojen rajoit-teiden vuoksi. Populaation eri ratkaisut saattavat palvella eri asiakkaita. Vaihtoehtoisista asiakkaista voidaan pitää kirjanpitoa kahdella listalla: yksi pitää kirjaa käytetyistä asiak-kaista, ja toinen käyttämättä jääneistä. Taulukko 3.7 esittää ehdotettua ratkaisua vaih-toehtoisten asiakkaiden esittämään ongelmaan.
Taulukko 3.7. Sovellettavan tietorakenteen esittämä ongelma, jossa ratkaisuun liittyy vaihtoehtoisia asiakkaita. a) Nykyinen ratkaisu. b) Lista käytetyistä, vaihtoehtoisista asiak-kaista. c) Listä käyttämättömistä, vaihtoehtoisista asiakasiak-kaista.
a) vd1 1 2 3 10 vd2 4 5 6 11 vd3 7 8 9 12
b) 10 11 12 – – – – – – – – – – – –
c) 13 14 15 16 17 18 – – – – – – – – –
Tässä luvussa esitetyt muutokset tietorakenteessa vaikuttavat Luvuissa 2.2.4 ja 2.2.5 esi-tettyihin risteytys- ja mutaatio-operaattoreihin. Näitä tutkitaan tarkemmin Luvussa 3.2.2.
3.1.2 Rajoitteet
GA muokkaa populaation yksilöitä risteytyksen ja mutaation myötä sekä kerran alustuk-sessa. Näiden toimenpiteiden jälkeen yksilöt täytyy tarkistaa ennen kuin ne hyväksytään populaatioon, koska seuraavat rajoitteet voivat rikkoutua:
• MaksimiaikaTmax(kuinka kauan ajoneuvot voivat olla reiteillään)
• MaksimietäisyysDmax(ajoneuvojen reittien maksimipituus)
• Ajoneuvojen kapasiteettiQ(kuinka paljon yksi ajoneuvo voi kantaa tavaraa)
• Asiakkaiden (kovat) aikaikkunat[ei, li](milloin asiakkaita voidaan palvella)
Jos ratkaisu rikkoo optimointiongelman rajoitteita, se on kelvoton. Kun populaatio koos-tuu yksilöistä, jotka koostuvat rajoitteita rikkovista ratkaisuista, se ei ole luotettava. Täten ratkaisut on tarkistettava välittömästi, kun niitä on muokattu tai luotu.
Ohjelma 3.1 esittää pseudokoodia, jolla tarkistetaan maksimiaika ja -etäisyys jokaiselta ajoneuvolta. Funktio”total_distance”laskee sen matkan pituuden, jonka ajoneuvo kulkee reitissä olevien asiakkaiden luona järjestyksessä, kun ajoneuvo aloittaa ja lopettaa reitin määräämässä varastossa. Funktio ”distance_to_time” kääntää kuljetun matkan ajaksi.
Lisäksi on huomioitava asiakkaiden palveluajat, sillä tavaroiden lastaamisessa (ja purka-misessa) kuluu aikaa. Tämä hoidetaan funktiolla”total_service_time”.
1 def v a l i d a t e _ d t ( p a t h _ t a b l e , i n d i v i d u a l , s t , d_max , t_max ) :
Ohjelma 3.1.Kokonaismatkan ja -ajan rajoitteiden tarkistaminen.
1 def v a l i d a t e _ c a p a c i t y ( p a t h _ t a b l e , i n d i v i d u a l , q _ l i s t , q_max ) :
Ajoneuvojen kapasiteettien rajoituksien huomioiminen tehdään Ohjelmalla 3.2. Funktio
”total_capacity” laskee yhteen kaikki ajoneuvon käyttämän reitin asiakkaiden kysynnät.
Tätä sitten vertaillaan ajoneuvojen maksimikapasiteetin kanssa.
Maksimiaikarajoitetta tarkistaessa on myös huomioitava odotusajat, jos asiakkailla on ai-kaikkunoita. Kovia aikaikkunoita käsitellessä ajoneuvo ei saa saapua myöhässä, mikä huomioidaan Ohjelmassa 3.3. Tässä ei huomioida maksimiaikaa ja -etäisyyttä, sillä näi-den yhdistäminen Ohjelman 3.1 kanssa on yksinkertaista (maksimiajan tapauksessa on kuitenkin huomioitava myös odotusajat, joita Ohjelmassa 3.1 ei ole käsitelty).
Kun populaation yksilön ratkaisu on tarkistettu rajoitteiden kannalta, seuraava toimenpide perustuu tarkistuksen lopputulokseen. Jos tarkistuksen myötä havaitaan rajoitteen rikko-mus, yksilön ratkaisu korvataan toisella ratkaisulla, joka myös tarkistetaan (tästä lisää Luvussa 3.2.3). Jos yksilön tarkistuksessa ei havaita rajoitteiden rikkomuksia, se täytyy seuraavaksi arvioida, jotta GA tietää, kuinka hyvä se on. Seuraavaksi käsitellään VRP:n ja tämän laajennuksien arvioimista.
1 def v a l i d a t e _ t w ( p a t h _ t a b l e , i n d i v i d u a l , s t , t w _ l , tw_u ) :
Ohjelma 3.3.Asiakkaiden kovien aikaikkunoiden tarkistaminen.
3.1.3 Arviointi
Fitness-arvojen avulla GA päättelee, mitkä yksilöt ovat parempia kuin toiset. Valikoimalla hyvät fitness-arvon omaavat yksilöt risteytysvaihetta varten odotukset ovat sellaiset, että hyvät geenit siirtyvät jälkeläisille, jolloin näillä on vielä paremmat fitness-arvot.
VRP:n fitness-arvo saadaan yksinkertaisesti sen minimoitavasta yhtälöstä (2.5). Vastaa-vasti CVRP:n fitness-arvo saadaan yhtälöstä (2.9), OVRP yhtälöstä (2.16), VRPP yhtä-löstä (2.20), MDVRP yhtäyhtä-löstä (2.33) ja VRPTW yhtäyhtä-löstä (2.38). Koska tavoitteena on minimoida kustannuksia, GA:ta tulee muokata siten, että se suosii alemman fitness-arvon omaavia yksilöitä (VRPP:n tapauksessa on muistettava maksimoida tuotot ja tarvittaessa minimoida matkakustannukset). Vaihtoehtoisesti voidaan soveltaa yhtälöä (2.45), jolloin minimointi muuttuu maksimoinniksi.
Joillakin VRP:n laajennuksilla tavoitteena on minimoida ajoneuvojen lukumäärä m. Al-goritmin yksinkertaistamisen vuoksi sitä pidetään vakiona. Luvussa 3.1.1 esitettyjen on-gelmakohtien vuoksi on kuitenkin mahdollista, että ajoneuvoja tulee käytettyä vähemmän kuin mitä on varattu. Tätä käsitellään enemmän Luvussa 3.2.3.