Ajoneuvoreititysongelman analysointi ja ratkaiseminen geneettisellä algoritmilla

(1)

AJONEUVOREITITYSONGELMAN ANALYSOINTI JA RATKAISEMINEN GENEETTISELLÄ ALGORITMILLA

Diplomityö Tekniikan ja luonnontieteiden tiedekunta Tarkastajat: yliopistonlehtori Henri Hansen yliopisto-opettaja Mika Mattila Toukokuu 2021

(2)

TIIVISTELMÄ

Teemu Perasto: Ajoneuvoreititysongelman analysointi ja ratkaiseminen geneettisellä algoritmilla Diplomityö

Tampereen yliopisto

Teknis-luonnontieteellinen koulutusohjelma Toukokuu 2021

Tässä diplomityössä analysoidaan ja ratkaistaan ajoneuvoreititysongelma, joka on operaatiotutkimuksessa sekä logistiikka-alalla hyvin tunnettu kombinatorinen optimointiongelma. Ajoneuvo- ja lähetetään varastosta palvelemaan asiakkaita, ja kun tämä on tehty, ne palaavat varastoon.

Tavoitteena on minimoida ajoneuvojen tuottamat matkakustannukset. Ajoneuvoreititysongelma muuttuu kauppamatkustajan ongelmaksi, jos ajoneuvoja on vain yksi.

Ajoneuvoreititysongelmasta on esitetty erilaisia laajennuksia, jotka soveltuvat käytännöllisiin tilanteisiin paremmin. Laajennuksista valitaan tutkittavaksi ne, jotka käsittelevät kapasiteetteja, reittien avoimuutta, tuottoja, useampia varastoja ja aikaikkunoita.

Ajoneuvoreititysongelman ja sen valittujen laajennusten käsittelyä varten sovelletaan geneet- tistä algoritmia, joka kehittää ratkaisuja sisältävää populaatiota luonnonvalinnan sääntöjä noudattaen. Sitä muokataan siten, että se soveltuu ajoneuvoreititysongelmalle sekä valituille laajennuk- sille. Lisäksi erilaisia algoritmeja tutkitaan ja valitaan hybridisoitavaksi geneettisen algoritmin eri vaiheisiin, joita ovat populaation alustus, yksilöiden valinta, risteytys ja mutaatio. Hybridisaatioiden avulla pyritään parantamaan geneettisen algoritmin suorituskykyä.

Kun geneettinen algoritmi on suunniteltu, sen toimivuutta ja tehokkuutta testataan erilaisin ai- neistoin. Ensimmäisenä sitä testataan yksinkertaisella esimerkkitapauksella puhtaasti toimivuuden kannalta. Seuraavaksi tutkitaan sen tehokkuutta ratkaisemalla muissa tutkimuksissa käytet- tyjä suorituskykytestejä, joissa suurimmalla osalla tunnetut ratkaisut ovat saatavilla. Lopuksi ge- neettisellä algoritmilla yritetään ratkaista kuljetusyhtiön tarjoama anonymisoitu testitapaus.

Tulokset käytetyistä aineistoista osoittavat, että esitetty algoritmi on toimivuuden kannalta kun- nossa. Laajuudeltaan pienien ongelmien tapauksessa se löytää ratkaisuja, jotka ovat hyvin lähellä tunnettuja ratkaisuja. Suurissa ongelmissa hyvän ratkaisun löytäminen osoittautuu aikaavieväk- si. Lisäksi havaitaan, että toinen metaheuristinen algoritmi suoriutuu paremmin kuin esitetty algoritmi, minkä vuoksi todetaan, että ongelma on esitetyn algoritmin ja sen toteutuksen huonos- sa suunnittelussa. Tästä seuraaviksi toimenpiteiksi ehdotetaan ajoneuvoreititysongelman yhteen laajennukseen erikoistumista, risteytys- ja mutaatio-operaattoreiden parantamista sekä muuttuvan ajoneuvolukumäärän käyttöä vakiolukumäärän sijaan.

Avainsanat: ajoneuvoreititysongelma, vrp, geneettinen algoritmi, ga

Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck -ohjelmalla.

(3)

ABSTRACT

Teemu Perasto: An analysis and a solution to the Vehicle Routing Problem using the Genetic Algorithm

Master of Science Thesis Tampere University

Science and Engineering Programme May 2021

This master’s thesis aims to analyze and solve the vehicle routing problem. It is a well-known combinatorial optimization problem in operations research and logistics field. Customers are ser- viced by vehicles that start and end their routes on a depot. The objective is to minimize resulting travel costs. The problem transforms into the traveling salesman’s problem if only one vehicle is used.

Various extensions of the vehicle routing problem have been created for better use in practical applications. Of these extensions, capacities, route openness, profits, multiple depots and time windows are considered here.

The genetic algorithm is applied as part of handling the vehicle routing problem and its selected extensions. It is based on the development of a population of solutions in accordance with the rules of natural selection. It is modified to work with the vehicle routing problem and its selected extensions. Additionally, various algorithms are examined and hybridized with various phases of the genetic algorithm. These are population initialization, individual selection, crossover and mutation. Hybridization is done in an attempt to improve the performance of the genetic algorithm.

Once the genetic algorithm has been designed, its functionality and performance is tested using a variety of problem instances. It is first tested with a simple example to make sure it works.

Then its performance is tested by solving various benchmarks, the majority of which have known solutions. Lastly it is used to attempt to solve an anonymized test case offered by a logistics company.

Results from used problem instances show that presented genetic algorithm works as in- tended. On lower-scale problems it finds solutions close to optimal ones, whereas on large-scale problems the process is very time-consuming. It is also discovered that another metaheuristic algorithm performs better than presented genetic algorithm; therefore, it is concluded that the performance issues come from the flawed design of both presented genetic algorithm and its im- plementation. Suggested courses of action include specializing in one extension instead of many, improving crossover and mutation operators, and using a variable number of vehicles instead of a fixed number.

Keywords: vehicle routing problem, vrp, genetic algorithm, ga

The originality of this thesis has been checked using the Turnitin OriginalityCheck service.

(4)

ALKUSANAT

Diplomityön teko eteni suurimmalta osin suunnitelmien mukaisesti. Aihealue oli ennes- tään tuttu, sillä olin kandidaatintyötä tehdessä tutkinut kauppamatkustajan ongelmaa.

Haastavinta työn teossa oli algoritmin suunnittelu tehokkuuden näkökulmasta: ilman kon- kreettista toteutusta suunnittelutyö jäi valistuneiden arvausten tekemisiksi, ja muutosten tekeminen toteutuksen jälkeen oli aikaavievää. Jälkikäteen ajatellen parempi lähestymis- tapa olisi ollut erilaisten toteutusten kokeilu, joista parhaimmin suoriutuva algoritmi sekä tietorakenne olisi valittu analysointia varten, ja algoritmien keksimisen sijaan tutkittujen algoritmien soveltaminen.

Työn ohelle toteutin pienoisohjelman, joka piirtää kuvaajia juuri ratkaistuista ongelmista.

Kuvaajat näyttivät selkeästi, että algoritmi tosiaan toimi, mikä motivoi minua jatkamaan.

Vertailut suorituskykytestien kanssa rohkaisivat lisää – vaikkakin laajemmissa ongelmissa tulokset eivät olleet kovin lupaavia. Muutaman kerran päädyin muokkaamaan algoritmin osia suorituskyvyn parantamiseksi, jolloin jouduin toistamaan suorituskykytestejä.

Ohjaajat antoivat alussa suuntaa antavia ohjeita sekä aiheelle olennaisia lähteitä. Työn edetessä he antoivat parannusehdotuksia, kun niitä pyysin. Lisäksi he tekivät järjestelyitä kuljetusyrityksen testitapauksen hankintaan ja anonymisointiin. Usein jouduin kysymään tarkentavia kysymyksiä, jotta kaikki tarvittavat tiedot testitapauksesta olivat hallussani.

Törmäsin samalla muutamaan väärinymmärrykseen, jotka venyttivät työn tekoa muutaman päivän. Tästä olen oppinut, kuinka tärkeää viestinnän selkeyttäminen on.

Odottamaton ongelma, johon törmäsin työtä tehdessä, oli algoritmitoteutuksen kyvyttö- myys ratkaista yrityksen testitapaus. Muutama päivä kului ongelman lähteen selvittämi- seen: algoritmi oli yksinkertaisesti hyvin hidas. Lopullisesti testitapaus tuli ratkaistua, kun kyselin tunnetuista ratkaisuista. Testitapauksen rakenteen luonteen vuoksi oli mahdollista tehdä ositus pienempiin osaongelmiin. Näiden ratkaiseminen sujui ongelmitta.

Kiitän kuljetusyhtiötä Vinka OY testitapauksen tarjoamisesta sekä ohjaajia heidän sinnik- kyydessä viestinnästä kuljetusyhtiön kanssa testitapaukseen liittyvien tietojen hankinnas- sa, yksityiskohtien selkeyttämisessä ja sen valmistelusta diplomityötä varten. Diplomityön teko onnistui ongelmista huolimatta hienosti!

Tampereella, 21. toukokuuta 2021

Teemu Perasto

(5)

SISÄLLYSLUETTELO

1 Johdanto . . . 1

2 Teoria . . . 4

2.1 Ajoneuvoreititysongelma . . . 6

2.1.1 CVRP (Kapasiteetit) . . . 9

2.1.2 OVRP (Avoimet reitit) . . . 11

2.1.3 VRPP (Vaihtoehtoiset asiakkaat) . . . 13

2.1.4 MDVRP (Useampia varastoja) . . . 14

2.1.5 VRPTW (Aikaikkunat) . . . 17

2.1.6 Sovellutukset . . . 19

2.2 Geneettinen algoritmi . . . 20

2.2.1 Alustus . . . 22

2.2.2 Arviointi . . . 24

2.2.3 Valinta . . . 25

