Lyhimmän reitin laskentaa monen osoitteen välille

[H. Jormalainen]

Olisi tarve jollekin ohjelmalle jolla saisi laskettua noin 40 osoitteen reitin lyhintä reittiä läpi käyden. Järjestyksellä ei siis väliä.

Onko kokemuksia ja/tai ehdotuksia?

Mapinfo on nähty ja koettu liian monimutkaiseksi koska navigaattorit on erikseen eikä muuta ohjelmalla tarvitsisi tehdä.

Tuskin näitä missään webin ilmaispalvelussa saa tehtyä? Käyttö olisi melko harvoin...

[EsaT]

Genimapin GT reittikartta ainakin osaa. Ainoastaan alku ja loppupiste on muuttumattomat.

[Babar]

Microsoft AutoRoute ohjelma. Sillä onnistuu. Pätevä ohjelma muutenkin. Tosin maksaa jotain euroja ellei lainaa jostain...

[ahu]

joulupukin reittiäkö laskekeslelet vai? Eniron reittilaskurilla ainakin saa monta eri kohdetta, mutta ei tietoa millaiseen järjestykseen se ne laittaa.

[H. Jormalainen]

Kiitos vastauksista!

joulupukin reittiäkö laskekeslelet vai?

:D

Kaverin puolesta tätä kyselen. Sen pitäisi käydä tietyt osoitteet läpi jokseenkin järkevästi.

Tähän mennessä on taidettu neuloja laittaa kartalle ja vaan hahmottaa sitä järkevintä reittiä.

[justus]

Toimisko google maps, siinä kun laittaa alku- ja loppupisteen ja vetelee luotua reittiä sopiviin paikkoihin.

Menin sitten koettamaan ja huomasin että sinnehän pystyy lisäämään useita reittipisteitä. URL

[H. Jormalainen]

Tossakin pitäisi itse järkeillä ne optimijärjestykseen...

E: Tosta Genimapista ei valmistaja verkkosivuillaan mainitse että osaisi järjestää reittipisteet optimijärjestykseen? Onkos joku ny väärässä?

[Miikael]

Kyllä toi Genimappi osaa.

[Juhis-84]

Genimappia en tunne, mutta uskaltaisin väittää että 40 osoitteen optimaalisinta järjestystä ei pysty laskemaan. Antaa varmaankin jonkinlaisen tuloksen, mutta ei kaikkein 'parasta'.

Kannattaa tutustua ns. "kauppamatkustajan ongelmaan".

[H. Jormalainen]

Juu, ilmaisin itseni siinä mielessä väärin että ei tässä supertietokoneen laskentaa ole tarkoitus ostaa :)

Sellanen suhteellisen fiksu reitti olisi haussa.

Eikö tuossa kauppamatkustajan ongelmassa kaydä vain kerran pisteessä? Tässä ei haittaa vaikka joutuisi käymään paluumatkalla uudestaan samassa paikassa. Mutta ei se taida paljoa laskentaa keventää...

[Juhis-84]

Tahdoin vain hieman päteä :)

Kauppamatkustajan ongelmassa tosiaankin käydään tasan kerran jokaisessa pisteessä. Eikä taida keventää laskentaa tuo että voidaan käydä samassa pisteessä useamman kerran.

http://keskustelu.plaza.fi/muropaketti/bbs/t489165

Tuolla keskustelivat GT Reittikartta Suomi Plus 2005 -ohjelmasta (tullut myös 2007 versio). En sitten tiedä onko paljonkin optimaalisempi kuin jo ehdotetut ohjelmat.

[chinz]

Eikä taida keventää laskentaa tuo että voidaan käydä samassa pisteessä useamman kerran.

Väittäisin että keventää. En kyllä vannomaan mene. =)

Järkevän tuloksen kuitenkin saa huomattavasti alle 40! laskutoimituksella, kun ei jokaisen pisteen jälkeen tarvitse ottaa kuin muutama lähin vaihtoehto huomioon. Eli kai hyvin suunniteltu softa, ainakin lähes joka tilanteessa, onnistuu sen oikeasti parhaan reitin valitsemaan?

[Juhis-84]

En siltikään usko, että keventää :) Jos kompleksisuus on tasoa n! ja tuohon sallitaan samassa pisteessä useaan kertaan vierailu, kompleksisuus olisi tasoa n! + x.

Ja kyllä, järkeviä tuloksia saa muutenkin kuin tuolla 40! laskutoimituksella. En nyt muista menetelmää, mutta taisi juurikin toimia siten, että menetelmä ottaa huomioon lähimmät pisteet sekä niiden etäisyydet ja sitä kautta laskee parhaimman reitin. Tämä menetelmä ei ole muistaakseni kovinkaan raskas ja tuottaa melko hyvän ratkaisun.

[ramiv]

http://www.hannusales.fi/uusiloisto/Digiroad.htm

Iso Loisto versiossa olevan paikkakokoelman optimointitoiminnon avulla voidaan helposti optimoida jakeluauton reitti. Esimerkiksi reitti joka kiertää 109 Rautakirjan toimipistettä pääkaupunkiseudulla:

Paikkoja 109
Pituus linnuntietä 225 km
reititetty matka 328 km ja ajoaika 06 14'20"

Napsauttamalla kuvaa näet toisen rankemmilla parametreillä lasketun reitin, muutokset ylempään reittiin näkyvät punaisena. Pari pientä muutosta reitissä säästää kaksi prosenttia ajoajassa ja matkassa. Vuoden mittaan niistä kertyy paljon.

Paikkoja 109
Pituus linnuntietä 229 km
reititetty matka 321 km ja ajoaika 06 06'55"