Kuntakierros

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.

HistogrammiKuva 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.

Matkat-QQnorm

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]

Published by

Niko Porjo

Joys: comedy, cycling and spotting argumentation errors in live speech. Physicist and thinker, a little bit of an amateur philosopher. I like to build things but when they work that’s enough, no polishing.

Translate »