2.2.4 Risteytys . . . 28

2.2.5 Mutaatio . . . 30

2.2.6 Lopetus . . . 31

2.2.7 Sovellutukset . . . 32

3 Analysointi . . . 34

3.1 Ajoneuvoreititysongelman kokoonpano . . . 34

3.1.1 Tietorakenne . . . 34

3.1.2 Rajoitteet . . . 37

3.1.3 Arviointi . . . 39

3.2 Algoritmin kokoonpano . . . 40

3.2.1 Populaation alustaminen ja vanhempien valinta . . . 40

3.2.2 Risteytys- ja mutaatio-operaattorit . . . 42

3.2.3 Lopetuskriteerit ja muut yksityiskohdat . . . 45

4 Ratkaiseminen . . . 47

4.1 Suorituskykytestit . . . 52

4.2 Laajemmat ongelmat . . . 59

5 Yhteenveto . . . 63

Lähteet . . . 65

Liite A Esimerkkitapauksen data . . . 69

Liite B Algoritmin yksityiskohtaisempia tuloksia . . . 70

Liite C Oletusparametrit . . . 78

(6)

KUVALUETTELO

1.1 Havainnollistus ajoneuvoreititysongelmasta . . . 2

1.2 Havainnollistus geneettisen algoritmin pääperiaatteesta . . . 3

2.1 Esimerkki ratkaisusta VRP:lle . . . 7

2.2 Esimerkki ratkaisusta CVRP:lle . . . 10

2.3 Esimerkki ratkaisusta OVRP:lle . . . 12

2.4 Esimerkki ratkaisusta VRPP:lle . . . 15

2.5 Esimerkki ratkaisusta MDVRP:lle . . . 16

2.6 Esimerkki ratkaisusta VRPTW:lle . . . 18

2.7 Havainnollistus rulettipyörävalinnasta . . . 26

2.8 Havainnollistus turnausvalinnasta . . . 27

2.9 Yksinkertaiset risteytysoperaattorit . . . 29

2.10 Risteytysoperaattoreita reaalikoodatulle tietorakenteelle . . . 30

2.11 Mutaatio-operaattoreita reaalikoodatulle tietorakenteelle . . . 31

3.1 Yhden ja kahden pisteen risteytysoperaattorit VRP:lle . . . 43

3.2 OX- ja VX-risteytysoperaattorit VRP:lle . . . 44

4.1 Tulokset esimerkkitapauksen VRP:stä . . . 48

4.2 Tulokset esimerkkitapauksen CVRP:stä . . . 49

4.3 Tulokset esimerkkitapauksen OVRP:stä . . . 50

4.4 Tulokset esimerkkitapauksen VRPP:stä (PTP) . . . 51

4.5 Tulokset esimerkkitapauksen MDVRP:stä . . . 52

4.6 Tulokset esimerkkitapauksen VRPTW:stä (kovat aikaikkunat) . . . 53

4.7 Tulokset esimerkkitapauksen VRPTW:stä (pehmeät aikaikkunat) . . . 54

(7)

TAULUKKOLUETTELO

2.1 VRP:n kustannusmatriisin rakenne . . . 8

2.2 OVRP:n kustannusmatriisin rakenne . . . 12

2.3 Binäärilukujen muunnelmia reaaliluvuiksi . . . 20

2.4 Turnausvalintamenetelmän ehdokkaiden voittotodennäköisyyksiä . . . 27

2.5 Seuraukset binäärirakenteen risteytyksestä TSP:ssä . . . 29

3.1 Sovellettava tietorakenne, versio 1 . . . 35

3.4 Sovellettavan tietorakenteen ongelmakohta 1 . . . 36

3.7 Sovellettavan tietorakenteen käsittely VRPP:n kannalta . . . 37

3.8 Sovellettavan tietorakenteen käsittely MDVRP:n kannalta . . . 43

4.1 Esimerkkitapauksessa sovelletut parametrit . . . 47

4.2 Suorituskykytesteissä sovelletut parametrit . . . 54

4.3 CVRP-suorituskykytestien tulokset . . . 55

4.4 OVRP-suorituskykytestien tulokset . . . 56

4.5 VRPP-suorituskykytestien tulokset . . . 57

4.6 MDVRP-suorituskykytestien tulokset . . . 58

4.7 VRPTW-suorituskykytestien tulokset . . . 58

4.8 Laajempien CVRP- ja OVRP-suorituskykytestien tulokset . . . 59

4.9 Laajempien MDVRP-suorituskykytestien tulokset . . . 60

4.10 Tulokset VeRoLog-yhteisön CVRP-instanssista . . . 61

4.11 Yrityskohtaisessa testitapauksessa sovelletut parametrit . . . 61

4.12 Tulokset yrityskohtaisesta testitapauksesta . . . 62

(8)

OHJELMA- JA ALGORITMILUETTELO

2.1 GA:n toteutus ohjelmallisesti. . . 22

2.2 Populaation alustaminen SA:lla. . . 24

3.1 Kokonaismatkan ja -ajan rajoitteiden tarkistaminen. . . 38

3.2 Ajoneuvojen kapasiteettirajoituksien tarkistaminen. . . 38

3.3 Asiakkaiden kovien aikaikkunoiden tarkistaminen. . . 39

3.4 Umpimähkäisen ratkaisun tuottaminen. . . 41

(9)

LYHENTEET JA MERKINNÄT

ANN Artificial Neural Network, keinotekoinen neuroverkko

(C)PTP (Capacitated) Profitable Tour Problem, (kapasitoitunut) tuottoisa matkaon- gelma

CPU Central Processing Unit, suoritin

CPU-aika Suorittimen käyttämä aika komentosarjojen suorittamisessa. Tässä tapauksessa CPU-aika on yhtäpitävä todellisuudessa kuluneen ajan kanssa (C)TOP (Capacitated) Team Orienteering Problem, (kapasitoitunut) ryhmäsuunnis-

tusongelma

CVRP Capacitated Vehicle Routing Problem, kapasitoitunut VRP D-C Etäisyyden ja kustannusten välinen suhde

D-T Etäisyyden ja ajan välinen suhde

EA Evolutionary Algorithm, evolutionäärinen algoritmi GA Genetic Algorithm, geneettinen algoritmi

MDVRP Multiple-Depot Vehicle Routing Problem, useamman varaston VRP MOGA Multi-Objective Genetic Algorithm, monitavoitteinen geneettinen algoritmi NN Nearest Neighbor, lähimmän naapurin hakualgoritmi

OVRP Open Vehicle Routing Problem, avoin VRP OX Order Crossover, järjestetty risteytys SA Simulated Annealing, simuloitu hehkutus T-C Ajan ja kustannusten välinen suhde

TS Tabu Search, tabuhaku

TSP Traveling Salesman’s Problem, kauppamatkustajan ongelma VRP Vehicle Routing Problem, ajoneuvoreititysongelma

VRPMT Vehicle Routing Problem with Multiple Trips, useamman reitin salliva VRP VRPP Vehicle Routing Problem with Profits, tuottoihin perustuva VRP

VRPTW Vehicle Routing Problem with Time Windows, aikaikkunoihin perustuva VRP

VX Vehicle Crossover, ajoneuvokohtainen risteytys

Ajoneuvo Yhden reitin suorittaja

Alleeli Kromosomin yksittäinen elementti Asiakas Solmu, johon liittyy yksi tilaus

Fitness Populaation yksilön objektiivinen arvo Geeni Kromosomissa oleva alleelisekvenssi

(10)

Kromosomi Yksilön esittämä ratkaisu

Populaatio Yksilöistä koostuva joukko, jota geneettinen algoritmi kehittää yksi sukupolvi kerrallaan

Reitti Joukko asiakkaita, joita yksi ajoneuvo palvelee esiintymisjärjestyksessä Solmu Sijainti, johon ajoneuvo voi kulkea. Vastaa joko asiakasta tai varastoa Tilaus Tehtävä, jonka suorittaa korkeintaan yksi ajoneuvo. Tilauksen suorittami-

sella tarkoitetaan samaa asiaa kuin asiakkaan palvelemista Varasto Solmu, josta ajoneuvot aloittavat ja lopettavat näiden reitit Yksilö Populaatiossa oleva yksittäinen ratkaisukokonaisuus

α_i Sakkokerroin

β Tiettyä varastoa käyttävien ajoneuvojen lukumäärä (c_ij) Kustannus-, etäisyys- tai aikamatriisi

c_ij Kahden solmun välisessä matkassa kuluva kustannus/etäisyys/aika δ Asiakkaiden vaihtoehtoisuutta esittävä muuttuja

D Varastosolmujen yhteinen merkintä (kun tämä ilmestyy yhdessä tapauksessa useammin kuin kerran, se esittää mitä tahansa varastosolmua) D_max Etäisyys, jonka ajoneuvot voivat kulkea enintään

E Kaarijoukko

e_i Aikaikkunan alaraja [e_i, l_i] Aikaikkuna

E_{M D} MDVRP:lle suunniteltu kaarijoukko

f(x) Yksilön objektiivisen arvon laskeva funktio γ Kytkin TOP:n ja PTP:n välillä

G Graafi

g Sukupolvi

G_{M D} MDVRP:lle suunniteltu graafi gmax Sukupolvien maksimilukumäärä

g_min Sukupolvien minimilukumäärä fitness-arvon muutoksen suhteen

k Ajoneuvo

li Aikaikkunan yläraja

m Ajoneuvojen (reittien) lukumäärä n Asiakkaiden (tilausten) lukumäärä n_d Varastojen lukumäärä

nmax Iteraatioiden maksimilukumäärä (SA:ssa)

n_p Populaation koko

n_sa Iteraatio SA:ssa

nt Yksilön sijoitus turnauksessa P(A) Todennäköisyys tapahtumalleA

P(A) Todennäköisyys tapahtumanAvastaiselle tapahtumalle

(11)

p_c Risteytystodennäköisyys

