ruteplanleggingsproblemer

Ruteplanleggingsproblemer er en gruppe optimeringsproblemer som søker å finne effektive ruter for ett eller flere kjøretøy som skal betjene en samling oppgaver eller kunder. Hovedmålet er ofte å minimere total distanse, kjøretid eller kostnader, samtidig som krav som kjøretøykapasitet, leveringstidsvinduer og start/sluttpunkter overholdes. Problemene kan være statiske, der oppgavene er fastlagte på forhånd, eller dynamiske, der oppdrag kommer inn underveis og ruter må justeres i sanntid.

Klasseeksempler inkluderer Travelling Salesman Problem (TSP), som handler om å finne kortest mulig rute som besøker hver by én gang og returnerer til utgangspunktet; Vehicle Routing Problem (VRP), som innebærer å dekke mange kunder med et flertall kjøretøy fra ett eller flere depoter; samt varianter som Capacitated VRP (CVRP) og VRP med tidsvinduer (VRPTW). Andre relevante problemer inkluderer Open VRP og Dial-a-Ride Problem (DARP).

Tilnærminger for løsning av ruteplanleggingsproblemer inkluderer eksakte metoder som helttallsprogrammering og grense-og-grense-bryting (branch-and-bound), som gir optimale løsninger for små til mellomstore problemstørrelser. På grunn av problemets NP-hardhet bruker man ofte heuristikker (f.eks. greediness, savings) og metaheuristikker (som genetiske algoritmer, tabu-søk, ant colony) for å finne gode løsninger. Kolonnegenerering og decomposisjonsteknikker brukes også i større VRP-varianter.

Anvendelser finnes i logistikk og distribusjon, kollektivtransport, varelevering, rideservice og nødetatene. Viktige ytelsesmål inkluderer total kjørelengde, total tid, antall kjøretøy, ventetid og forutsigbarhet. Vanskeligheter som usikkerhet i etterspørsel, trafikk og tidsvinduer gjør at robusthet og sanntidsomplanlegging ofte er nødvendig.