kjøretøyrutingproblemer

Kjøretøyruting, eller vehicle routing, er ein gren av operasjonell forsking som handterer korleis ein flåte av kjøretøy skal levere varer eller tenester til eit sett kundar frå eit depot, under krav som kapasitet, tidsvindauge og eventuelle restriksjonar. Hovudmålet er å minimalisere samla køyreradie eller kjøretid, ofte samtidig som kostnader, køyringstid og miljøpåverknad blir ta med i vurderinga.

Variantar av problemet inkluderer kapasitetbasert VRP (CVRP), VRP med tidsvindauge (VRPTW), VRP med henting og levering (VRPPD) og dynamiske VRP. Desse problema blir formulerte som blandingseinigsysproblem eller nettverksproblem, og løyst gjennom eine rekke metodar, frå eksakte tilnærmingar.

Metoder som blir brukte omfattar exakte teknikkar som branch-and-bound eller branch-and-cut for mindre oppsett, samt heuristikkar og metaheuristikkar for større problem. Kjende heuristikkar inkluderer Clarke–Wright-sparingsmetoden og Sweep-metoden, medan metaheuristikkar som genetiske algoritmar, tabu-søking, simulated annealing og insektskubeinspirerte teknikkar ofte gir pragmatiske løysingar i komplekse modular. Desse løysingane kan også utgjere MILP-formuleringar som blir løyst med cutting-plane-teknikkar.

Data og krav som vanlegvis er nødvendige inkluderer depotlokasjon, kundar med etterspørsel, kjøretøykapasitet og eventuelle tidsvindu. Dynamisk VRP tek omsyn til sanntidsendringar som trafikk eller nye bestillingar.

Kjøretøyruting har omfattande bruksområde innan logistikk, netthandel, matlevering, avfallshandtering og offentleg transport, og vert rekna som eit sentralt verktøy for å auke effektivitet og redusere miljøpåverknad.