Luultavasti olen jostain kohtaa ajanut läpi tai lentänyt yli jokaisen Varsinais-Suomen kunnan, mutta paremman kuvan saisi kun kävisi kurkkaamassa miltä kylillä näyttää.
Varsinais-Suomessa on tällä hetkellä vielä 28 kuntaa, joten matkaa tulee vähintään melko paljon. Kuntien väliset etäisyydet vaihtelevat, mutta jos arvaa keskimääräiseksi välimatkaksi 30 km niin matkaa olisi noin 900 km. Matka olisi ajettavissa yhdessä päivässä jos oikein yrittää.
Todellinen matka kuitenkin riippuu siitä missä järjestyksessä kunnat kiertää. Mahdollisimman lyhyen reitin löytäminen on kuitenkin haastavaa koska mahdollisia reittejä on paljon.
Kyseessä on niin sanottu kauppamatkustajan ongelma, jonka matemaattista ratkaisua on pohdittu enemmänkin. Määränpäiden lukumäärän kasvaessa ongelma muodostuu nopeasti työlääksi ratkaista jopa tietokoneella.
Asiaa pohtiessani pieni nörtti sisälläni heräsi ja päätin kokeilla yksinkertaista algoritmiä. Kirjoitin taulukkoon google mapsin antamia lyhimpiä etäisyyksiä kuntien välillä ja laitoin koneen valitsemaan arvalla seuraavan kohteen. Annoin koneen laskea jonkin aikaa, Kuva 1 näyttää minkä pituisia matkoja löytyi.
Lyhin matka oli 809 km ja pisin 1619 km. Vieläkin pidempiä matkoja olisi varmasti tullut, mutta en jaksanut kirjoittaa taulukkoon kaikkia mahdollisia reittejä. Ajan säästämiseksi laitoin vain etäisyyden muutamaan lähimpään kuntaan.
Kuva 1. Noin 600 000 yritystä joista 81786 johti takaisin kotiin. Ryhmästä “Uniikit” on poistettu useampaan kertaan esiintyneet matkan pituudet
Taulukko 1.
Min. 1st Qu. Median Mean 3rd Qu. Max. Ryhmä
809 1143 1207 1206 1270 1619 Kaikki
809 1119 1215 1211 1304 1619 Uniikit
Koska varsinkin kaikista piirretty histogrammi näyttä kovasti normaalijakautuneelta niin plottasin vielä QQplotin normalli jakaumaa vasten (R-QQnorm). Lineaarinen transformaatio tarvitaan ennen kuin kaikkien jakauma on normaali. Pelkästään uniikit matkan pituudet hyväksyvä jakauma poikkeaa normaalista enemmän. En osaa muuta sanoa kuin että jotain tälläistä voisi odottaa kun kohtuu satunnaisia pituuksia arpoo monta peräkkäin ja laskee summan.
Alla laskennassa käytetty R-koodi:
[code language=”css”]
## laske kauppamatkustajan ongelmaa kiertueelle
TSP.distance <- function(yri=10, method = "mininum", verbosity=3){
# method = miten valitaan seuraava paikka
# verbosity = miten paljon kerrotaan toiminnasta
load("kkk.Rdata")
kotiin=kkk[kkk$variable=="Piikkiö", c("X", "variable", "value")]
K=kkk
D.k=numeric()
m.k=list()
m=0
for (j in 1:yri){
kkk=K
D=0
vajaa=F
Uk="Piikkiö"
Kaikki.K=numeric()
Kaikki.K[1]=Uk
for (i in 1:28){
k=kkk[kkk$variable==Uk, "X"]
if (length(k)==0){
vajaa=T
break
}
k=sample(k, 1)
Uk2=as.character(kkk[kkk$variable==Uk &
kkk$X==k,"X"])[1]
D=D+kkk[kkk$variable==Uk & kkk$X==k,"value"][1]
kkk=kkk[!(kkk$X==Uk | kkk$variable==Uk),]
Uk=Uk2
Kaikki.K[i+1]=Uk
}
if (!vajaa){
print(j)
m=m+1
D=D+kotiin[kotiin$X==Uk, "value"]
Kaikki.K[i+2]="Piikkiö"
print(D)
D.k[[m]]=D
m.k[[m]]=Kaikki.K
}
}
Reissut=list(Pituudet=D.k, Kunnat=m.k )
}
TSP.Lyhin <- function(R){
P=10000
for (i in 1:length(R$Pituudet)){
if (R$Pituudet[[i]]<P){
P=R$Pituudet[[i]]
K=R$Kunnat[[i]]
}
}
list(P, K)
}
[/code]
