Jokaisen sukupolven aikana yksilöitä valikoidaan vähintään 2np vanhemmiksi, luodaan vähintäännp risteytyksen sekä mutaation seurauksesta, ja usein enemmän kuinnp tar-kastetaan sekä arvioidaan. Useimmilla asetuksilla valittavien vanhempien, luotavien ja tarkastettavien yksilöiden lukumäärä kasvaa, jos ongelmaan liittyy rajoitteita. Mitä tiukem-mat rajoitteet ovat, sitä enemmän tätä todennäköisesti tapahtuu. Yhden yksilön tarkastuk-sen ja arvioinnin yhteydessä iteroidaannasiakasta useaan otteeseen. Suurilla asiakaslu-kumäärillä edellä mainitut toimenpiteet alkavat merkittävästi vaikuttamaan suoritusaikoi-hin. Seurausta tästä nähdään Taulukon 4.6 tapausten 8–11 tuloksista.
Seuraavissa suorituskykytesteissä sovelletaan samoja parametreja kuin Luvussa 4.1, mutta poikkeuksina toimivat algoritmin lopetuskriteerit. CPU-aikaa on 1 tunti (ellei toi-sin mainita) ja sukupolvia on rajattomasti käytettävissä. Tällöin GA:lla on enemmän aikaa sekä mahdollisuuksia löytää fitness-arvoltaan parempia ratkaisuja.
Ensin tutkitaan Taulukoissa 4.3 ja 4.4 käsiteltyjä suorituskykytestejä, joissa n ≥ 150. Taulukossa 4.8 esitetään tulokset yhden tunnin suorituksista. Tulokset ovat odotetusti pa-rempia, mutta muutokset ovat hyvin pieniä, vaikkakin algoritmin on annettu käsitellä niitä 6 kertaa pitempään. Koska tunnettua optimia ei ole saavutettu, algoritmi on suppeutunut lokaaliin optimiin. OVRP:n suorituskykytesteissä GA on suoriutunut hieman paremmin ta-pauksissa 9 ja 10, jotka poikkeavat vastaavasti tapauksista 4 ja 5 maksimiajan läsnäololla.
Mahdollinen syy tähän on se, että maksimiaika rohkaisee käyttämään lyhyempiä reittejä, mikä vähentää sellaisia ratkaisuja, jotka rikkovat kapasiteettirajoituksia.
Taulukko 4.8. Lyhyet koosteet ja tulokset CVRP- ja OVRP-suorituskykytesteistä, joissa n ≥150. Tulokset on pyöristetty kahden desimaalin tarkkuuteen.
Tunnus n Q Tmax m z0 zmin zavg zmax zmin/z0
CMT04 150 200 ∞ 50 1028.42 1100.07 1115.99 1139.28 +7%
CMT05 199 200 ∞ 100 1291.29 1413.91 1442.97 1458.43 +9%
CMT09 150 200 200 80 1164.54 1237.76 1245.64 1264.26 +6%
CMT10 199 200 200 150 1404.67 1533.85 1572.65 1608.10 +9%
C4 150 200 ∞ 40 733.13 817.07 821.70 830.46 +11%
C5 199 200 ∞ 75 871.21 1042.29 1052.02 1068.65 +20%
C9 150 200 200 50 743.51 803.47 831.79 844.79 +8%
C10 199 200 200 75 873.89 1014.26 1027.65 1034.76 +16%
Seuraavaksi käsitellään Taulukon 4.6 laajempia suorituskykytestejä. Tulokset Taulukossa 4.9 näyttävät eroavaisuuksia tuloksissa eri CPU-aikojen välillä. Suurin vaikutus on ensim-mäisen tunnin kohdalla, ja seuraavilla tunneilla parannukset ovat keskimäärin 5%. Cor-deau et al. näyttävät tutkimuksen [49] suorituskykytestien tuloksista, että käsitellyt
suo-Taulukko 4.9.Lyhyet koosteet ja tulokset laajoista suorituskykytesteistä, jotka on suunni-teltu laajennukselle MDVRP kapasiteettivaatimuksien kanssa, eri CPU-ajoilla. Jokaisessa testissäQ= 500jaTmax = 310. Tulokset on pyöristetty kahden desimaalin tarkkuuteen.
CPU-aika: 1 h
Tunnus n nd m z0 zmin zavg zmax zmin/z0
I08 249 2 200 4482.44 5600.43 5671.64 5718.90 +25%
I09 249 3 150 3920.85 4920.41 5063.67 5247.79 +25%
I10 249 4 150 3714.65 4633.68 4769.43 4966.69 +25%
I11 249 5 150 3580.84 4548.72 4715.14 4864.22 +27%
CPU-aika: 2 h
Tunnus n nd m z0 zmin zavg zmax zmin/z0
I08 249 2 200 4482.44 5255.37 5400.21 5620.41 +17%
I09 249 3 150 3920.85 4669.75 4752.49 4859.16 +19%
I10 249 4 150 3714.65 4490.23 4531.12 4644.66 +21%
I11 249 5 150 3580.84 4416.10 4504.27 4653.73 +23%
CPU-aika: 3 h
Tunnus n nd m z0 zmin zavg zmax zmin/z0
I08 249 2 200 4482.44 5117.97 5239.47 5366.56 +14%
I09 249 3 150 3920.85 4549.50 4608.30 4740.68 +16%
I10 249 4 150 3714.65 4241.07 4393.11 4539.55 +14%
I11 249 5 150 3580.84 4195.46 4283.05 4363.93 +17%
rituskykytestit 8–11 on ratkaistu keskimäärin 20 minuutissa. Tästä voidaan todeta, että esitetyssä GA:ssa tai tämän toteutuksessa on jotain vialla tehokkuuden kannalta.
Viimeinen suorituskykytesti, jota työssä käsitellään, on VeRoLog-yhteisön vuoden 2016 CVRP-instanssi, jossan = 1068. Näiden sijainnit XY-koordinaatistossa heijastavat olen-naisimpia kaupunkeja eri maissa. [52] Sovelletaan Taulukon 4.2 parametreja seuraavin poikkeuksin: m = 25,Q = 170(suorituskykytestissä sovellettu ajoneuvokapasiteetti) ja alustajan SA parametritnmax = 50000,T(1) = 100japsa = 1.50. Ajoneuvojen lukumäärä on asetettu pieneksi, koska asiakkaiden kysynnät ovat alhaiset (keskiarvo on1.44).
VeRoLog-CVRP-instanssia on yritetty 3 kertaa eri CPU-ajoilla kolmella eri menetelmällä.
Pienimmät saavutetut fitness-arvot yrityksistä sijaitsevat Taulukossa 4.10. Tässä näyte-tään tulokset GA:sta, kun alustajana toimii SA sekä NN, ja SA:sta sellaisenaan eri iteraa-tioiden lukumäärillä. Tuloksista nähdään, että SA suoriutuu itsenäisesti paremmin kuin GA, jossa SA toimii GA:n alustajana, ajan suhteen. Tämä vahvistaa edellä mainittua pää-telmää, jonka mukaan GA:ssa tai sen toteutuksessa on tehokkuuteen liittyviä ongelmia.
Kun alustajana on NN, tulokset ovat merkittävästi parempia: se on löytänyt asiakasrykel-miä ja siten merkittävästi vähentänyt matkakustannuksia. Alustuksen päätyttyä
fitness-Taulukko 4.10. Tulokset VeRoLog-yhteisön CVRP-instanssista eri CPU-ajoilla. Pienim-mät fitness-arvot (kahden desimaalin tarkkuudella) yrityksistä ovat esillä.
CPU-aika 1 h 2 h 3 h 4 h 5 h
zmin (GA + SA) 11 038.45 8757.53 8196.90 7010.65 6267.90 zmin (GA + NN) 3184.31 3140.33 3110.43 3073.56 3001.60
SA-iteraatiot 50 000 100 000 500 000 1 000 000 2 000 000 Kulunut CPU-aika (s) 351.45 680.38 3677.63 7488.45 15 275.19 zmin 22 813.46 19 162.13 10 611.09 7872.89 6297.14
arvoksi on saatu4289.38, ja GA on parantanut sitä arvoksi3446.4610 minuutissa.
Lopuksi käsitellään todellista testitapausta. Kyseessä on Vinka OY:n kuljetustilaukset, jot-ka on anonymisoitu tässä työssä käytettäväksi. Asiakjot-kaita on yhteensä n = 1223. Ajo-neuvoilla on 2 eri kapasiteettityyppiä (Q1 = 60, Q2 = 12) ja asiakkaiden kysyntöjen kes-kiarvot ovat vastaavasti1.71ja0.83. Testitapaus on luonteeltaan CVRPTW kovilla aikaik-kunoilla. Tavoitteena on minimoida ensisijaisesti ajoneuvojen lukumäärä ja toissijaisesti matkakustannukset. Testitapauksessa sovellettavat parametrit ovat Taulukossa 4.11.
Taulukko 4.11. Yrityskohtaisen testitapauksen käsittelyssä käytetyt parametrit. Näiden parametrien lisäksi aikaikkunat simuloivat kovia aikaikkunoita pehmeinä aikaikkunoina.
VRP-parametrit Alustusparametrit Operaattoriparametrit Lopetuskriteerit
Rajoitteita rikkovat yksilöt korvataan GA:n optimiyksilön naapureilla.
Tunnetut ratkaisut ovat saatavilla, mutta niissä on huomioitava, että ne on saavutettu olet-taen, että testitapaus on CVRPTW:n lisäksi avoin (OVRP) ja ajoneuvojen uudelleenkäyt-tö on sallittu (VRPMT). Ongelman avoimuuden vuoksi paluumatkoja ei ole huomioitu eikä optimoitu. Tässä työssä paluumatkoille tehdään poikkeuksellisesti aikamatriisiin(cij) pe-rustuva arvaus; huomioimalla kaikki mahdolliset paluumatkojen ajoajat keskiarvoksi saa-daan noin 23 minuuttia, joka pyöristetään 20 minuuttiin. Tämän verran ajoaikaa lisätään jokaista käytettyä ajoneuvoa kohti. Koska tunnettu ratkaisu on saatu yllä kuvatuilla oletuk-silla ja paluumatkoihin liittyvän tiedon puutteelle on tehty arvaus, on pidettävä mielessä, että vertailut ajoaikojen suhteen eivät ole täydellisiä vääristyneiden lukujen vuoksi.
Asiakkaiden tilaukset toimitetaan yhden viikon eri arkipäivinä. Täten yrityksen testitapaus voidaan jakaa arkipäivien suhteen viiteen pienempään osaongelmaan. Näistä saadut tu-lokset ovat Taulukossa 4.12. Tässä työssä ei ole käsitelty VRP:n laajennusta VRPMT, minkä vuoksi on asetettu m21 = m22. Käytettyjen ajoneuvojen lukumäärä on saatu hy-vin lähelle tunnetun ratkaisun lukemia. Matkakustannukset, jotka esitellään ajoaikoinaT2
verrattuna tunnetun ratkaisun ajoaikoihin T1, eivät ole kovin lohduttavia: melkein yhden henkilön työpäivän tunnit menevät hukkaan.
Taulukko 4.12.Tunnetut ratkaisut ja esitetyn GA:n tulokset yrityskohtaisesta testitapauk-sesta. m11 on tunnetun ratkaisun ajoneuvolukumäärä, m12 tunnetun ratkaisun reittien lukumäärä, T0 on tunnetun ratkaisun kokonaisajoaika jaT1 on sama kuinT0, mutta sii-hen on lisätty arvaukset paluumatkoihin kuluvista ajoajoista.m21,m22jaT2 ovat esitetyn GA:n vastaavat tiedot. Kokonaisajoajat on pyöristetty sekuntitarkkuuteen ja eroavaisuus-prosentit kahden desimaalin tarkkuuteen.
Päivä Maanantai Tiistai Keskiviikko Torstai Perjantai Kaikki
n 286 249 283 173 232 1223
m11 21 17 21 11 16 86
m12 22 20 21 14 17 94
T0 31:15:27 29:31:19 29:10:18 23:34:36 26:43:46 140:15:26 T1 38:15:27 35:11:19 36:10:18 27:14:36 32:03:46 168:55:26
m21 23 18 23 12 18 94
m22 23 18 23 12 18 94
T2 41:23:52 33:27:52 39:10:33 29:20:48 33:28:49 176:51:54 T2−T1 3:08:25 -1:43:27 3:00:15 2:06:12 1:25:03 7:56:28
T2/T1 +8% −5% +8% +8% +4% +5%
Tunnetussa ratkaisussa kuljetaan yhteensä 4970.35km. Tätä ei kuitenkaan huomioida paluumatkoissa. Kun oletetaan, että aika voidaan tasaisesti laskea kilometreiksi, arvauk-siin perustuvat paluumatkat lisäävät kuljettavaa matkaa1015.87kmverran, jolloin kuljet-tu matka on yhteensä5986.22km, ja esitetyn GA:n tuloksesta saadaan6267.63km, eli 281.41kmenemmän. Jos käytetyt ajoneuvot kuluttavat bensaa esimerkiksi30l/100km ja tämän hinnan oletetaan olevan1.50e/l, lisäkustannukset pelkästään bensan kulutuk-sessa ovat noin126.63e. Lisäksi on huomioitava rekankuljettajien palkat, jotka oletetaan tässä olevan14.00e/hilman ylityötunteja. Ylimääräisistä työtunneista kertyy noin111.18 e. Esitetyn GA:n tehottomuus maksaisi kuljetusyhtiölle bensan ja palkanmaksun suhteen 237.81 e enemmän, jos sen tuottamaa ratkaisua sovelletaan yrityskohtaisessa testita-pauksessa. Summa ei ole sinänsä merkittävä kuljetusyrityksille, mutta nämä käsittelevät useita tilauksia, jolloin tällaisia lisäkustannuksia alkaa kertyä paljon pitkällä juoksulla, min-kä vuoksi on tärkeää, että optimointimenetelmät ovat kunnossa.
5 YHTEENVETO
Tässä työssä on tutkittu kombinatorisen optimointiongelman VRP ja sen laajennusten CVRP, OVRP, VRPP (TOP ja PTP), MDVRP ja VRPTW ratkaisemista metaheuristisen al-goritmin GA avulla. Tätä varten on laadittu tietorakenne, jolla VRP esitetään. Lisäksi erilai-sia algoritmeja on suunniteltu GA:n eri vaiheiden hybridisointia varten. Esitetystä GA:sta on toteutettu tietokoneohjelma, joka on avoimesti saatavilla GitHubissa. Sen toimivuus on todettu yksinkertaisella esimerkkitapauksella.
Esitetyn GA:n suorituskykyä on testattu monista tutkimuksista löydetyillä suorituskykytes-teillä. Asiakasmääriltään pienille testeille on varattu 10 minuuttia, kun taas suurille testeille on varattu vaihtelevasti 1–5 tuntia. Pienissä testeissä GA on suoriutunut hyvin, muttei op-timaalisesti. Saatujen ratkaisujen fitness-arvot poikkeavat suurimmalta osin korkeintaan 60% tunnettujen ratkaisujen fitness-arvoista, kun aikaa on käytössä 10 minuuttia. Suuris-sa testeissä GA on löytänyt ratkaisuja Suuris-samankaltaisesti, mutta merkittävästi hitaammin.
Mitä enemmän asiakkaita ongelmassa on, sen hitaampaa hyvien ratkaisujen etsintä on.
Rajoitukset, kuten kapasiteetit ja aikaikkunat, vaikuttavat myös suoritusaikoihin, sillä ne vähentävät kelvollisten ratkaisujen lukumääriä. Tästä syntynyt rajoitettu ratkaisuavaruus on johtanut siihen, että GA on joutunut useammin korvaamaan kelvottomia ratkaisuja.
Näiden korjaamisessa rajoitteita on tarkastettava aina, kun niihin tehdään muutoksia, mi-kä on suurilla asiakaslukumäärillä aikaavievää. Tällaista ongelmaa on yritetty väistää so-veltamalla yksinkertaisia korvausmenetelmiä, joilla on seurauksena kohdattu suppene-vuusongelmia. Tulokset kuljetusyrityksen testitapauksesta ovat osoittaneet, että esitetty GA ei ole kannattava vaihtoehto yritystoiminnassa.
GA perustuu satunnaisuuteen. Populaatio alustetaan satunnaisesti, ja risteytys sekä mu-taatio tehdään satunnaisesti. Työssä on todettu, että (meta)heurististen algoritmien käyttö populaation alustusfunktioina nopeuttavat GA:ta merkittävästi. Tällaista parannusta ei ole kuitenkaan tehty risteytys- ja mutaatiovaiheille. Risteytys- ja mutaatio-operaattorit katso-vat pelkästään yksilöiden kromosomeja; risteytys- ja mutaatio-operaattoreilla ei ole min-käänlaista tietoa siitä, miten niiden muutokset vaikuttavat yksilöiden ratkaisujen laatuun.
Ne saattavat parantua merkittävästi, jos ne tutkivat yksilöiden kromosomien lisäksi näiden fitness-arvoja sekä rajoitteita. Tällä tavalla voidaan esimerkiksi luoda joukko muutoseh-dotuksia, joista fitness-arvoon parhaiten vaikuttava muutos valitaan tehtäväksi.
Yleisenä ratkaisijana GA kätevästi ratkaisee erilaisia VRP:n laajennuksia. Tämän kustan-nuksena kuitenkin toimii sen tehokkuus; eri laajennukset on huomioitava algoritmissa eri tavoin. Esimerkiksi VRPP:ssä on huomioitava vaihtoehtoiset asiakkaat risteytys- ja mu-taatiovaiheessa, kun taas MDVRP:ssä on tavalla tai toisella muistettava, mitä varastoja käytetään (tai päätellä laskelmin, mitkä varastovat toimivat parhaiten eri reiteille). Näihin poikkeuksiin liittyvät tarkistukset kuluttavat aikaa merkittävästi, sillä niitä toistetaan tilan-teesta riippuen enemmän kuin populaatiossa olevien yksilöiden verran yhtä sukupolvea kohti. Tehokkuuden kannalta on täten helpompaa keskittää GA yhteen tai kahteen laa-jennukseen, vaikkakin useamman algoritmin suunnittelua edellytetään, jos yhä halutaan ratkaista useita VRP:n eri laajennuksia.
Algoritmia suunnitellessa on kiinnitettävä erityistä huomiota sen tehokkuuteen. Kun on-gelmat koostuvat useista sadoista asiakkaista, suoritusajat pitenevät merkittävästi, minkä vuoksi ohjelman toteutuskoodi on merkittävä päätös; Pythonin sijaan parempi vaihtoehto voisi olla esimerkiksi C tai C++. Vaihtoehtoisesti laskelmien kiihdyttämistä GPU:lla (Grap-hics Processing Unit, näytönohjain) voi harkita käyttämällä sille kohdistettuja rajapintoja, joita ovat esimerkiksi CUDA (Compute Unified Device Architecture) ja OpenCL (Open Computing Language).
VeRoLog-yhteisön CVRP-instanssin tuloksista on tehty havainto, että SA on suoriutunut selkeästi paremmin kuin GA, joten toteutuskoodin lisäksi on kiinnitettävä huomiota itse toteutukseen. Sovellettu tietorakenne on lopullisesti toimiva, mutta vuorovaikutukset sen kanssa ovat tehottomia. Siihen sisältyy aina ongelmalle varattujen ajoneuvojen verran va-rastosolmuja, vaikkakin näistä tarvitaan vain murto-osaa suorituksen loppupuolella. GA joutuu käyttämään kallista aikaa turhien varastosolmujen ylläpitämiseen. Täten ajoneu-vojen dynaaminen lukumäärä on lopullisesti parempi vaihtoehto; kun ajoneuvo rikkoo jo-takin rajoitetta, ratkaisun korvaamiseen sijaan lisätään yksi ajoneuvo lisää.
VRP:stä on tehty paljon tutkimuksia siitä, miten sen eri laajennuksia voidaan ratkaista.
Ehdotettuja algoritmeja on useita, joista GA on eräs kilpaileva vaihtoehto. Vaikkakin täs-sä työstäs-sä algoritmin toteutus on tehokkuuden kannalta epäonnistunut, monet tutkimukset ovat osoittaneet, että GA on hyvin kilpailukykyinen metaheuristinen algoritmi optimoin-tiongelmien ratkaisemista varten. Käyttämällä parempia työkaluja, kuten yllä mainittuja yksityiskohtia, GA:n soveltuvuutta VRP:n kaltaisissa käytännön tilanteissa on kannatta-vaa pohtia. Tässä työssä on analysoitu sekä ratkaistu VRP GA:lla yksitavoitteisesti, mut-ta todellisissa tilanteissa ne yleistyvät useampimut-tavoitteisiksi. Mahdollinen jatkotutkimus- mut-tai kehitystyötarve liittyy MOGA:n käyttöön VRP:n kompleksisissa laajennuksissa. Joissakin VRP:n laajennuksissa tosiaan on useampia tavoitteita, esimerkiksi matkakustannusten minimointi ja käytettävien ajoneuvojen minimointi. Todellisissa tilanteissa eri tavoitteita voi olla melkein mitä tahansa.
LÄHTEET
[1] Nazif, H. ja Lee, L. Optimised crossover genetic algorithm for capacitated vehicle routing problem.Applied Mathematical Modeling36.5 (toukokuu 2012), pp. 2110–
2117.DOI:https://doi.org/10.1016/j.apm.2011.08.010.
[2] Wang, C. ja Lu, J. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert Systems with Applications 36.2 (maaliskuu 2009), pp.
2921–2936.DOI:https://doi.org/10.1016/j.eswa.2008.01.072.
[3] Sharma, A.Operations Research. Rev. ed. Mumbai, India: Himalaya Pub. House, 2009, 454 p.
[4] Pisinger, D. ja Ropke, S. A general heuristic for vehicle routing problems. Com-puters & Operations Research 34.8 (elokuu 2007), pp. 2403–2435. DOI: https : //doi.org/10.1016/j.cor.2005.09.012.
[5] Archetti, C., Bianchessi, N. ja Speranza, M. G. Optimal solutions for routing prob-lems with profits. Discrete Applied Mathematics 161.4–5 (maaliskuu 2013), pp.
547–557.DOI:https://doi.org/10.1016/j.dam.2011.12.021.
[6] Cavazzuti, M. Optimization Methods: From Theory to Design Scientific and Tech-nological Aspects in Mechanics. 1. Aufl. Berlin, Heidelberg: Springer-Verlag, 2013, 262 p.
[7] Hou, Y. T., Shi, Y. ja Sherali, H. D. Applied Optimization Methods for Wireless Networks. Cambridge, England: Cambridge University Press, 2014, 348 p.
[8] Back, T., Fogel, D. ja Michalewicz, Z.Handbook of Evolutionary Computation. New York, NY: Oxford University Press, 1997, 988 p.
[9] Du, D. Z., Ko, K. I. ja Hu, X. Design and Analysis of Approximation Algorithms.
Vol. 62. Springer Optimization and Its Applications. Springer, New York, NY, 2012, 440 p.
[10] Sörensen, K. Metaheuristics - the metaphor exposed.International Transactions in Operational Research22.1 (tammikuu 2015), pp. 3–18. DOI:https://doi.org/
10.1111/itor.12001.
[11] Alemayehu, T. S. ja Kim, J. H. Efficient Nearest Neighbor Heuristic TSP Algorithms for Reducing Data Acquisition Latency of UAV Relay WSN.Wireless Personal Com-munications95 (2017), pp. 3271–3285.
[12] Lawler, E. L., Lenstra, J. K., Kan, R. A. ja Shmoys, D. B. The traveling salesman problem: A guided tour of combinatorial optimization. New York: Wiley, 1985, 465 p.
[13] Aarts, E. H. L. ja Korst, J.Simulated Annealing and Boltzman Machines. New York, NY: John Wiley & Sons, 1989, 272 p.
[14] Dorigo, M. ja Stützle, T. Ant Colony Optimization. A Bradford Book. MIT Press, 2004, 305 p.
[15] Glover, F. ja Laguna, M.Tabu search. Boston, MA: Kluwer-Academic, 1997, 416 p.
[16] Gendreau, M., Hertz, A. ja Laporte, G. A Tabu Search Heuristic for the Vehicle Routing Problem.Management Science40.10 (lokakuu 1994), pp. 1276–1290.
[17] Glover, F. Tabu Search: A Tutorial.Interfaces20.4 (heinäkuu 1990), pp. 74–94.DOI: https://doi.org/10.1287/inte.20.4.74.
[18] Dantzig, G. B. ja Ramser, J. H. The Truck Dispatching Problem. Management Science 6.1 (lokakuu 1959), pp. 80–91. DOI: https : / / doi . org / 10 . 1287 / mnsc.6.1.80.
[19] Bodin, L. ja Golden, B. Classification in Vehicle Routing and Scheduling.Networks 11.2 (1981), pp. 97–108.DOI:https://doi.org/10.1002/net.3230110204. [20] Stavropoulou, F., Repoussis, P. P. ja Tarantilis, C. D. The Vehicle Routing Problem
with Profits and consistency constraints.European Journal of Operational Research 274.1 (huhtikuu 2019), pp. 340–356.DOI:https://doi.org/10.1016/j.ejor.
2018.09.046.
[21] Miranda, D. M. ja Conceição, S. V. The vehicle routing problem with hard time win-dows and stochastic travel and service time.Expert Systems with Applications64 (joulukuu 2016), pp. 104–116.DOI:https://doi.org/10.1016/j.eswa.2016.
07.022.
[22] Cattaruzza, D., Absi, N. ja Feillet, D. Vehicle routing problems with multiple trips.
Annals of Operations Research271.1 (joulukuu 2018), pp. 127–159.DOI:https:
//doi.org/10.1007/s10479-018-2988-7.
[23] Sariklis, D. ja Powell, S. A heuristic method for the open vehicle routing problem.
The Journal of Operational Research Society 51.5 (toukokuu 2000), pp. 564–573.
[24] Archetti, C., Hertz, A. ja Speranza, M. G. Metaheuristics for the Team Orienteering Problem. Journal of Heuristics 13.1 (helmikuu 2007), pp. 49–76. DOI: https: //
doi.org/10.1007/s10732-006-9004-0.
[25] Archetti, C., Feillet, D., Hertz, A. ja Speranza, M. G. The Capacitated Team Orien-teering and Profitable Tour Problems. The Journal of the Operational Research Society 60.6 (kesäkuu 2009), pp. 831–842. DOI:https://doi.org/10.1057/
palgrave.jors.2602603.
[26] Karakatiˇc, S. ja Podgorelec, V. A survey of genetic algorithms for solving multi depot vehicle routing problem.Applied Soft Computing27 (helmikuu 2015), pp. 519–532.
DOI:https://doi.org/10.1016/j.asoc.2014.11.005.
[27] Taillard, É., Badeau, P., Gendreau, M., Guertin, F. ja Potvin, J. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows.Transportation
Science31.2 (toukokuu 1997), pp. 101–195. DOI:https://doi.org/10.1287/
trsc.31.2.170.
[28] Toth, P., Vigo, D., Desaulniers, G., Madsen, O. ja Ropke, S.Vehicle Routing: Prob-lems, Methods and Applications. Second Edition. Society for Industrial ja Applied Mathematics, joulukuu 2014, 481 p.
[29] Hosseinabadi, A. A. R., Vahidi, J., Balas, V. E. ja Mirkamali, S. S. OVRP_GELS:
Solving Open Vehicle Routing Problem Using the Gravitational Emulation Local Search Algorithm. Neural Computing and Applications 29 (2018), pp. 955–968.
DOI:https://doi.org/10.1007/s00521-016-2608-x.
[30] Yu, V. F., Jewpanya, P. ja Redi, A. A. N. P. Open vehicle routing problem with cross-docking. Computers & Industrial Engineering 94.4–5 (huhtikuu 2016), pp. 6–17.
DOI:https://doi.org/10.1016/j.cie.2016.01.018.
[31] Liu, R., Jiang, Z. ja Geng, N. A hybrid genetic algorithm for the multi-depot open vehicle routing problem. OR Spectrum 36 (2014), pp. 401–421. DOI: https : / / doi.org/10.1007/s00291-012-0289-0.
[32] Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Ana-lysis with Applications to Biology, Control and Artificial Intelligence. University of Michigan Press, 1975, 183 p.
[33] Morris, G. M., Goodsell, D. S., Halliday, R. S., Huey, R., Hart, W. E., Belew, R. K. ja Olson, A. J. Automated Docking Using a Lamarckian Genetic Algorithm and an Em-pirical Binding Free Energy Function. Journal of Computational Chemistry 19.14 (marraskuu 1998), pp. 1639–1662. DOI:https : / / doi . org / 10 . 1002 / (SICI ) 1096-987X(19981115)19:14%3C1639::AID-JCC10%3E3.0.CO;2-B.
[34] Konak, A., Coit, D. W. ja Smith, A. E. Multi-objective optimization using genetic algorithms: A tutorial.Reliability Engineering & System Safety91.9 (syyskuu 2006), pp. 992–1007.DOI:https://doi.org/10.1016/j.ress.2005.11.018.
[35] Baker, B. M. ja Ayechew, M. A. A genetic algorithm for the vehicle routing problem.
Computers & Operations Research30 (2003), pp. 787–800.
[36] Deb, K. An efficient constraint handling method for genetic algorithms.Computer Methods in Applied Mechanics and Engineering186.2–4 (kesäkuu 2000), pp. 311–
338.DOI:https://doi.org/10.1016/S0045-7825(99)00389-8.
[37] Liu, S., Huang, W. ja Ma, H. An effective genetic algorithm for the fleet size and mix vehicle routing problems.Transportation Research Part E: Logistics and Transpor-tation Review 45.3 (toukokuu 2009), pp. 434–445. DOI:https://doi.org/10.
1016/j.tre.2008.10.003.
[38] Goldberg, D. E.Genetic Algorithms in Search Optimization and Machine Learning.
Addison Wesley, 1989, 412 p.
[39] Wu, Y. ja Liu, W. Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks.IET Wireless Sensor Systems 3.2 (kesäkuu 2013), pp.
112–118.DOI:https://doi.org/10.1049/iet-wss.2012.0117.
[40] Karimi, H. ja Yousefi, F. Application of artificial neural network–genetic algorithm (ANN–GA) to correlation of density in nanofluids. Fluid Phase Equilibria 336.25 (joulukuu 2012), pp. 79–83.DOI:https://doi.org/10.1016/j.fluid.2012.
08.019.
[41] Potvin, J. Y., Dubé, D. ja Robillard, C. A hybrid approach to vehicle routing using neural networks and genetic algorithms. Applied Intelligence 6 (heinäkuu 1996), pp. 241–252.
[42] vrp-gen-alg. GitHub. Saatavissa (viitattu 8.5.2021): https://github.com/terratenff/vrp-gen-alg.
[43] Vehicle Routing Problem Repository. VRP-REP. Saatavissa (viitattu 6.1.2021):
http://vrp-rep.org.
[44] Christofides, N., Mingozzi, A. ja Toth, P. The vehicle routing problem.Combinatorial Optimization(1979), pp. 315–338.
[45] Networking and Emerging Optimization. NEO. Saatavissa (viitattu 12.3.2021):
https://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances.
[46] Mester, D. ja Bräysy, O. Active-guided evolution strategies for large-scale capaci-tated vehicle routing problems.Computers & Operations Research 34.10 (lokakuu 2007), pp. 2964–2975.DOI:https://doi.org/10.1016/j.cor.2005.11.006. [47] Ruiz, E., Soto-Mendoza, V., Ruiz Barbosa, A. E. ja Reyes, R. Solving the open
ve-hicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers & Industrial Engineering 133 (heinäkuu 2019), pp. 207–219.DOI:https://doi.org/10.1016/j.cie.2019.05.002.
[48] Chao, I. M., Golden, B. ja Wasil, E. A. The team orienteering problem.European Journal of Operational Research88.3 (helmikuu 1996), pp. 464–474.DOI:https:
//doi.org/10.1016/0377-2217(94)00289-4.
[49] Cordeau, J. F., Gendreau, M. ja Laporte, G. A tabu search heuristic for periodic and multi-depot vehicle routing problems.Networks30.2 (syyskuu 1997), pp. 105–119.
[50] Solomon, M. Algorithms for the Vehicle Routing and Scheduling Problems with Ti-me Window Constraints. Operations Research 35.2 (maaliskuu 1987), pp. 254–
265.DOI:https://doi.org/10.1287/opre.35.2.254.
[51] Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. M. ja Soumis, F. 2-Path Cuts for the Vehicle Routing Problem with Time Windows.Transportation Science 33.1 (helmikuu 1999), pp. 101–116.
[52] Thomopulos, D. ja Vigo, D. VeRoLog Members VRP instances (elokuu 2016). As-sociation of European Operational Research Societies. Saatavissa (viitattu 6.1.
2021): https://www.euro-online.org/websites/verolog/verolog-members-tsp-and-vrp-instances-08-16/.