p_i Tuotto, jonka saa erään tilauksen suorittamisesta pm Mutaatiotodennäköisyys

p_ri Yksilön todennäköisyys tulla valituksi rulettipyörävalinnassa P⁽ⁿ^sa⁾ Todennäköisyys ehdokasratkaisun valintaan

p_sa Hehkutuskerroin

p_t Turnausvalinnassa ensimmäiseksi sijoittuneen valintatodennäköisyys Q Jokaisen ajoneuvon kapasiteetti

q_i Tilauksen kysyntä

qt Turnausvalinnan osallistujalukumäärä T⁽¹⁾ Alustava lämpötila SA:ssa

t_i Ajoneuvon saapumisaika asiakkaan luona T_k Aika, joka kuluu erään reitin suorittamisessa

T_max Aika, joka määrää, kuinka kauan ajoneuvot voivat olla reiteillään T⁽ⁿ^sa⁾ Lämpötila tietyllä iteraatiolla SA:ssa

V Solmujoukko

VC Asiakasjoukko

V_D Varastojoukko

v_ci Asiakassolmu

v_di Varastosolmu

v_i Solmu

(v_i, v_j) Kaari kahden eri solmun välillä w_i Ajoneuvon odotusaika

wt Yksilön todennäköisyys tulla valituksi turnausvalinnassa (x_ij) Solmukohtainen kohdistusmatriisi

x_ij Kohdistus tietylle matkalle kahden eri solmun välillä x^(g)_i Populaation yksilö GA:ssa,i= 1, ..., n_p

x⁽ⁿ^sa⁾ Nykyisen iteraation ratkaisu SA:ssa x⁽ⁿ^sa⁺¹⁾ Ehdokasratkaisu SA:ssa

(y_ik) Ajoneuvokohtainen kohdistusmatriisi

yik Kohdistus, jossa tietty ajoneuvo suorittaa tietyn tilauksen

z Minimoitava kokonaiskustannus, -etäisyys tai -aika, tai maksimoitava ko- konaistuotto. Identtinen objektiivisen funktionf(x)kanssa. Fitness-arvo z₀ Tunnetun optimiratkaisun fitness-arvo

zavg Tulosten esittelyssä tulosjoukon keskiarvo

z_max Fitness-arvo, jonka ylitettyä suoritus lopetetaan. Tulosten esittelyssä tulosjoukon suurin fitness-arvo

zmin Fitness-arvo, jonka alitettua suoritus lopetetaan. Tulosten esittelyssä tulosjoukon pienin fitness-arvo

z_t Fitness-arvon kynnysarvo, jolla kevennetään fitness-kriteerejä

(12)

1 JOHDANTO

Monet yritykset, kuten kaupat, valmistajat, ravintolat ja jälleenmyyjät, saavat tarvitseman- sa raaka-aineet, ruoat, tuotteet ja kaikkea muuta toimipisteihinsä kuljetus- ja logistiikka- toiminnan avulla. Rekat kantavat raaka-aineita sekä jälleenmyytäviä tuotteita, pakettiau- tot toimittavat postipaketteja asiakkaiden luo tai näiden noutopisteisiin, ja bussit kuljettavat ihmisiä julkisessa liikenteessä. Nämä toimenpiteet yleistyvät entistä enemmän talouden kasvaessa. Asiakkaiden lukumäärä kasvaa ja heidän tarpeet monipuolistuvat. Tarpeiden tyydyttämistä varten on otettava käyttöön enemmän tavaroiden jakelupisteitä, jotka puo- lestaan monimutkaistavat toimitustehtäviä. Näistä aiheutuvien kustannusten (esimerkiksi bensa, työtunnit ja ajoneuvojen ylläpitö) on oltava mahdollisimman pieniä, jotta kuljetusyritykset voivat olla kilpailukykyisiä kuljetusmarkkinoilla. Esitetty ongelma tunnetaan ajo- neuvoreititysongelmana, jota esitellään havainnollistavasti Kuvassa 1.1.

Ajoneuvoreititysongelma (Vehicle Routing Problem, VRP) on kombinatorinen optimointiongelma, jossa asiakkaille on toimitettava tavaraa varastosta saakka. Yhdestä varastosta lähetetään vaihteleva lukumäärä ajoneuvoja, jotka kulkevat niille sunniteltuja reittejä asiakkaita kohti. Kun eräs ajoneuvo on toimittanut kaikki tavarat, sen täytyy matkustaa takaisin varastoon. Jokaiselle asiakkaalle on toimitettava tavaroita, ja täsmälleen yksi ajoneuvo suorittaa sen yhden asiakkaan luona. Tavoitteena on suunnitella ajoneuvoille sellaiset reitit, jotka kattavat kaikki asiakkaat siten, että kuljetuksista kertyvät kustannukset ovat mahdollisimman pienet. [1][2] Jos VRP:ssä on vain yksi ajoneuvo käytettävissä, ky- seisen ajoneuvon on määrä toimittaa tavaraa jokaiselle asiakkaalle ja sitten palata varastoon. Tämän kaltainen tapaus tunnetaan kauppamatkustajan ongelmana (TSP, Traveling Salesman’s Problem). [3, s. 152]

VRP:stä on kehitetty erilaisia ongelmia, jotka soveltuvat enemmän käytännöllisiä tilantei- ta varten. Näitä ovat muun muassa kapasitoitunut VRP (CVRP, Capacitated VRP), avoin VRP (OVRP, Open VRP), tuottoihin perustuva VRP (VRPP, VRP with Profits), useamman varaston VRP (MDVRP, Multiple-Depot VRP) ja aikaikkunoihin perustuva VRP (VRPTW, VRP with Time Windows) [4][5]. Ratkaisemalla VRP:n laajennuksia voidaan parantaa monia logistiikka-, kuljetus- ja verkostojärjestelmiä kilpailukykyisiin kuntoihin vähentämällä kuljetuksiin, etäisyyksiin ja kuluvaan aikaan liittyviä kustannuksia [2]. Laajennuksia on monia, mutta tässä työssä keskitytään yllä mainittuihin VRP:n laajennuksiin.

(13)

Kuva 1.1.Kuvitteellinen kartta, johon on merkitty vierailtavissa olevat kohteet. Vihreä piste merkitsee varaston sijaintia ja punaiset pisteet asiakaspisteitä.

VRP:n analysointia ja ratkaisemista varten sovelletaan geneettistä algoritmia (GA, Gene- tic Algorithm), joka on metaheuristinen ja evolutionäärinen algoritmi. Se perustuu Darwi- nin säännön mukaiseen luonnonvalintaan, jossa parhaat yksilöt valitaan seuraavaan su- kupolveen, kun taas huonot yksilöt katoavat populaatiosta. Tämä prosessi koostuu pää- asiallisesti neljästä eri vaiheesta: populaation alustus, yksilöiden valinta, risteytys ja mutaatio. [6][7, katso 8] GA:n perusideaa näytetään Kuvassa 1.2.

GA:n täydentävän luonteen vuoksi se on helposti muokattavissa sekä parannettavissa hybridisaatioilla muiden algoritmien kanssa. Tällöin optimaalista ratkaisua tavoitellessa GA toimii algoritmina globaalisti, kun taas muut algoritmit toimivat lokaalisti GA:n eri vai- heissa. [2]

(14)

Kuva 1.2. Laatikoissa olevat pisteet esittävät populaatioita eri sukupolvissan. Mitä tum- mempi piste on, sen suurempi fitness-arvo sillä on. Ideana on se, että sukupolvien myötä hyvät geenit korvaavat huonot geenit.

Työn tavoitteena on analysoida sekä ratkaista VRP:tä ja sen valittuja laajennuksia GA:n eri hybridisaatioiden avulla. Luvussa 2 käsitellään kirjallisia selvityksiä VRP:stä ja GA:sta.

Luvussa 3 analysoidaan, miten GA:ta voidaan soveltaa VRP:n ja sen muunnelmien ratkaisemisessa. Luvussa 4 sovelletaan Luvussa 3 käsiteltyjä menetelmiä yksinkertaisen esi- merkin, muutaman suorituskykytestin ja todellisen testitapauksen avulla. Lopuksi tehdään yhteenveto laaditun GA:n soveltuvuudesta VRP:n ratkaisemisessa, jossa pohditaan, mikä on onnistunut, missä on parantamisen varaa ja mitä voisi mahdollisesti tutkia jatkossa.

(15)

2 TEORIA

Optimointiongelmissa ratkaisujen löytäminen on helppoa, mutta tärkeämpää sekä haas- tavampaa on löytää sellaisia ratkaisuja, joiden soveltamisesta kertyvät kustannukset ovat mahdollisimman pienet. Ne voidaan jakaa kombinatorisiin ja jatkuviin optimointiongelmiin.

Kombinatorisissa ongelmissa valitaan optimiratkaisu äärelliessä ratkaisuavaruudessa, ja jatkuvissa ongelmissa ratkaisu saadaan jatkuvaksi määritellystä tavoitefunktiosta, jota joko maksimoidaan tai minimoidaan siihen liittyvien rajoitteiden avulla. Tässä työssä kombinatoriset optimointiongelmat ovat olennaisempia tutkittavan optimointiongelman kannalta.

Kombinatorisia optimointiongelmia ovat esimerkiksi:

• Kokonaislukuoptimointi (Integer Programming) on periaatteessa samanlaista kuin lineaarinen optimointi, jossa määritellään maksimoitava (tai minimoitava) tavoitefunktio (epä)yhtälörajoitteineen. Poikkeuksena toimii se, että muuttujat rajoitetaan kokonaisluvuiksi. Kokonaislukuoptimointi soveltuu tilanteisiin, joissa tavoitteena on määritettävä konkreettisten kappaleiden lukumäärä (esimerkiksi ihmiset, autot ja varusteet jotakin työtä varten) tai pyöristäminen ei ole kelvollinen menettely. [3, s.

18–19, 99–100]

