Kjøretøyruting

Kjøretøyruting er et område innen logistikk og operasjonsanalyse som omhandler planlegging og optimering av kjøretøyruter for en flåte som leverer varer eller tjenester fra ett eller flere depoter til et sett kunder. Hovedmålet er å minimere totale kostnader, ofte målt som total kjøretid eller avstand, samtidig som begrensninger som kjøretøykapasitet og leveringsfrister overholdes. Modellene representerer ofte et nettverk med depoter og kunder som noder, og kanter som kostnader mellom plasseringene.

Problemformulering og karakteristikk

Kjøretøyruting innebærer å tildele kunder til kjøretøy og bestemme rekkefølgen på kundebesøk slik at ruter er gyldige og totale kostnader minimaliseres. Vanlige begrensninger inkluderer kapasitet per kjøretøy, tidsvindu for levering, serviceperioder og antall tilgjengelige kjøretøy. VRP-stillinger er NP-hard, og problemene kreses ofte ned til praktiske størrelser gjennom forenklinger eller antagelser.

Varianter

- Capacitated VRP (CVRP)

- VRP with Time Windows (VRPTW)

- VRP with pickups and deliveries

- Multi-depot VRP

- Open VRP

- Dynamic og stochastic VRP

Metoder og tilnærminger

Løsninger kan være eksakte eller heuristiske. Eksakte metoder inkluderer MILP-formuleringer og branch-and-price for små til mellomstore oppgaver. Heuristikker og metaheuristikker som Clarke–W Wright-sparing, sweep-algoritmer, tabu search, genetiske algoritmer, ant colony optimization og hybride metoder brukes for større og mer komplekse problemer.

Anvendelser og betydning

Kjøretøyruting er sentralt i logistikk, varelevering, post- og renovasjonssektorer, samt tjenester som tar i bruk feltarbeidere. Viktige data inkluderer kundeetterspørsel, tidsvindu, service-/kjøretider, kapasitet og nettverkskostnader. Se også Vehicle Routing Problem og logistikk.