3.2 Algoritmin kokoonpano
3.2.3 Lopetuskriteerit ja muut yksityiskohdat
Kun GA lopetetaan aikaisin, ratkaisu saadaan nopeasti, mutta tämä on yleensä kauem-pana globaalista optimista. Kun GA:n annetaan kehittää populaatio useamman sukupol-ven ajan, ratkaisun laatu paranee. Jos aikaa annetaan vielä enemmän, ratkaisun laatu ei välttämättä parane merkittävästi, koska tuolloin on mahdollista, että GA on löytänyt lokaa-lin (tai globaalokaa-lin) optimin. Täten on luontevinta lopettaa suoritus suppenemisen kohdalla.
Tätä varten sovelletaan Luvussa 2.2.6 esitettyjä lopetuskriteerejä, joita ovat sukupolvien lukumäärätgminjagmax, fitness-arvotzminjazmaxkynnysarvonztavulla sekä CPU-ajat.
Lopuksi käsitellään muita yksityiskohtia, joilla parannetaan GA:n suorituskykyä sekä al-goritmin suunnittelussa törmättyihin ongelmiin. Käsiteltävät asiat liittyvät huonon elitismin kitkemiseen, hyvän elitismin lisäämiseen, monipuolisuuden parantamiseen sekä ylläpi-toon, varastosolmujen optimointiin ja ajoneuvojen lukumäärän ongelmakohtiin.
Kun populaatio alkaa koostua hyvistä yksilöistä, ne saattavat toistua ja siten korvata popu-laation muita yksilöitä. Seurauksena populaatio muuttuu hyvin yksipuoliseksi, eli suppe-nee jotakin ratkaisua kohti. Tällainen elitismi on populaatiolle haitallista, joten sitä on kit-kettävä. Tässä sovelletaan suodatusmenetelmää, jota Nazifet al.käyttävät tutkimuksessa [1]. Ensimmäiseksi vanhempien ja jälkeläisten sukupolvet yhdistetään yhdeksi populaa-tioksi. Sitten saatu populaatio järjestetään fitness-arvojen mukaan. Seuraavaksi järjestet-ty populaatio jaetaan kahtia. Populaation ensimmäinen puolikas (fitness-arvojen suhteen parempi puoli) valitaan uuden sukupolven populaatioksi. Lopuksi monipuolisuuden yllä-pitämistä varten korvataan identtiset yksilöitä umpimähkäisillä yksilöillä. Tässä oletetaan, että saman fitness-arvot omaavat yksilöt ovat identtisiä toistensa kanssa. Koska kahden populaation parhaat yksilöt liittyvät yhteen populaation, elitismin voidaan myös todeta ole-van ylläpidetty, sillä populaatiossa on seurauksena useita yksilöitä, jotka poikkeavat toi-sistaan hyvillä – mutta eri suurilla – fitness-arvoilla.
Populaation monipuolisuudella varmistetaan, että populaatio löytää useita hyviä, moni-puolisia ratkaisuja yhden sijaan. Monipuolisuutta ylläpidetään mutaatio-operaattoreilla.
Näiden lisäksi sovelletaan samaa menetelmää, jota käytetään suodatusmenetelmässä:
muutaman sukupolven välein – mutta useammin kuin suodatusmenetelmässä – popu-laatio järjestetään yksilöiden fitness-arvojen mukaan. Jos löytyy yksilöitä, joilla on samat fitness-arvot, näistä ylimääräiset korvataan satunnaisesti luoduilla yksilöillä.
MDVRP:n tapauksessa ajoneuvojen käyttämät varastot vaikuttavat matkakustannuksiin.
Jokin varasto voi olla lähempänä joitakin asiakkaita kuin toinen varasto. Varastojen luku-määrä verrattuna asiakkaiden lukuluku-määrään on yleensä hyvin pieni, minkä vuoksi on mah-dollista tehokkaasti optimoida ajoneuvojen reittejä siten, että jokainen ajoneuvo käyttää sellaista varastoa, joista kertyvät kustannukset ovat mahdollisimman pieniä. Tässä tietysti oletetaan, että ajoneuvot eivät ole rajoitettu tiettyihin varastoihin, eli jokaisessa
varastos-sa on ajoneuvoja varastos-saatavilla. Kun varastot optimoidaan näin, erillistä mutaatio-operaattoria varastosolmuja varten ei tarvita.
Taulukoissa 3.5 ja 3.6 esitetyt ongelmat tuottavat ajoneuvoja, jotka eivät kulje minnekään.
Tällöin joidenkin ajoneuvojen reitit ovat pidempiä, mikä saattaa johtaa ratkaisujen hylkää-miseen rajoitteiden vuoksi. Näitä rikkovien yksilöiden ratkaisujen korvaamista varten on luotu muutama yksinkertainen menetelmä. Nämä ovat seuraavia:
1. Täysin satunnaisia ratkaisuja tuotetaan niin kauan, kunnes löydetään ratkaisu, joka ei riko rajoitteita. Jos nämä ovat kevyet, satunnaisratkaisuilla voidaan kätevästi mo-nipuolistaa populaatiota. Tiukoilla rajoituksilla ne aiheuttavat GA:n hajaantumista.
2. Rajoitteita rikkova ratkaisu korvataan GA:n parhaalla löydöllä. Korvaustoimenpide onnistuu erittäin nopeasti, mutta seurauksena populaation monipuolisuus kärsii, koska populaatio voi täyttyä identtisistä ratkaisuista.
3. GA:n paras löytämä ratkaisu mutatoidaan kerran. Jos saatu ratkaisu rikkoo rajoit-teita, tehty mutaatio peruutetaan ja toista mutaatiota yritetään. Tätä toistetaan niin kauan, kunnes rajoitteita rikkomaton ratkaisu löydetään. Koska kelvottomat ratkai-sut korvataan parhaan löydöksen muunnoksilla, populaatioon lisätään elitismiä ja mahdollisesti myös monipuolisuutta.
4. Rajoitteita rikkovaa ratkaisua mutatoidaan niin kauan, kunnes se ei riko rajoitteita.
Jos rajoitukset ovat tiukat, tällä menetelmällä voi kulua hyvin pitkä aika, koska yksilö tarkistetaan joka kerta, kun sitä on mutatoitu.
5. Ratkaisu korvataan GA:n löytämällä ratkaisulla, jota sitten mutatoidaan niin kauan, kunnes kunnollinen ratkaisu löytyy. Tämä on menetelmien 2 ja 4 yhdistelmä.
6. Korjaustoimenpiteen sijaan kelvoton ratkaisu poistetaan kokonaan ja GA:n anne-taan luoda uusi yksilö tavallisesti.
VRP:n ratkaisemista varten ajoneuvojen lukumäärä m on valittava ennen suorituksen aloitusta. Jos ongelman rajoitukset ovat tiukat, pienelläm GA voi joutua vaikeuksiin kel-vollisten ratkaisujen löytämisessä. Suurilla m ratkaisuja löytyy siten, että alussa käyte-tään monta ajoneuvoa, ja useiden muutosta myötä ratkaisuun muodostuu Taulukon 3.5 mukaisia varastojonoja sekä pitkiä ja kelvollisia reittejä. Liian suurillamGA hidastuu: rat-kaisussa onm+nsolmua, ja vaihtelevasti vähemmän, jos siihen sisältyy vaihtoehtoisia asiakkaita. Tämä harmillisesti johtaa muuttujanmeri arvojen kokeilemiseen. Nyrkkisään-tönä voidaan käyttää ongelman rajoitteita: mitä tiukemmat rajoitukset ovat, sen enemmän ajoneuvoja varataan. Toinen ongelma, johon tässä törmätään, on ajoneuvojen puute. Jos ajoneuvoja on rajoitetusti, jää kaksi vaihtoehtoa: käytetään rajoitettu määrä ajoneuvoja GA:n suorituksessa, jolloin suoritus on hyvin hidas tai välittömästi keskeytynyt, tai käyte-tään suurempi määrä ajoneuvoja ja toivoa, että lopputulos käyttää riittävästi ajoneuvoja.
4 RATKAISEMINEN
Tässä luvussa sovelletaan Luvussa 3 esiteltyjä VRP- ja GA-kokoonpanoja Luvussa 2.1 esitettyjen ongelmien ratkaisemista varten. Ensin käsitellään yksinkertaista esimerkkiä kaikilla esitetyillä VRP:n laajennuksilla. Sitten tutkitaan, miten GA suoriutuu erilaisissa suorituskykytesteissä. Lopuksi sitä kokeillaan laajemmissa VRP-instansseissa, joihin liit-tyy myös testitapaus, joka perustuu todelliseen tilanteeseen. Esimerkkitapauksen, suori-tuskykytestien ja todellisen testitapauksen käsittelylle sovelletaan työtä varten tehtyä tie-tokoneohjelmaa, joka on toteutettu tieteellisellä Pythonilla (NumPy, SciPy ja MatPlotLib) ja on avoimesti saatavilla GitHub-palvelussa [42].
Aloitetaan käsittelemällä esimerkkitapausta, jota on esitelty Luvussa 2.1 eri laajennusten kuvittamisessa. Liitteessä A sijaitsee taulukko, joka sisältää yksityiskohtaisempia tietoja esimerkkitapauksesta, kuten koordinaatit, kapasiteetit, palveluajat, tuotot, aikaikkunat ja sakkokertoimet. Asetetaan kaikille laajennuksille yhteiset parametrit. Nämä ovat nähtä-vissä Taulukossa 4.1.
Taulukko 4.1.Esimerkkitapauksessa sovelletut olennaiset parametrit. Poikkeukset maini-taan erikseen. D-T on matkan ja ajan välinen suhde. T-C on ajan ja kustannusten välinen suhde. D-C on matkan ja kustannuksen välinen suhde. Suodatuksen frekvenssi on suku-polveittain: 100:n sukupolven välein samanlaiset yksilöt korvataan satunnaisilla yksilöillä, ja 500:n sukupolven välein sovelletaan itse suodatusstrategiaa.
VRP-parametrit Alustusparametrit Operaattoriparametrit Lopetuskriteerit
m 10 np 100 Valitsija Turnaus gmin 2000
D-T 1.00 Alustaja Random qt 5 gmax 10 000
T-C 0.00 – – pt 0.75 CPUmin 10s
D-C 1.00 – – Risteytys VX CPUmax 10min
Tmax ∞ – – pc 0.85 zmin −∞
Dmax ∞ – – pm 0.10 zmax ∞
Q 50 – – Suodatus 100/500 zt 0
Rajoitteita rikkovat yksilöt korvataan satunnaisesti luoduilla yksilöillä.
Ratkaistaan ensimmäisenä VRP yksinkertaisimmassa muodossa. Ainoana rajoitteena toimii ajoneuvojen lukumäärä, joka on jo sinänsä reilu. Täten algoritmilla on suurimmalta osin vapaat kädet ongelman ratkaisemisessa.
(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.1.Esimerkkitapauksen VRP:n löydettyyn optimiratkaisuun liittyviä tuloksia.
Kuva 4.1 esittää algoritmin tuottamia tuloksia laajentamattoman VRP:n ratkaisusta. Piikit Kuvaajassa 4.1a - lukuun ottamatta ensimmäisen sukupolven piikkiä - merkitsevät tilantei-ta, joissa suodatusmenetelmää ja samanlaisten yksilöiden paikkausta on suoritettu. Juu-ri ennen seuraavaa piikkiä viiva kulkee suuJuu-rimmalta osin vaakasuuntaisesti, joka viittaa GA:n suppenemista lokaaliin (tai globaaliin) optimiratkaisuun. Kuvaajasta 4.1b nähdään käyrä, jonka muoto muistuttaa funktiota x1. Ratkaisun laatu paranee nopeasti suorituksen alussa ja hitaasti loppupuolella. Kun käyrä lakkaa liikkumasta pystysuunnassa kokonaan, GA on löytänyt optimiratkaisunsa, globaali tai ei. Kuvasta 4.1c selviää välittömästi, että optimiratkaisu saadaan yhden ajoneuvon käytöstä. Mitä vähemmän ajoneuvoja käyte-tään, sen vähemmän paluumatkoja tehdään.
Seuraavaksi käsitellään esimerkkitapauksen CVRP, jossa asiakkaiden kysynnät on huo-mioitava. Kun Q = 50, yksi ajoneuvo ei enää riitä kaikkien asiakkaiden palvelemiseen, sillä asiakkaiden kokonaiskysyntä on Liitteessä A olevien tietojen mukaan∑︁n
i=1qi = 222. Ajoneuvoja tarvitaanm≥5, jotta kaikki kysynnät voidaan tyydyttää.
Kuva 4.2 esittää tulokset esimerkkitapauksen CVRP:stä. Kuvassa 4.2c eri väriset silmu-kat merkitsevät reittejä, joita eri ajoneuvot kulkevat. Näiden kulkusuunnalla on merkitystä vain VRPTW:n tapauksessa – tai jos asiakkaiden väliset etäisyydet eivät noudata kolmio-epäyhtälöä|cij|+|cjk| ≥ |cik|(eli kustannusmatriisi ei ole symmetrinen). Vaikkakin
suo-(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.2.Esimerkkitapauksen CVRP:n löydettyyn optimiratkaisuun liittyviä tuloksia.
datusmenetelmän tarkoituksena on monipuolisuuden saavuttamisen avulla löytää parem-pia ratkaisuja, Kuvaajasta 4.2a nähdään, että näin ei aina tapahdu: GA on ensimmäisenä löytänyt Kuvan B.4c mukaisen ratkaisun, mutta suodatusmenetelmän käytön seuraukse-na GA on suppeutunut huonompaan ratkaisuun sukupolvestag ≈1700lähtien.
Esimerkkitapauksen OVRP:n tulokset sijaitsevat Kuvassa 4.3. Kuvasta 4.3c nähdään, et-tä useammalla kuin yhdellä ajoneuvolla voidaan minimoida matkakustannuksia eniten.
OVRP:ssä ajoneuvot eivät tee paluumatkoja varastoon, minkä vuoksi useammalla ajo-neuvolla voidaan minimoida asiakkaiden välisiä matkakustannuksia. Jos ensisijaisena ta-voitteena on minimoida ajoneuvojen lukumäärä, tätä on vähennettävä manuaalisesti, sillä esitetty GA ei erikseen pyri minimoimaan niitä eikä tarjoa suoraa käännöstä kustannusten ja ajoneuvojen välille.
Seuraavaksi käsitellään esimerkkitapauksen VRPP:tä, jossa asiakkaiden palveleminen ei ole pakollista, mutta niin tekemisestä saadaan tuottoja. Tässä tarkastellaan ongelman PTP-puolta. TOP-puolta käsitellään Liitteessä B. Asetetaan tälle tapaukselle tiukempia rajoituksia, jotta saadaan tuloksia, joissa oikeastaan jätetään joitakin asiakkaita palvele-matta. Asetetaan ajoneuvojen lukumääräksim = 3ja maksimiajaksiTmax = 600. Koska tuottoja on rajoitetusti, ongelmalle voidaan tarvittaessa asettaa lopetuskriteeriksizmax =
∑︁n
i=1pi = 7989sopivalla kynnysarvollazt, esimerkiksizt =mTmax = 3·600 = 1800.
(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.3.Esimerkkitapauksen OVRP:n löydettyyn optimiratkaisuun liittyviä tuloksia.
PTP:n tulokset yllä mainituin rajoituksin löytyvät Kuvasta 4.4. Kuvaajien 4.4a ja 4.4b käy-rät ovat nyt ylösalaisin, koska tavoite on muuttunut minimoinnista maksimointiin. Kuvaa-jassa 4.4a esiintyvät piikit ovat pitkiä ja ilmenevät useammin. Näitä ilmiöitä selittävät asiakkaiden vaihtoehtoisuus ja tiukat rajoitteet. Kun satunnainen yksilö luodaan, vaihtoeh-toisten asiakkaiden lukumäärä valitaan satunnaisesti. Jos näitä on vähän, fitness-arvo on tyypillisesti pieni. Kun niitä on paljon, matkakustannukset voivat syödä suurimman osan tuotoista, jolloin fitness-arvo on taas pieni. Piikkejä ilmestyy usein, koska populaatioon on ilmestynyt rajoitetun ratkaisuavaruuden vuoksi identtisiä yksilöitä. Nämä on korvat-tu suodakorvat-tuksissa sakorvat-tunnaisilla yksilöillä. Fitness-arvoltaan heikkojen yksilöiden valinta on todennäköisempää, koska valinnat ehdokasjoukkoon ovat umpimähkäisiä. Tällaisia piik-kejä voidaan vähentää kasvattamalla muuttujiaqtjapt.
Seuraavaksi käsitellään useamman varaston tapausta, eli MDVRP:tä. Tässä tapaukses-sa varastoiksi on valittu solmut 0, 18 ja 22. Lisätään siihen myös kapasiteettirajoitukset CVRP:stä, jotta tulokset VRP:stä eivät toistu (ks. Liite B MDVRP:n kohdalla). Esimerkki-tapauksen MDVRP-laajennuksen tulokset ovat Kuvassa 4.5. Kuvasta 4.5c nähdään, että varasto 18 on jätetty käyttämättä, mikä on ymmärrettävissä, sillä asiakkaiden etäisyy-det sitä kohti ovat nähtävästi suurempia kuin varastoissa 0 ja 22. Varastoa 18 lähimmät asiakkaat ovat 17 ja 19, mutta nämä voidaan palvella halvemmalla varastosta 22.
(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.4.Esimerkkitapauksen VRPP:n (PTP) löydettyyn optimiratkaisuun liittyviä tulok-sia.
Kun ongelmainstanssiin liittyy useampi kuin yksi varasto, yksilöitä voidaan optimoida Lu-vussa 3.2.3 esitetyn menetelmän mukaisesti. Liitteessä B vertaillaan sen suoriutumista laajemmassa, satunnaisesti luodussa tapauksessa.
Lopuksi tutkitaan rajoittavinta laajennusta VRPTW. Ajoneuvojen on saavuttava asiakkai-den kanssa sovittujen aikaikkunoiasiakkai-den aikoina. Ohjelma automaattisesti optimoi reittejä ensimmäisen asiakkaan suhteen siten, että jos ajoneuvo saapuu liian aikaisin, sen aloi-tusaikaa myöhennetään odotettavan ajan verran. Tällöin ensimmäisen asiakkaan luona ei tarvitse odotella, mikä vähentää kokonaiskustannuksia ajan suhteen.
Kovien aikaikkunoiden tapauksessa algoritmi kulkee erittäin hitaasti. Siihen liittyviä tulok-sia voi tarkastella Liitteessä B. Kuvassa 4.6 sen sijaan simuloidaan kovia aikaikkunoita asettamalla sakkokertoimiksiαijokin suuri arvo (tässä tapauksessa 9999). Tulokseksi on saatu Kuvan 4.6c esittämä ratkaisu, joka ei riko aikaikkunoita ollenkaan. Tällaiset sakko-kertoimet voivat aiheuttaa suuria piikkejä fitness-arvoissa suodatusmenetelmän (sekä sa-tunnaisen paikkausmenetelmän) käytön myötä. GA pystyy nopeasti korjaamaan tällaiset piikit samalla tavalla kuin suorituksen alussa.
Laadultaan parempi ratkaisu on löydettävissä, jos aikaikkunoita on mahdollista joustaa
(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.5. Esimerkkitapauksen MDVRP:n löydettyyn optimiratkaisuun liittyviä tuloksia.
Kapasiteettirajoitukset on huomioitu tässä.
sallimalla saapuminen asiakkaiden luo tavallista myöhemmin. Myöhästymisen merkittä-vyys täytyy ensin selvittää, sillä sakkofunktiot (tai -kertoimet) vaikuttavat ongelman opti-miratkaisuun. Kuvassa 4.7 ilmenee tulokset paremmasta ratkaisusta, jos sovelletaan esi-merkkitapauksen sakkokertoimia.
Liitteessä B esitetään poikkeustapausten lisäksi muita yksityiskohtaisempia tuloksia esi-tetyn GA:n suorituksesta, kuten populaation alustajien, yksilöiden valitsijafunktioiden, ris-teytysoperaattoreiden, mutaatio-operaattoreiden ja korjausmenetelmien vaikutuksia. Ute-liaisuuden myötä siinä katsotaan myös, miten esitetty GA suorituu, kun kaikki laajennuk-set yhdistetään yhteen (VRPP:stä PTP ja VRPTW:stä pehmeät aikaikkunat).
4.1 Suorituskykytestit
Tässä luvussa selvitetään esitetyn GA:n suorituskykyä ratkaisemalla VRP:n eri laajen-nuksille suunniteltuja suorituskykytestejä. Nämä on haettu sivustosta ”VRP-REP” [43].
Suorituskykytesteihin liittyvä data on sitten muokattu ohjelmalle soveltuvaan muotoon.
Suorituksia varten on valittu Taulukon 4.2 mukaiset parametrit. Mainitsematta jääneet pa-rametrit saavat oletusarvot (poislukien kustannusmatriisi), joita esitellään Liitteessä C.
(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.6. Esimerkkitapauksen VRPTW:n löydettyyn optimiratkaisuun liittyviä tuloksia.
Pehmeät aikaikkunat, mutta jokaisen asiakkaan sakkokerroin on9999.
Poikkeukset käytetyistä parametreista mainitaan erikseen. Jokaiselle suorituskykytestil-le varataan 5 yrityskertaa, elsuorituskykytestil-lei toisin mainita. Tässä työssä esitetyt suorituskykytestit on suoritettu Windows 10 x64 -tietokoneella (Versiolla 20H2), jossa on AMD Ryzen 5 5600X 6-ytiminen suoritin (käytetty kellotaajuus on3.70GHz).
Ensimmäisenä ratkaistaan CVRP:lle suunniteltuja suorituskykytestejä. Christofideset al.
ovat esitelleet niitä ensimmäistä kertaa tutkimuksessa [44]. Varastosolmut ovat jokaises-sa testissä solmujoukosjokaises-sa viimeinen solmu. Testitapauksiin 6–10 ja 13–14 liittyy ajoneu-vojen maksimiaikojen lisäksi myös asiakkaiden palveluajat, jotka ovat asiakkaiden kesken yhtäsuuria:10tapauksissa 6–10,50tapauksessa 13 ja90tapauksessa 14 [45]. Taulukos-sa 4.3 kerrotaan lyhyesti jokaisen suorituskykytestin luonne asiakkaiden lukumäärinä ja ajoneuvojen kapasiteetteina. Lisäksi siinä näytetään tunnetut optimiratkaisut, jotka Mes-ter et al. ovat saavuttaneet tutkimuksessa [46], sekä varattujen ajoneuvojen lukumäärä, jolla suoritusyritysten ratkaisut on saatu. Samassa taulukossa olevista tuloksista havai-taan, että tapauksissa, joissan ≤ 100, GA on suoriutunut riittävän hyvin, vaikkakin tun-nettuja optimiratkaisuja ei ole saavutettu. Muissa tapauksissa yritykset ovat heikompia – erityisesti tapauksissa 5 ja 10. Luvussa 4.2 käsitellään tapauksia 4, 5, 9 ja 10 uudelleen.
Seuraavaksi tutkitaan OVRP:lle sopivia suorituskykytestejä, joita Ruizet al.esittävät
tut-(a)Sukupolvien parhaat yksilöt. (b)Optimiratkaisun kehitys ajan suhteen.
(c)Optimiratkaisun kuvallinen ilmentymä.
Kuva 4.7. Esimerkkitapauksen VRPTW:n löydettyyn optimiratkaisuun liittyviä tuloksia.
Pehmeät aikaikkunat esimerkkitapauksen sakkokertoimin.
Taulukko 4.2.Jokaisessa suorituskykytestissä sovelletut parametrit. Poikkeukset maini-taan erikseen. Alustusfunktiota SA käytetään aikaikkunoita sisältävissä tapauksissa (lu-kuun ottamatta tapaukset, joissa on vain reittien maksimiajat), ja NN muissa.
VRP-parametrit Alustusparametrit Operaattoriparametrit Lopetuskriteerit
m Vaihtelee np 100 Valitsija Turnaus gmin 2000
D-T 1.00 Alustaja NN / SA qt 5 gmax 10 000
T-C 0.00 nmax 5000 pt 0.75 CPUmin 1min
D-C 1.00 T(1) 50 Risteytys VX CPUmax 10min
Tmax Vaihtelee psa 1.25 pc 0.90 zmin −∞
Dmax ∞ – – pm 0.20 zmax ∞
Q Vaihtelee – – Suodatus 100/500 zt 0
Rajoitteita rikkovat yksilöt korvataan GA:n löytämän optimiyksilön mutaatiolla.
Taulukko 4.3.Lyhyet koosteet ja tulokset suorituskykytesteistä, jotka on suunniteltu laa-jennukselle CVRP.mon suorituskykytestille varattu ajoneuvojen lukumäärä.z0on tunne-tun optimiratkaisun fitness-arvo. Yrityksistä saaduista fitness-arvoistazminon pienin,zavg on keskiarvo jazmax on suurin. Tulokset on pyöristetty kahden desimaalin tarkkuuteen.
Tunnus n Q Tmax m z0 zmin zavg zmax
CMT01 50 160 ∞ 10 524.61 539.33 559.48 597.65
CMT02 75 140 ∞ 25 835.26 863.71 893.89 907.80
CMT03 100 200 ∞ 40 826.14 860.07 882.65 903.75
CMT04 150 200 ∞ 50 1028.42 1160.33 1175.69 1198.81 CMT05 199 200 ∞ 100 1291.29 1557.52 1632.48 1711.50
CMT06 50 160 200 10 555.43 562.65 580.65 607.73
CMT07 75 140 160 40 909.68 951.87 967.04 979.08
CMT08 100 200 230 60 865.94 900.05 919.84 941.26
CMT09 150 200 200 80 1164.54 1274.69 1325.72 1359.80 CMT10 199 200 200 150 1404.67 1703.59 1727.30 1752.46 CMT11 120 200 ∞ 40 1042.11 1233.72 1275.69 1316.51
CMT12 100 200 ∞ 40 819.56 844.39 881.91 909.86
CMT13 120 200 720 60 1543.26 1682.72 1774.70 1854.10 CMT14 100 200 1040 60 866.37 901.88 933.98 967.36
kimuksessaan [47]. Tunnetut optimiratkaisut on poimittu samasta tutkimuksesta vertailuja varten. Testit ovat alkuperältään samoja kuin yllä esitetyt CVRP:n suorituskykytestit: ai-noa eroavaisuus on se, että ajoneuvot eivät palaa varastoihin. Taulukossa 4.4 sijaitsee tulokset OVRP:n suorituskykytesteistä. Kuten CVRP:n tuloksissa, ne ovat riittävän hy-viä tuloksia. Poikkeuksia ovat samankaltaisesti tapaukset 5 ja 10. Samankaltaisuuksien (CVRP:n kanssa) vuoksi tapauksia 4, 5, 9 ja 10 käsitellään uudelleen Luvussa 4.2.
VRPP:n tapauksessa käsitellään sellaista TOP-ongelmaa, joissa aloitus- ja lopetuspaikat ovat samoja. Tähän liittyen on poimittu yksi testitapaus, joka on peräisin testijoukosta, joi-ta Chaoet al. ovat esittäneet tutkimuksessa [48]. Valittua testitapausta varten on haettu vertailtavaksi tunnettuja optimiratkaisuja, jotka Archettiet al.ovat saavuttaneet tutkimuk-sessa [24]. Tällä kertaa jokaiselle tapauksen osatapaukselle varataan 10 yritystä, ja vain suurin löydetty fitness-arvo esitetään. Lisäksi rajoitteita rikkovia yksilöitä kohdellaan eri tavalla; parhaan yksilön ja sen jatkuvan mutatoinnin sijaan otetaan jokin parhaan yksilön naapuri. Käytettäviä ajoneuvoja on tässä tapauksessa välillä[2,4], mikä saattaa heiken-tää VX:n suorituskykyä. Täten VX:n sijaan käyteheiken-tään yhden pisteen risteytystä.
Tulokset sijaitsevat Taulukossa 4.5. Saavutetut ratkaisut ovat lähellä tunnettuja optimirat-kaisuja, mutta ne heikkenevät nopeasti rajoitusten heikentyessä. Todennäköinen selitys tälle ilmiölle on se, että ainoastaan tuotot määrävät fitness-arvon; GA ei saa hyödyllisiä
Taulukko 4.4.Lyhyet koosteet ja tulokset suorituskykytesteistä, jotka on suunniteltu laa-jennukselle OVRP kapasiteettivaatimuksien kanssa. Tulokset on pyöristetty kahden desi-maalin tarkkuuteen.
Tunnus n Q Tmax m z0 zmin zavg zmax
C1 50 160 ∞ 10 412.96 418.59 425.95 430.19 C2 75 140 ∞ 25 564.06 604.01 615.43 632.22 C3 100 200 ∞ 30 639.26 686.58 704.38 723.42 C4 150 200 ∞ 40 733.13 829.22 854.59 878.10 C5 199 200 ∞ 75 871.21 1144.99 1211.37 1242.32 C6 50 160 200 20 412.96 419.81 428.50 436.67 C7 75 140 160 30 567.59 604.42 620.09 633.84 C8 100 200 230 40 646.75 664.58 691.40 713.52 C9 150 200 200 50 743.51 867.30 898.46 927.59 C10 199 200 200 75 873.89 1088.25 1116.82 1151.91 C11 120 200 ∞ 30 676.40 719.71 784.53 823.15 C12 100 200 ∞ 30 536.20 551.30 582.30 616.36 C13 120 200 720 40 862.74 923.97 988.02 1053.90 C14 100 200 1040 40 554.67 592.42 608.34 628.34
ohjeita paremman ratkaisun löytämistä varten. Jos suorituskykytestejä kohdellaan siten, että ne ovat TOP:n sijaan PTP, matkakustannukset antavat lisäohjeita. TOP:ta vastaavat vastaukset saadaan lisäämällä tuottoihin matkakustannukset. Sivuvaikutuksena ilmenee mahdollisuus, että GA suppenee sellaiseen ratkaisuun, jossa sovelletaan vähemmän ajo-neuvoja: suorituksen alkupuolella tuotot eivät ole tarpeeksi suuria useamman ajoneuvon perusteltuun käyttöön. Tällaisen suppenemisen todennäköisyyttä voidaan pienentää vä-hentämällä matkakustannusten merkitystä muokkaamalla sopivaa suhdearvoa. Tapausta P7T on kokeiltu uudelleen esitetyillä poikkeusjärjestelyillä (aika-kustannus-suhteeksi on asetettu0.50); tuloksiksi on saatu1117,1028ja996. Hyviä ratkaisuja voidaan siten saa-da, mutta se tietysti edellyttää eri parametrien kokeiluja yritysten ja virheiden kautta.
Käytetään Cordeaunet al. tutkimuksessa [49] ratkaistuja MDVRP:n suorituskykytestejä.
Näitä on yhteensä 23, mutta tässä käsitellään niistä ensimmäiset 14. Jokaisessa tapauk-sessa varastosolmut ovat viimeisetndsolmua. Parametreja muutetaan siten, että etäisyys ei käänny kustannuksiksi ollenkaan, vaan aika kääntyy kustannuksiksi kertoimella1.00, ja varastosolmujen optimointi otetaan käyttöön. Taulukossa 4.6 nähdään suurimmalta osin tyydyttävä suoriutuminen eri tapauksissa – lukuun ottamatta tapauksissa 8–11, joita käsi-tellään uudelleen Luvussa 4.2. Suorituksissa on oletettu, että varastosolmujen ja ajoneu-vojen välillä ei ole rajoituksia; ajoneuvoja voidaan käyttää missä tahansa varastosolmussa millä tahansa lukumäärin.
Taulukko 4.5.Lyhyet koosteet ja tulokset suorituskykytesteistä, jotka on suunniteltu laa-jennukselle VRPP (TOP). Jokaisessa testitapauksessa n = 100 samoilla koordinaatis-toilla. Tunnetut optimit ovat saatavilla vain TOP:lle. z0 esittää tunnettua optimia ja zmax yrityksistä saatua suurinta fitness-arvoa.
m = 2 m = 3 m = 4
Tunnus Tmax z0 zmax Tmax z0 zmax Tmax z0 zmax
P7E 50.0 290 250 33.3 175 168 – – –
P7F 60.0 387 289 40.0 247 221 30.0 164 152
P7G 70.0 459 324 46.7 344 268 35.0 217 208
P7H 80.0 521 407 53.3 425 335 40.0 285 254
P7I 90.0 579 450 60.0 487 413 45.0 366 338
P7J 100.0 644 499 66.7 564 431 – – –
P7K 110.0 705 523 73.3 633 439 55.0 520 389 P7L 120.0 767 536 80.0 683 476 60.0 590 440 P7M 130.0 827 561 86.7 762 541 65.0 646 467 P7N 140.0 888 625 93.3 820 561 70.0 730 493 P7O 150.0 945 632 100.0 874 587 75.0 781 548 P7P 160.0 1002 667 106.7 927 620 80.0 846 597 P7Q 170.0 1044 721 113.3 987 632 85.0 906 628 P7R 180.0 1094 739 120.0 1024 660 90.0 970 650 P7S 190.0 1136 815 126.7 1081 714 95.0 1022 675 P7T 200.0 1179 875 133.3 1116 780 100.0 1077 709
Käsitellään lopuksi VRPTW:n suorituskykytestejä. Nämä ovat C1 -testien osajoukko So-lomonin tutkimuksesta [50]. Tunnetut ratkaisut, jotka Kohl et al.ovat saaneet aikaiseksi tutkimuksessa [51], on valittu vertailuja varten. Koordinaatteja on yhteensä 3 eri joukkoa:
yhdessä on 25 asiakasta, toisessa 50 ja kolmannessa 100. Eri tapausten väliset eroa-vaisuudet ovat vain aikaikkunoissa. Kaikissa tapauksissa sovelletaan kovia aikaikkunoita.
Taulukossa 4.7 esitetyt tulokset on laskettu pehmeillä aikaikkunoilla, jotka simuloivat ko-via aikaikkunoita. Tapaukset, joissa n ≤ 50, on ratkaistu lähes täydellisesti, kun taas tapauksissan= 100suoriutuminen on tyydyttävää luokkaa.
Kun ongelmat ovat kooltaan pieniä tai keskisuuruisia, esitetty GA ratkaisee ne tehokkaasti (muttei täysin optimaalisesti) lyhyessä ajassa, kun taas laajemmissa tapauksissa GA jo-ko tarvitsee enemmän aikaa tai suppenee lokaaliin optimiin. Rajoitukset myös vaikuttavat GA:n suorituskykyyn: mitä enemmän rajoituksia on ja mitä tiukempia ne ovat, sen vähem-män on ratkaisuja, jotka kelpaavat lopullisiksi ratkaisuiksi. Mitä enemvähem-män kelvottomia rat-kaisuja, sen todennäköisemmin GA löytää tällaisia ratrat-kaisuja, jolloin on löydettävä jokin muu ratkaisu, mikä on pitkällä juoksulla aikaavievää – etenkin silloin, kun asiakkaiden lukumäärä on hyvin suuri. Tällaisia tapauksia käsitellään seuraavassa luvussa.
Taulukko 4.6.Lyhyet koosteet ja tulokset suorituskykytesteistä, jotka on suunniteltu laa-jennukselle MDVRP kapasiteettivaatimuksien kanssa. Tulokset on pyöristetty kahden de-simaalin tarkkuuteen.
Tunnus n nd Q Tmax m z0 zmin zavg zmax
I01 50 4 80 ∞ 30 576.87 594.90 615.51 637.21 I02 50 4 160 ∞ 30 473.87 489.97 499.42 517.98 I03 75 5 140 ∞ 40 641.20 671.99 697.19 713.80 I04 100 2 100 ∞ 50 1006.66 1158.90 1187.95 1204.40 I05 100 2 200 ∞ 50 753.34 806.72 836.05 883.14 I06 100 3 100 ∞ 50 876.50 987.61 1009.03 1035.36 I07 100 4 100 ∞ 50 891.95 1014.74 1050.05 1083.92 I08 249 2 500 310 200 4482.44 6726.06 6968.50 7277.55 I09 249 3 500 310 150 3920.85 5773.13 5886.64 6030.06 I10 249 4 500 310 150 3714.65 5558.00 5628.33 5691.49 I11 249 5 500 310 150 3580.84 5129.70 5572.96 5978.22 I12 80 2 60 ∞ 30 1318.95 1358.95 1435.75 1513.92 I13 80 2 60 200 30 1318.95 1337.63 1386.72 1451.72 I14 80 2 60 180 30 1360.12 1424.59 1468.40 1510.85
Taulukko 4.7.Lyhyet koosteet ja tulokset suorituskykytesteistä, jotka on suunniteltu laa-jennukselle VRPTW kovilla aikaikkunoilla ja kapasiteettirajoituksien kanssa. Tulokset on pyöristetty kahden desimaalin tarkkuuteen.
Tunnus n Q Tmax m z0 zmin zavg zmax
C101_025 25 200 1236.0 10 191.30 191.81 191.81 191.81 C101_050 50 200 1236.0 20 362.40 363.25 409.16 491.12 C101_100 100 200 1236.0 50 827.30 1040.27 1142.63 1210.47 C102_025 25 200 1236.0 10 190.30 190.74 213.03 252.40 C102_050 50 200 1236.0 20 361.40 362.17 412.34 462.28 C102_100 100 200 1236.0 50 827.30 1022.98 1087.66 1196.55 C103_025 25 200 1236.0 10 190.30 190.74 203.87 251.53 C103_050 50 200 1236.0 20 361.40 362.17 424.46 451.05 C103_100 100 200 1236.0 50 826.30 1040.73 1087.63 1183.08 C104_025 25 200 1236.0 10 186.90 187.45 189.45 190.74 C104_050 50 200 1236.0 20 358.00 362.17 397.77 445.91 C104_100 100 200 1236.0 50 822.90 1027.28 1063.42 1086.63