• Selkäreppuongelma (Knapsack Problem) on resurssinhallintaongelma, jossa teh- täviä tekemällä saadaan tuottoja. Nämä ovat tehtävistä riippuvaisia. Tehtävien tekeminen vaatii resursseja, ja niitä voi suorittaa useammin kuin kerran. Saatavilla olevat resurssit ovat äärelliset. Tavoitteena on maksimoida tuotot. [9, s. 1–2]

• Kohdistusongelma (Assignment Problem) on resurssinhallintaongelma, jossa erilaiset resurssit täytyy kohdistaa erilaisiin tehtäviin siten, että jokaiseen tehtävään on kohdistettu täsmälleen yksi resurssi. Resurssien suorituskyvyt kustannuksina eri tehtävissä tunnetaan, jotka on koottu kustannusmatriisille. Tavoitteena on tehtävä sellaiset kohdistukset, joista kertyvät kustannukset ovat mahdollisimman pienet. [3, s. 148–149]

• Kauppamatkustajan ongelmassa (TSP, Traveling Salesman’s Problem) on joukko kaupunkeja, joissa on tarkoitus vierailla. Vierailut suunnitellaan siten, että jokaises- sa kaupungissa vieraillaan täsmälleen kerran, ja viimeisessä kaupungissa vierail- tua on palattava takaisin siihen kaupunkiin, josta matka on aloitettu. Näitä rajoitteita noudattaen tavoitteena on suunnitella matka siten, että kuljettava matka on mahdollisimman lyhyt. [3, s. 152]

(16)

• Ajoneuvoreititysongelma (VRP, Vehicle Routing Problem) on yleistys TSP:stä sii- nä mielessä, että kauppamatkustajia on enemmän kuin yksi. Ajoneuvot vastaavat kauppamatkustajia, kun taas asiakkaat vastaavat kaupunkeja. Jokainen ajoneuvo aloittaa sekä päättää matkansa samasta pisteestä, joka tunnetaan varastona. Vain yksi ajoneuvo vierailee yhden asiakkaan luona. Tilanteesta riippuen ajoneuvojen lukumäärä voi olla rajoite. Tavoitteena on suunnitella ajoneuvoille kustannuksiltaan mahdollisimman pienet reitit. [1][2]

Monet kombinatoriset optimointiongelmat johtavat tilanteisiin, joissa ratkaisuvaihtoehto- ja on niin paljon, että kaikkien ratkaisujen läpikäynti ei ole enää kannattavaa eksakteilla algoritmeilla pitkien laskelma-aikojen vuoksi. Tällaisen ongelman ratkaisemista varten on kehitetty (meta)heuristisia algoritmeja. Heuristinen algoritmi on optimointiongelmasta riip- puvainen, kun taas metaheuristinen algoritmi on optimointiongelmasta riippumaton. Ne eivät välttämättä löydä optimaalisinta ratkaisua, mutta ne löytävät ratkaisuja, jotka ovat melko lähellä sitä. [10]

(Meta)heuristisia algoritmeja on monia, ja niitä on tutkittu merkittävästi operaatiotutkimuksessa, tietotekniikassa ja matematiikassa. Huomattavia esimerkkejä (meta)heuristisista algoritmeista ovat seuraavat:

• Lähimmän naapurin hakualgoritmi (NN, Nearest Neighbor) on yksinkertainen heuristinen algoritmi, jossa solmujen valinta perustuu näiden läheisyyteen. Aluksi valitaan yksi solmu satunnaisesti, jonka jälkeen valitaan aina sellainen käsittelemätön solmu, joka on lähimpänä nykyistä solmua. Tällaista algoritmia sekä sen muunnok- sia sovelletaan usein TSP:n ratkaisemisessa. [11, katso 12]

• Simuloitu hehkutus (SA, Simulated Annealing) on metaheuristinen algoritmi, joka perustuu metallurgiseen tekniikkaan, jossa jotakin materiaalia lämmitetään ja jääh- dytetään kontrolloidusti. Materiaalin kristallit kasvavat kooltaan, jolloin materiaalin epäkohdat häviävät. Hehkutusprosessi alkaa korkeasta lämpötilasta, jossa materiaalin atomit liikkuvat enemmän ja niiden energiatasot ovat korkeat. Sitten materiaalia viilennetään hitaasti, kunnes lämpötasapaino saavutetaan. Atomit saavat enem- män tilaisuuksia lopullisen konfiguraation, jossa ne järjestäytyvät kristallihilaksi, löy- tämiseen. Optimointiongelmissa lämpötila vastaa satunnaisuutta naapuriratkaisun valitsemisessa. Kun lämpötila laskee, iteraatioiden vaihtelevuus laskee jatkuvasti, mikä johtaa algoritmin suppenemiseen, jolloin tästä saatu ratkaisu myös suppenee.

[6, s. 107–110][7, katso 13]

• Hiukkasparvioptimointi (Particle Swarm Optimization) on metaheuristinen algoritmi, joka pyrkii toisintamaan lintujen sosiaalista käyttäytymistä. Linnut etsivät ruokaa ja seuraavat parven johtajaa – eli sellaista lintua, joka on löytänyt ruokaa. Optimoin- tiongelmissa linnut ovat ratkaisuja, jotka seuraavat parven johtajaa – eli ratkaisua, joka on tuolla hetkellä algoritmin löytämä optimiratkaisu. Jokaisella iteraatiolla rat-

(17)

kaisut liikkuvat tietyllä nopeudella sellaiseen suuntaan, jonka määrää funktio, joka ottaa parametreiksi nykyisen hetken parhaan ratkaisun ja henkilökohtaisen parhaan suunnan kohti tiettyjä sijainteja suunnitteluavaruudessa. [6, s. 110–113]

• Muurahaispesäoptimointi (Ant Colony Optimization) on metaheuristinen algoritmi, joka perustuu muurahaisten tekemään yhteistyöhön muurahaispesässä. Muurahai- sia simuloidaan yksinkertaisina ja stokastisina agentteina, jotka viestivät toistensa kanssa ympäristön avulla. Ne rakentavat keskeneräistä ratkaisua inkrementaalises- ti lisäämällä tilanteeseen sopivia ratkaisukomponentteja. [14, s. 33–38]

• Tabuhaku (Tabu Search) on metaheuristinen algoritmi, joka soveltaa hakuhistoriaa.

Tämä sisältää aiemmin löydettyjä ratkaisuja, jotka ovat olleet löytöhetkellä parhaim- pia. Ratkaisusta luodaan sen naapureita, jotka eroavat ratkaisusta yhdellä muutok- sella. Naapuruston paras ratkaisu kirjataan hakuhistoriaan, jonka jälkeen siitä luodaan naapureita samalla tavalla. Jos naapurustosta löytyy ratkaisu, joka on haku- historiassa, se jätetään huomiotta. [7, katso 15][16][17]

• Evolutionäärinen algoritmi (EA, Evolutionary Algorithm) on metaheuristinen algoritmi, joka perustuu Darwinin teorian mukaiseen luonnonvalintaan. Ratkaisuja käsitel- lään populaatiossa, jota kehitetään sukupolveittain. Vahvat yksilöt selviävät seuraa- valle sukupolvelle ja heikot kuolevat sukupuuttoon. Vahvojen ratkaisujen jälkeläiset korvaavat heikot ratkaisut. Olennaisin toimenpide tässä algoritmissa on mutaatio- operaattorin käyttö. [6, s. 103, 116]

• Geneettinen algoritmi (GA, Genetic Algorithm) on EA:n osajoukkoon kuuluva metaheuristinen algoritmi. Se toimii perimmiltään eri tavalla kuin EA, mutta molemmissa algoritmeissa on sama pääperiaate; ratkaisuja ylläpidetään populaatiossa yksi sukupolvi kerrallaan. Tässä algoritmissa risteytysoperaattorin soveltaminen on olen- naisempaa. [6, s. 103, 121][7, katso 8]

Kombinatorisista optimointiongelmista valitaan VRP tutkittavaksi, ja metaheuristisista algoritmeista GA. Ensin tutustutaan optimointiongelmaan VRP sekä sen laajennuksiin. Sen jälkeen tutkitaan algoritmia GA, jota sovelletaan VRP:n ratkaisemisssa. Molempien aihei- den tapauksissa tutkitaan lopuksi niiden käytännöllisiä sovellutuksia.

2.1 Ajoneuvoreititysongelma

VRP on operaatiotutkimuksessa sekä kuljetus- ja logistiikkajärjestelmissä hyvin tunnettu kombinatorinen optimointiongelma. Ajoneuvoja lähetetään yhdestä varastosta toimittamaan tavaraa kaikille asiakkaille siten, että asiakkaan luona käy täsmälleen yksi ajoneuvo ja toimituksista kertyvät kustannukset ovat mahdollisimman pienet. Ajoneuvot palaavat takaisin varastoon reittien päätyttyä. George Dantzig ja John Ramser ovat esittäneet VRP:n ensimmäistä kertaa bensakuljetuksiin liittyvässä tutkimuksessa vuonna 1959. Se

(18)

Kuva 2.1. Eräs ratkaisu VRP:lle. Varasto on solmu 0, ja muut solmut ovat asiakkaita, joita on yhteensä 23. Ratkaisussa käytetään 3 ajoneuvoa, joiden reitit esitetään nuoleista koostuvilla Hamiltonisilla sykleillä. Näiden eri värit merkitsevät eri ajoneuvoja.

on yleistys vuonna 1955 esitetystä TSP:stä. [18]

VRP on NP-kova, joka tarkoittaa sitä, että se on ratkaistavissa epädeterministisessä po- lynomiaaliajassa. Täten sille ei voida muodostaa polynomiaalista yhtälömallia sen op- timiratkaisua varten. [2] Bodin Lawrence ja Golden Bruce ovat todistaneet VRP:n NP- kovuuden tutkimuksessaan vuonna 1981 [19]. Kuva 2.1 esittää VRP:tä graafisesti.

