Ruteoptimalisering forklart: hvorfor rekkefølgen på stoppene faktisk betyr noe

Det virker enkelt: du har 20 stopp, du kjører dem i en fornuftig rekkefølge. Men «fornuftig» er ikke det samme som «best» — og forskjellen kan utgjøre en time eller mer kjøring per dag.

Hvorfor rekkefølgen faktisk betyr noe

Problemet med å finne den korteste ruten gjennom et sett stopp er et av de mest kjente problemene i optimalisering — kjent som handelsreisendes problem (traveling salesman problem). Med 20 stopp finnes det over 60 kvadrillioner mulige rekkefølger. Selv en datamaskin som prøvde en milliard ruter i sekundet, ville brukt lengre tid enn universets alder på å sjekke dem alle.

Derfor bruker ingen — verken Framme eller store logistikkselskaper — brute force. Løsningen er heuristikker: metoder som finner en svært god rute raskt, i stedet for å garantere den matematisk perfekte.

Nearest neighbor: den raske starten

«Nærmeste nabo» er den enkleste heuristikken som finnes: stå på ett stopp, kjør til det nærmeste ubesøkte stoppet, gjenta. Rask å regne ut, men grådig — den tar alltid det som er nærmest akkurat nå, uten å tenke på hva det gjør med resten av ruten. Resultatet er ofte en rute med en eller flere unødvendige omveier mot slutten, der de siste stoppene ligger spredt fordi de nærmeste alternativene ble «brukt opp» tidlig.

2-opt: forbedringen som retter opp omveiene

Her kommer 2-opt inn. Metoden ser etter par av strekninger i ruten som krysser hverandre eller ligger unødvendig langt fra hverandre, og bytter om rekkefølgen mellom dem hvis det gir en kortere totalrute. Framme gjentar dette til ingen flere forbedringer er å finne innenfor et satt tidsbudsjett — nok til å luke ut de fleste åpenbare omveiene, uten at beregningen tar unødvendig lang tid selv med mange stopp.

Kombinasjonen — nearest neighbor for en rask start, 2-opt for å polere den — er en velprøvd tilnærming som gir gode ruter uten å kreve tung matematikk-maskineri i bakgrunnen.

Tidsvinduer som myke føringer, ikke harde stopp

En kunde med leveringsvindu 14:00–15:00 kompliserer bildet: den korteste ruten er ubrukelig hvis den bryter et tidsvindu. Framme legger derfor inn en straff i kostfunksjonen for hvert brutt tidsvindu, slik at optimaliseringen veier kortest mulig kjøretid opp mot færrest mulige brutte vinduer — i stedet for å behandle tidsvinduer som en hard regel som kan gjøre hele ruten uløselig hvis to kunder ber om overlappende tider.

Hvorfor dette ikke krever en betalt API

Ruteoptimalisering selges ofte som en dyr, ekstern tjeneste. Nearest neighbor og 2-opt er derimot velkjente, åpne metoder som kjører helt fint lokalt — Framme trenger ingen ekstern optimaliserings-API for dette, kun egen kjøretidsberegning (heuristikk, eller ekte kjøretider via en selvhostet OSRM-tjeneste). Beregningen kjører i en egen bakgrunnsprosess, slik at grensesnittet ikke fryser selv når en rute har over 100 stopp.

Vil du se før/etter-effekten på din egen rute? Last opp dagens adresser og se optimaliseringen i praksis, eller kom i gang med en gang.