VRP voidaan määritellä matemaattisesti seuraavasti [1][2]: olkoon suunnaton graafi

G= (V, E), (2.1)

joka koostuu solmuista

V ={v0, v1, ..., vn}={0,1, ..., n} (2.2) ja kaarijoukosta

E ={(v_i, v_j)|v_i, v_j ∈V, i < j}, (2.3) jossanon asiakassolmujen lukumäärä ja(v_i, v_j)vastaa suunnatonta kaarta solmujenv_i jav_j välillä. Oletetaan, että solmujoukonV varastosolmu on sen ensimmäinen solmuv₀. Ehdolla i < j varmistetaan, että jokaisen solmun kesken on täsmälleen yksi solmu, lu-

(19)

Taulukko 2.1.VRP:n kustannusmatriisin rakenne. Ensin valitaan vaakarivii, joka esittää aloitussijaintia. Sitten valitaan pystyrivi j, joka esittää kohdesijaintia. Näin saadaan se kustannus, joka kertyy kulkemalla solmustav_i solmuunv_j.

0 1 2 · · · n 0 0 c₀₁ c₀₂ · · · c_0n 1 c₁₀ 0 c₁₂ · · · c_1n 2 c₂₀ c₂₁ 0 · · · c_2n ... ... ... ... . . . ... n c_n1 c_n1 c_n2 · · · 0

kuun ottamatta tapaukset, jossa kaari alkaa ja loppuu samassa solmussa (siis (v_i, v_i)).

Ehdolla v_i ̸= v_j saataisiin jokaisen solmun kesken kaksi kaarta, joka soveltuu epäsym- metrisiin tapauksiin. Tässä tapauksessa graafinGtulisi olla suunnattu. Symmetrisillä ta- pauksilla oletetaan, että(v_i, v_j) = (v_j, v_i).

Varastosta kulkee m itsenäistä ajoneuvoa, jotka vastaavat asiakkaiden v₁, ..., v_n tava- ravaatimuksiin. Ajoneuvojen liikkumiseen liittyy kustannusmatriisi (c_ij), jossa c_ij vastaa kustannusta siitä, että ajoneuvo kulkee asiakkaaltav_i asiakkaanv_j luo. Toisaalta matriisi (c_ij)voidaan nähdä myös pituus- tai aikamatriisina. Taulukko 2.1 esittää sen rakennetta.

Matriisin(c_ij)alkiot liittyvät graafinGyhteyksiin kaarijoukossaE. Symmetrisissä tapauksissa matriisille(c_ij)pätee

c_ij =c_ji. (2.4)

Eräs ratkaisu ongelmalle esitetään kohdistusmatriisilla (x_ij), joka esittää kohdistuksia kustannusmatriisissa(c_ij). Jos x_ij = 1, niin eräs ajoneuvo kulkee solmustav_i solmuun v_j. Josx_ij = 0, niin mikään ajoneuvo ei tee kyseistä matkaa.

Esitettyjen tietojen avulla voidaan määritellä tavoitefunktio VRP:lle:

Minimoiz =

n

∑︂

i=0 n

∑︂

j=0

c_ijx_ij, (2.5)

jonka rajoitteet ovat

n

∑︂

i,j∈S

x_ij ≤ |S| −1, S⊆V \ {v₀} (2.6)

n

∑︂

i=0

x_ij =

n

∑︂

i=0

x_ji =

⎧

⎨

⎩

m, j = 0 1, j = 1, ..., n

(2.7)

x_ij ∈ {0,1}, i= 0, ..., n; j = 0, ..., n (2.8)

(20)

Rajoitteella (2.6) varmistetaan, että kohdistuksia asiakkaiden keskuudessa on tehty vain sen verran kuin pitäisi. Rajoite (2.7) takaa, että ajoneuvot aloittavat ja lopettavat varastossa sekä jokainen asiakas on kohdistettu täsmälleen kerran. Rajoite (2.8) rajoittaa kohdis- tamiseen sovellettavat arvot sopiviksi. Asettamallam= 1ongelma muuttuu TSP:ksi.

Joissakin tapauksissa VRP:n rajoitteisiin lisätään myös maksimiaikaT_max, joka määrää, kuinka kauan ajoneuvo saa olla reitillään. Tätä varten asiakkaille määritetään omat palveluajat, jotka vastaavat tavaroiden purkuaikaa eri asiakkaiden luona. [1][4][16][20] Ajo- neuvojen maksimiaika nähdään kovana aikaikkunana, jota käsitellään enemmän Luvussa 2.1.5. Toisinaan on mahdollista, että asiakkaiden palveluaikoja joko ei tunneta etukäteen tai ne vaihtelevat merkittävästi. Tällaista tapausta on tutkittu mallintamalla palveluaikoja (ja matkoihin kuluvia aikoja) tilastollisina jakaumina. [21]

Ajoneuvon kulkemisessa kuluu aikaa, minkä vuoksi etäisyyden ja ajan välille on asetet- tava jokin suhdearvo. Tämä yleensä asetetaan yksinkertaisuuden vuoksi arvoksi 1.00, eli yksi etäisyyden yksikkö vastaa yhtä aikayksikköä. Monissa tutkimuksissa etäisyyksiä, aikoja ja kustannuksia kohdellaan keskenään vaihtokelpoisesti. Tässä työssä oletetaan, että nämä yksiköt ovat samalla tavalla vaihtokelpoisia, ellei sitä erikseen mainita.

2.1.1 CVRP (Kapasiteetit)

Erittäin yleinen laajennus VRP:stä on tämän kapasiteettiversio CVRP. Tavoitteena on suunnitella ajoneuvojen reitit siten, että niihin liittyviä kapasiteettirajoituksia noudatetaan.

Kaikilla ajoneuvoilla on yhtä suuri kapasiteettiQ, joka ei saa ylittyä. Jokaisella asiakkaalla on oma kysyntänsäq_i. Varastolla ei ole kysyntää, jonka vuoksi asetetaanq₀ = 0. Ajoneu- vojen kapasiteettien kirjanpitoa varten määritetään kohdistusmatriisi (y_ik), joka esittää tietoa siitä, onko asiakkaan vi luona vieraillut ajoneuvo k. Josyik = 1, niin ajoneuvo k täyttää asiakkaanv_i kysynnän, ja muussa tapauksessay_ik = 0. [2]

CVRP määritellään matemaattisesti seuraavasti:

Minimoiz =

n

∑︂

i=0 n

∑︂

j=0

c_ijx_ij, (2.9)

(21)

Kuva 2.2.Eräs ratkaisu CVRP:lle, jossa ajoneuvojen kapasiteetti on 6 ja jokaisen asiakkaan kysyntä on 1. Täten ajoneuvojen reitit voivat sisältää enintään 6 asiakasta.

n

∑︂

i,j∈S

x_ij ≤ |S| −1, S ⊆V \ {v₀} (2.10)

n

∑︂

i=0

q_iy_ik ≤Q, k= 1, ..., m (2.11)

n

∑︂

i=0

x_ij =

n

∑︂

i=0

x_ji =

⎧

⎨

⎩

m, j = 0 1, j = 1, ..., n

(2.12)

m

∑︂

k=1

y_ik =

⎧

⎨

⎩

m, i= 0 1, i= 1, ..., n

(2.13)

x_ij ∈ {0,1}, i= 0, ..., n; j = 0, ..., n (2.14) y_ik ∈ {0,1}, i= 0, ..., n; k= 1, ..., m (2.15)

Uusia rajoitteita ovat (2.11), (2.13) ja (2.15). Rajoitteella (2.11) varmistetaan, ettei ajoneuvojen kapasiteetit ylity asiakkaiden kysynnästä. Rajoite (2.13) takaa sen, että jokainen ajoneuvo käy varastossa ja jokaisen asiakkaan luona käy täsmälleen yksi ajoneuvo.

Kuva 2.2 havainnollistaa CVRP:n ratkaisun luonnetta.

(22)

Jos CVRP:tä varten asetetut ajoneuvokapasiteetit ja asiakkaiden esittämät kysyntävaati- mukset ovat liian tiukat, kaikkien asiakkaiden palveleminen ei ehkä ole mahdollista. Tämä sitten johtaa kahteen eri VRP-laajennukseen: useammat reissut (VRPMT, VRP with Mul- tiple Trips), joissa tiukat rajoitteet voidaan kiertää ohjeistamalla ajoneuvoja suorittamaan useampia reittejä, tai tuottojen priorisointi (VRPP) ajan tai resurssien puutteen vuoksi [5][22]. Näistä optimointiongelmista VRPP:tä tutkitaan tarkemmin Luvussa 2.1.3.

Monissa tutkimuksissa CVRP esitetään yksinkertaisesti VRP:nä, jolla on kapasiteettirajoituksia. Lisäksi muilla VRP:n laajennuksilla oletetaan sisältävän näitä, jolloin ne oikeasti ovat laajennuksia CVRP:stä. Seuraavissa määritelmissä oletetaan, että esitetyt ongelmat ovat VRP:n laajennuksia ja VRP ei sinänsä sisällä kapasiteettirajoitusta, ellei toisin mainita. Lisäämällä rajoitteet (2.11), (2.13) ja (2.15) saadaan tutkittava ongelma kapasiteetti- luonteiseksi.

2.1.2 OVRP (Avoimet reitit)

OVRP:n ainoa eroavaisuus VRP:hen verrattuna on se, että Hamiltonisten syklien sijaan käytetään Hamiltonisia reittejä. Hamiltonisessa syklissä aloitetaan ja lopetetaan samassa pisteessä, kun taas Hamiltonisessa reitissä aloitetaan pisteestäAja lopetetaan pisteessä B. Toisin sanoen tämä tarkoittaa sitä, että OVRP:ssä ajoneuvot eivät palaa takaisin sinne, mistä ne ovat aloittaneet, eli varastoon. [23]

Kustannukset saadaan laskettua samalla tavalla kuin VRP:ssä, mutta kohdistus paluu- matkasta varastoon on poistettava. Kustannukset saadaan siis seuraavasti:

Minimoiz =

n

∑︂

i=0 n

∑︂

j=0

c_ijx_ij, (2.16)

n

∑︂

i,j∈S

xij ≤ |S| −1, S⊆V \ {v0} (2.17)

n

∑︂

i=0

xij =

n

∑︂

i=0

xji =

⎧

⎪⎪

⎪⎨

⎪⎪

⎪⎩

m, j = 0 1, j = 1, ..., n 0, i= 0

(2.18)

x_ij ∈ {0,1}, i= 0, ..., n; j = 0, ..., n (2.19)

Muutos matemaattisessa määritelmässä ilmenee rajoitteessa (2.18). Sillä varmistetaan, että kohdistuksia, joissa ajoneuvojen kohteina on varasto, ei ole. Kuva 2.3 esittää, miten VRP:n avoimuus saattaa vaikuttaa sen ratkaisun luonteeseen.

(23)

Kuva 2.3. Eräs ratkaisu OVRP:lle. Hamiltonisten syklien sijaan käytetään Hamiltonisia reittejä. Koska ajoneuvojen ei tarvitse palata varastoon, lyhimmät reitit usein saadaan suunnittelemalla reitit varastosta pois päin ulottuvista murtoviivoista.

Taulukko 2.2.OVRP:n kustannusmatriisin rakenne. Matriisi poikkeaa VRP:n kustannus- matriisista siten, että matkat asiakkailta varastoon ovat ilmaisia.

0 1 2 · · · n 0 0 c₀₁ c₀₂ · · · c_0n 1 0 0 c₁₂ · · · c_1n 2 0 c21 0 · · · c2n

... ... ... ... . . . ... n 0 c_n1 c_n2 · · · 0

Vaihtoehtoisesti OVRP:tä voidaan ajatella samalla tavalla kuin VRP:tä matemaattisella määritelmällä. Tämän muokkaamisen sijaan muokataan itse kustannusmatriisia(c_ij)sillä tavalla, että matkat varastoon ovat välittömiä ja ilmaisia. [4] Taulukko 2.2 esittää kyseistä muutosta kustannusmatriisissa(c_ij).

Tilanteesta riippuen tärkeämpi tavoite on matkakustannusten sijaan käytettävien ajoneuvojen minimointi. Yleensä oletetaan, että ajoneuvojen lukumäärä vaikuttaa kustannuksiin merkittävästi enemmän kuin matkakustannukset. [23] Tätä yksityiskohtaa selitetään enemmän Luvussa 2.1.6.

(24)

2.1.3 VRPP (Vaihtoehtoiset asiakkaat)

VRP:ssä jokaista asiakasta on palveltava täsmälleen kerran. Tämän säännön myötä on suunniteltava reitit, joilla minimoidaan kokonaiskustannus muiden rajoitteiden ohella. Ky- seistä sääntöä ei ole VRPP:ssä, jossa kaikkia asiakkaita ei tarvitse palvella. Kustannus- ten käsittelyä varten asiakkaille määritetään tuotot heidän palvelemisesta. Asiakkaiden tuottojen vuoksi tavoitteena on minimoinnin sijaan maksimointi. [5]

VRPP jakautuu erilaisiin optimointiongelmiin, joita on tutkittu sellaisinaan. Tässä käsitel- lään seuraavia tunnettuja optimointiongelmia:

• Ryhmäsuunnistusongelmassa (TOP, Team Orienteering Problem) ajoneuvolaivas- to palvelee tiettyä asiakasjoukkoa. Jokaisella asiakkaalla on oma tuottonsa. Tavoit- teena on löytää sellainen asiakasosajoukko, jonka jäseniä tulisi palvella, jotta ko- konaistuotto on maksimoitu. Jokaiselle ajoneuvon reitille asetetaan yhteinen maksimiaika, johon mennessä ajoneuvojen on oltava varastossa. TOP perustuu suun- nistusongelmaan (Orienteering Problem), jossa ajoneuvolaivaston sijaan käytetään vain yhtä ajoneuvoa. [24]

• Kapasitoituneessa ryhmäsuunnistusongelmassa (CTOP, Capacitated TOP) ajoneuvoilla on yhtä suuri kapasiteettiQ ja jokaisella asiakkaalla on oma kysyntä, kuten CVRP:ssä. Se on muuten identtinen TOP:n kanssa. [25]

• Kapasitoituneessa tuottoisassa matkaongelmassa (CPTP, Capacitated Profitable Tour Problem) tavoitteena on maksimoida tuottojen ja matkakustannusten erotus.

Rajoituksena on vain ajoneuvojen kapasiteetit. [25]

Huomaa, että ongelmissa TOP ja CTOP tuotoista ei vähennetä matkakustannuksia. Ero- tus tapahtuu vain CPTP:ssä. Tässä työssä myös oletetaan, että aloitussolmu on myös lo- petussolmu: alkuperäisissä määritelmissä aloitus- ja lopetussolmut voivat olla toisistaan erillisiä.

Olkoonpi ei-negatiivinen tuotto, joka saadaan palvelemalla asiakastavi,qi asiakkaanvi

kysyntä,γ ∈ {0,1}muuttuja, joka määrää tuottojen vähentämisestä kokonaiskustannuk- sella,T_kaika, joka kuluu ajoneuvonkreitissä (kulkemiseen menevä aika ja reitillä olevien asiakkaiden palveluajat) ja T_max aika, joka määrää, kuinka kauan ajoneuvot voivat olla reiteillään enintään. VRPP määritellään seuraavasti:

Maksimoiz =

n

∑︂

i=0 m

∑︂

k=1

p_iy_ik−γ

n

∑︂

i=0 n

∑︂

j=0

c_ijx_ij, (2.20)

(25)

n

∑︂

i,j∈S

xij ≤ |S| −1, S ⊆V \ {v0} (2.21)

n

∑︂

i=0

q_iy_ik ≤Q, k= 1, ..., m (2.22) T_k ≤T_max, k = 1, ..., m (2.23)

n

∑︂

i=0

xij =

n

∑︂

i=0

xji =

⎧

⎨

⎩

m, j = 0 δ, j = 1, ..., n

(2.24)

m

∑︂

k=1

y_ik =

⎧

⎨

⎩

m, i= 1 δ, i= 2, ..., n

(2.25)

x_ij ∈ {0,1}, i= 1, ..., n; j = 1, ..., n (2.26) y_ik ∈ {0,1}, i= 1, ..., n; k= 1, ..., m (2.27)

δ ∈ {0,1} (2.28)

Rajoitteet (2.22), (2.25) ja (2.27) tekevät VRPP:stä kapasitoidun. Rajoite (2.23) on ajoneuvojen aikarajoite, joka on olennainen ongelmissa TOP ja CTOP. Rajoite (2.28) on li- sätty rajoitteita (2.24) ja (2.25) varten. Nämä perustuvat rajoitteisiin (2.11) ja (2.13) ja niillä varmistetaan, että kaikkia asiakkaita ei tarvitse palvella. AsettamallaT_max =∞jaγ = 1 saadaan CPTP. Kuva 2.4 esittää VRPP:n ratkaisun luonnetta.

VRPP:tä on käsitelty lisäksi siten, että asiakkaat on jaettu kahteen eri joukkoon: ensisijaiset ja toissijaiset asiakkaat. Ensisijaiset asiakkaat ovat ne asiakkaat, joita täytyy palvella poikkeuksitta. Toissijaisia asiakkaita ei tarvitse palvella, mutta näin tekemällä saavutetaan lisätuottoja. Tällaista asiakkaiden jakoa on tutkittu VRPP:ssä, johon liittyy johdonmukai- suuteen perustuvia rajoitteita. [20]

2.1.4 MDVRP (Useampia varastoja)

MDVRP eroaa VRP:stä siten, että varastoja on enemmän kuin yksi, joista ajoneuvot voivat aloittaa reitit [26]. Johdonmukaisuuden vuoksi oletetaan, että jos ajoneuvo aloittaa reitin varastostaA, se myös palaa varastoonAeikä varastoonB.

Sovelletaan suunnatonta graafia

G_{M D} = (V_C ∪V_D, E_{M D}), V_C∩V_D =∅, (2.29)

(26)

Kuva 2.4.Eräs ratkaisu VRPP:lle. Joitakin asiakkaita ei palvella, koska kustannukset niihin matkustamisesta vaikuttavat tuottoihin liikaa.

jossa asiakassolmut ovat joukossa

V_C ={v_c1, v_c2, ..., v_cn} ⊂V (2.30) ja varastosolmut joukossa

V_D ={v_d1, v_d2, ..., v_dn_d} ⊂V, (2.31) joissa n on asiakkaiden lukumäärä ja n_d varastojen lukumäärä. Suunnattoman graafin G_{M D}kaarijoukko

E_{M D} ={(v_i, v_j)|v_i, v_j ∈V_C ∪V_D, i < j} (2.32) yhdistää asiakkaat ja varastot toisiinsa. [26] MDVRP voidaan nyt määritellä seuraavasti:

Minimoiz =

n+n_d

∑︂

i=1 n+n_d

∑︂

j=1

c_ijx_ij, (2.33)

(27)

Kuva 2.5.Eräs ratkaisu MDVRP:lle. Osa ajoneuvoista aloittaa muista varastoista kustannusten minimoimiseksi.

n

∑︂

i,j∈S

x_ij ≤ |S| −1, S ⊆V_C (2.34)

n+nd

∑︂

i=1

xij =

n+nd

∑︂

i=1

xji=

⎧

⎨

⎩

β, j ∈V_D 1, j ∈V_C

(2.35)

x_ij ∈ {0,1}, i= 1, ..., n+n_d; j = 1, ..., n+n_d (2.36)

β ∈ {0,1, ..., m} (2.37)

Asiakas- ja varastosolmut ovat eroteltu toisistaan erillisiin joukkoihinV_C jaV_D, mikä huomioidaan rajoitteissa (2.34) ja (2.35). Lisäksi summien termien lukumäärissä on huomioitu molempien solmujoukkojen suuruudet n ja n_d. Kuva 2.5 näyttää, miten useamman varaston olemassaolo vaikuttaa VRP:n ratkaisuihin.

On mahdollista, että MDVRP:n epäsymmetrisissä tapauksissa tulee esille tilanne, jossa on matkustettava asiakkaastaAasiakkaan B luo, mutta kyseinen matka nopeutuu mer- kittävästi, jos matkan varrella poiketaan varastossa C. Yksinkertaisuuden vuoksi tässä työssä oletetaan, että tällaisen oikotien soveltaminen ei ole mahdollista.

(28)

2.1.5 VRPTW (Aikaikkunat)

VRPTW laajentaa VRP:tä lisäämällä asiakkaille aikaikkunat, joiden sisällä asiakkaita on palveltava. Jokaisella asiakkaalla on tyypillisesti yksi aikaikkuna [e_i, l_i], jossa e_i esittää aikaikkunan alarajaa jal_iaikaikkunan ylärajaa. Jokainen asiakas pitää kirjaa ajoneuvojen saapumisajoista t_i. Jos ajoneuvo saapuu asiakkaan luo myöhässä (eli aikaikkunan ylä- rajan jälkeen), ratkaisun kokonaisuudelle määrätään toimenpide, jolla rohkaistaan aikaikkunan sisällä saapumista. Seuraamukset riippuvat siitä, millaisia aikaikkunoita käytetään.

Yleensä nämä jaetaan kahteen eri tyyppiin: pehmeisiin ja koviin aikaikkunoihin. [21][27]

Pehmeissä aikaikkunoissa ajoneuvo saa tulla asiakkaan luo myöhässä, mutta siitä sa- kotetaan. Sakon suuruuden voi itse määrittää, mutta se yleensä asetetaan suoraan ver- rannolliseksi myöhästymisen tai odotettavan ajan pituuteen. Sakottamista varten määri- tetään sakkokerroin α_i, jonka suuruus kertoo asiakkaan v_i tärkeydestä: mitä suurempi sakkokerroin on, sen tärkeämpi asiakas on. [27]

Kovissa aikaikkunoissa ajoneuvo ei saa tulla myöhässä. Jos näin kuitenkin tapahtuu, ratkaisu on kelvoton. [21] Pehmeät aikaikkunat voidaan muuttaa helposti koviksi aikaikku- noiksi asettamalla sakkokertoimet α_i erittäin suuriksi. Toteutuksen kannalta voi olla te- hokkaampaa soveltaa kovia aikaikkunoita suoraan: ratkaisuja voidaan poistaa laskelmis- ta nopeasti, kun saadaan tietoa siitä, että myöhästymisiä on tapahtunut. [27]

Jos ajoneuvo saapuu aikaikkunan kannalta aikaisin (eli ennen aikaikkunan alarajaa), ratkaisun hylkäämisen tai sakottamisen sijaan se voi odottaa asiakkaan luona palvelun aloi- tusta varten. Tätä varten määritetään odotusaikawi =ei−ti, jossati on saapumisaika asiakaallav_i. [21][27] Toisinaan oletetaan, että kovien aikaikkunoiden kohdalla odotusajat eivät vaikuta kokonaiskustannukseen [21, katso 28, s. 119–159]. Tässä työssä oletetaan, että aikaisin saapuva ajoneuvo odottaa aikaikkunan alarajaan saakka.

VRPTW määritellään matemaattisesti seuraavasti:

Minimoiz =

n

∑︂

i=0 n

∑︂

j=0

c_ijx_ij +

n

∑︂

i=1

α_i·max(0, t_i−l_i), (2.38)

(29)

Kuva 2.6.Eräs ratkaisu VRPTW:lle. Se on suunniteltu siten, että oikealla esitetyt aikaikkunat huomioidaan suurin piirtein.

n

∑︂

i,j∈S

x_ij ≤ |S| −1, S⊆V \ {v₀} (2.39) T_k ≤T_max, k = 1, ..., m (2.40)

n

∑︂

i=0

x_ij =

n

∑︂

i=0

x_ji =

⎧

⎨

⎩

m, j = 0 1, j = 1, ..., n

(2.41)

x_ij ∈ {0,1}, i= 0, ..., n; j = 0, ..., n (2.42)

Minimoitavassa funktiossa (2.38) ajoneuvojen myöhästyminen on huomioitu lineaarisel- la sakkofunktiolla. Asiakkaiden sakkokertoimet α_i on määritettävä erikseen. Saapumis- ajoissatihuomioidaan kulkemisessa kuluva aika, asiakkaiden palvelemiseen kuluva aika ja mahdolliset odotusajat, jos ajoneuvot saapuvat liian aikaisin. Ajoneuvojen saapumisaika varastossa on niiden käyttämä kokonaisaikaT_k, jota tilanteesta riippuen verrataan ajoneuvojen maksimiaikaan T_max. Jos tätä käytetään pehmeänä aikaikkunana, tavoite- funktioon (2.38) lisätään termi∑︁m

k=1α₀·max(0, T_k−T_max)ja rajoite (2.40) poistetaan.

Kuvassa 2.6 esitellään, miten aikaikkunat saattavat vaikuttaa VRP:n ratkaisuun.

(30)

VRPTW pehmeillä aikaikkunoilla sallii joustavuutta reittien suunnittelussa. Koska myö- hästyminen on sallittua, on mahdollista suunnitella reittejä, jotka ovat niin lähellä optimia, että myöhästymisistä kertyneet sakot ovat merkityksettömiä. Tämä kuitenkin tarkoittaa si- tä, että erikseen määritettävät sakkokertoimet vaikuttavat ratkaisuun suoraan. Täten sakkokertoimet on aina määritettävä oikein, jotta optimiratkaisu saavutetaan.

2.1.6 Sovellutukset

VRP on monille aloille tuttu ongelma, etenkin logistiikka-, jakelu- ja kuljetusaloilla. Esi- merkkejä näihin liittyvistä tehtävistä ovat muun muassa pankkikuljetukset, postin jakelu, koulukyyditykset, teollisuusjätteen keräys ja elintarvikkeiden toimitus. [21][27][29] Logis- tiikkajärjestelmien jakeluverkostoja parannetaan lisäämällä jakelupisteitä. Tällöin jakelu- verkosta tulee kompleksisempi, minkä vuoksi kyky ratkaista laajempia VRP-tyyppisiä ongelmia on nykyajan yrityksille tärkeää. Ajoneuvoihin liittyviä kustannuksia vähentämällä kilpailukykenevyys paranee markkinoilla. [2]

Aikaikkunoiden avulla asiakkaat voidaan palvella sopivaan aikaan rakentamalla niihin perustuva aikataulu, jossa asiakkaat tietävät arvion siitä, milloin tilauksiin liittyvät ajoneuvot saapuvat toimittamaan tai hakemaan tavaraa. Tällöin asiakkaiden sekä kuljettajien ei tarvitse huolehtia mahdollisista myöhästymisistä tai päällekkäisyyksistä muiden kuljetusten kanssa, jos tavaroiden lastauspisteitä on rajoitetusti.

Joillakin yrityksillä on tarve suorittaa kuljetuksia, mutta niillä ei ole omia ajoneuvoja tai nämä eivät riitä. Tällöin ne tekevät sopimuksia muiden logistiikkayhtiöiden kanssa. Nämä tarjoavat ajoneuvoja, joilla kuljetukset tehdään. Sopimuksen tekijän näkökulmasta heidän tarvitsee huomioida vain ne kustannukset, jotka kertyvät varaston ja viimeisen asiakkaan välillä. Täten syntynyt VRP on luonteeltaan avoin. [30] Ajoneuvon vuokraamista pidetään kalliimpana kuin säästettävissä olevat matkakustannukset, minkä vuoksi alustavana tavoitteena on minimoitava ajoneuvojen lukumäärä [23]. Ajoneuvolaivaston vuokraamisen yhteydessä ei tarvitse huolehtia ajoneuvojen ylläpitokustannuksista, vakuutuksista ja ve- roista [30]. Kun ajoneuvoja on käytössä suurin lukumäärin, on yleisempää, että käytössä olevia varastoja on enemmän kuin yksi, mikä tekee VRP:stä monimutkaisemman [31].

Säännöllisten, sopimusten mukaisten asiakkaiden lisäksi on mahdollista käsitellä yksit- täisiä, vaihtoehtoisia asiakkaita. Pakollisia asiakkaita palvellaan johdonmukaisesti pitkäl- lä aikavälillä, ja jos ajoneuvoihin liittyvissä rajoitteissa on vielä liikkumavaraa, näistä on mahdollista saada lisätuottoja käyttämällä ne vaihtoehtoisten asiakkaiden palvelemiseen.

[20] Nykyään kuljetuspyyntöjä julkaistaan internetissä. Yritykset, jotka erikoistuvat logis- tiikkaan, kuljetuksiin tai toimituksiin, voivat poimia esitettyjä pyyntöjä ja tarjota palveluitaan vastaaville asiakkaille. Yritykset valitsevat tästä asiakasjoukosta ne, jotka ovat niille käte- vimpiä pakollisia asiakkaita ajatellen. [24] Nämä tunnetaan pistelasteina (Spot Load), ja nämä tekevät VRP:stä VRPP:n [25].

(31)

Taulukko 2.3. Muunnelmia binääriluvuista reaalilukuihin, joita GA:ssa voidaan soveltaa optimointiongelman ratkaisuparametrien koodaamista varten. [6, s. 122]

00–11 000–111 0000–0111 1000–1111

Binääri Reaali Binääri Reaali Binääri Reaali Binääri Reaali 00 0.000 000 0.000 0000 0.000 1000 0.533 01 0.333 001 0.143 0001 0.067 1001 0.600 10 0.667 010 0.286 0010 0.133 1010 0.667 11 1.000 011 0.429 0011 0.200 1011 0.733

– – 100 0.571 0100 0.267 1100 0.800

– – 101 0.714 0101 0.333 1101 0.867

– – 110 0.857 0110 0.400 1110 0.933

– – 111 1.000 0111 0.467 1111 1.000

Jotkut rahtaajat huutokauppaavat kanta-asiakkuuksia useiden kuljetusyritysten kanssa.

Näin saaduissa pitkäaikaisissa sopimuksissa kuljetusyritykset kärsivät, koska ajoneuvojen täyttä kapasiteettia ei voida aina hyödyntää. Tämän vuoksi pistelastien haku on usein olennaista. Pistelastit antavat kuljetusyrityksille tilaisuuden hyödyntää ajoneuvojen täyt- tä kapasiteettia, jolloin vältytään tyhjiltä tuotoilta. Hyvillä pistelasteilla ajoneuvojen kapasiteetit eivät ylity ja reitit eivät poikkea tavallisista reiteistä liikaa. Muissa pistelasteissa saatu tuotto ei korvaa lisäkustannusta, joka kertyy asiakkaan palvelemisesta. Tämä on arvioitava suunnitteluvaiheessa. [25]

2.2 Geneettinen algoritmi

GA on metaheuristinen ja evolutionäärinen optimointialgoritmi, jonka ideana on mallintaa luonnon evoluutiota soveltamalla geneettistä perintää Darwinin teorian mukaisesti. Se ra- kentaa ja ylläpitää kokeellisista ratkaisuista koostuvaa populaatiota useiden sukupolvien ajan. John Holland on esittänyt GA:n ensimmäistä kertaa 1960-luvulla. [1, katso 32]

Populaatiossa olevat ratkaisut esitetään binäärikoodatuilla merkkijonoilla, joita kutsutaan kromosomeiksi. Nämä koostuvat alleeleista, jotka ovat binääriarvoja 0 tai 1. Tämän vuoksi GA:n suunnitteluavaruus tehdään diskreetiksi siten, että arvot, joita muuttujat voivat saada, ovat luvun 2 potensseja, eli 2ⁿ, jossa n ∈ N. Ratkaisuun liittyvät muuttujat voidaan tällä tavalla esittää binäärimuodossa toisiinsa liitettyinä. Kokonaislukuina muuttujia ovat esimerkiksi 00 = 0,01 = 1,10 = 2 ja 11 = 4. Binääriarvoja voidaan esittää re- aalilukuina, joista esitellään esimerkkejä Taulukossa 2.3. Eräs ratkaisu eräälle ongelmalle on esimerkiksi101000110110101, joka koostuu neljästä muuttujasta, jotka ovat liitetty toisiinsa sekventiaalisesti:1010,0011,011ja0101. Genetiikassa nämä tunnetaan geno- tyyppeinä ja näiden ilmentymät (eli ratkaisujen muuttujat, jotka ovat Taulukon 2.3 mukaan vastaavasti0.667,0.200,0.429ja0.333) ovat fenotyyppejä. [6, s. 121]

(32)

Klassisessa GA:ssa ratkaisut esitetään tietyn mittaisina binäärisinä merkkijonoina. Monis- sa ongelmissa tällainen esitysmuoto tuottaa usein sellaisia arvoja, jotka ovat kiinnostavan kohdealueen ulkopuolella. Tästä seuraavien karkeiden epätarkkuuksien vuoksi suositel- laan todellisten koodauksien soveltamista. [33]

GA etenee yleisesti seuraavin askelin, joita esitellään Algoritmissa 2.1 ohjelmallisessa muodossa [6, s. 121–122]:

1. (Alustusvaihe) Luodaan muuttujann_p ∈ N suuruinen populaatio, joka koostuu yk- silöistäx⁽¹⁾₁ , ...,x⁽¹⁾np diskretisoidussa suunnitteluavaruudessa.

2. (Arviointivaihe) Lasketaan jokaiselle yksilölle objektiivinen kuntoarvo (fitness-arvo), joka kertoo yksilön sopivuudesta ratkaisuna optimointiongelmaan. Erilaisilla opti- mointiongelmilla on erilaiset fitness-funktiot, jotka yleensä liittyvät kustannuksiin.

3. Toistetaan sukupolvessag ∈ Naskeleita 4–6 niin kauan, kunnes koko populaatio on generoitu (siis yksilötx^(g+1)₁ , ...,x^(g+1)np ). Näillä askelilla luodaan kaksi jälkeläistä.

4. (Valintavaihe) Kaksi yksilöä valitaan toimimaan vanhempina.

5. (Risteytysvaihe) Valituilla yksilöillä suoritetaan risteytysoperaatio todennäköisyydel- läp_c, josta syntyy kaksi jälkeläistä. Jos risteytystä ei tapahdu, jälkeläiset ovat ident- tisiä kopioita vanhemmistaan. Risteytyksen todennäköisyys on yleensä hyvin suuri, esimerkiksip_c≈0.90.

6. (Mutaatiovaihe) Risteytyksestä syntyneille jälkeläisille suoritetaan mutaatio toden- näköisyydellä p_m. Tämä on yleensä alhainen, esimerkiksip_m ≈ 0.01, koska mutaatio suoritetaan jälkeläisten kromosomien jokaiselle alleelille.

7. Uudesti luotu populaatio korvaa edellisen populaation ja arviointivaihe tehdään uu- delleen. Josnp on pariton, yksi valitaan satunnaisesti poistettavaksi.

8. (Lopetusvaihe) Askelia 2–7 toistetaan, kunnes algoritmia varten ennalta asetetut lopetuskriteerit täyttyvät.

Metaheuristisilla algoritmeilla on 3 tyypillistä ongelmaa, jotka täytyy ratkaista ennen kuin niitä voidaan tehokkaasti soveltaa optimointiongelmissa. Ne

1. jumittuvat lokaaliin optimiin, 2. rajoittuvat tiettyyn sykliin ja

3. eivät pysty pakenemaan tietystä hakualueesta. [2]

Ongelman 1 GA ratkaisee mutaatiovaiheellaan. Kun populaatio pysyy monipuolisena mu- taatioiden myötä, ratkaisuhaku voi paeta lokaaleista optimeista. [34] Ongelmat 2 ja 3 on ratkaistu GA:n kanssa automaattisesti, koska tämä on luonteeltaan stokastinen: syklit muuttuvat jatkuvasti, koska risteytys- ja mutaatiovaiheiden operaattorit perustuvat satun- naisuuteen – ja GA:lla ei ole minkäänlaisia sääntöjä, joka ohjaisi sen hakusuuntaa. Vain satunnaisuus ohjaa GA:ta. [2]

(33)

1 def g e n e t i c _ a l g o r i t h m ( ) :

2 GENERATION_COUNT = 100

3 POPULATION_SIZE = 100

4

5 p o p u l a t i o n = i n i t i a l i z e _ p o p u l a t i o n( POPULATION_SIZE ) 6 evaluate( p o p u l a t i o n )

7 l e a d i n g _ i n d i v i d u a l = b e s t _ i n d i v i d u a l( p o p u l a t i o n ) 8

9 f o r n i n range(GENERATION_COUNT ) : 10 n e w _ p o p u l a t i o n = [ ]

11

12 while len( n e w _ p o p u l a t i o n ) < POPULATION_SIZE : 13 p a r e n t s = sele ct_pare nts( p o p u l a t i o n )

14 o f f s p r i n g 1 , o f f s p r i n g 2 = crossover( p a r e n t s ) 15 mutate( o f f s p r i n g 1 )

16 mutate( o f f s p r i n g 2 )

17 n e w _ p o p u l a t i o n . append ( o f f s p r i n g 1 ) 18 n e w _ p o p u l a t i o n . append ( o f f s p r i n g 2 ) 19

20 evaluate( n e w _ p o p u l a t i o n )

21 c o m p e t i n g _ i n d i v i d u a l = b e s t _ i n d i v i d u a l( n e w _ p o p u l a t i o n ) 22 i f c o m p e t i n g _ i n d i v i d u a l > l e a d i n g _ i n d i v i d u a l :

23 l e a d i n g _ i n d i v i d u a l = c o m p e t i n g _ i n d i v i d u a l 24

25 p o p u l a t i o n = n e w _ p o p u l a t i o n 26

27 r e t u r n l e a d i n g _ i n d i v i d u a l

Ohjelma 2.1.GA:n toteutus ohjelmallisesti.

GA:n vaiheita voidaan täydentää ja muokata monilla eri tavoilla sen parantamista varten.

Se etsii ratkaisuja globaalisti (tutkimalla koko populaatiota), kun taas toinen algoritmi – (meta)heuristinen tai ei – etsii lokaalisti (tutkimalla populaatiossa olevia kromosomeja yksitellen) [2]. Seuraavaksi käsitellään jokainen GA:n vaihe yksityiskohtaisemmin, jotta saadaan parempi kuva GA:n toiminnasta. Luvuissa 2.2.4 ja 2.2.5 on hyvä pitää mielessä, että reaalikoodattujen kromosomien tapauksissa oletetaan, että risteytys- ja mutaatio- operaattorit kohdistuvat TSP-tyyppisille optimointiongelmille.

2.2.1 Alustus

Alustusvaiheessa luodaan populaatio, joka koostuu yksilöistä. Nämä esittävät ratkaisuja optimointiongelmalle. Populaatio alustetaan yleensä satunnaisesti. [34] Populaation kook- si on suositeltu olevan välillä[30,200][1]. Menetelmä, jolla populaatio alustetaan, on kuitenkin muokattavissa. Soveltamalla erikoistuneita algoritmeja populaation alustuksessa on mahdollista, että hyviä ratkaisuja löydetään aikaisemmin [35]. Tässä luvussa esitel-