Ruteplanlegging med AI

Bakgrunn

Östgötatrafiken har daglig ansvar for rundt 5500 bestillingsturer på blant annet reisetjenester, medisinske turer og skoletransport i hele Östergötland. For å gjennomføre alle disse reisene på en effektiv måte, med tanke på reisendes behov og rettigheter, er det nødvendig med støtte i form av administrasjon av bestillinger og planlegging av ruter. Derfor ønsket Östgötatrafiken å undersøke og teste hvordan ny teknologi innen AI kan brukes til å forenkle og forbedre arbeidet med ruteplanlegging.

Attentec har sett nærmere på hvordan vi kan lage kostnadseffektive ruteplaner.

Løsning

Attentec formulerte og modellerte problemet som et ‘Vehicle Routing Problem with Time Windows’ (VRPTW) for å dra nytte av moderne planleggere innen AI-området automatisk planlegging.

Sammen med Östgötatrafiken ble det beskrevet et domene som definerer regler og begrensninger som en endelig plan må ta hensyn til. Løsningen bruker en ekstern kartleverandør for å estimere avstander og reisetid mellom steder. Som en planlegger deretter bruker, ved hjelp av optimaliseringsprogramvare, til iterativt å søke etter løsninger. (planer) Dette minimerer de totale kostnadene når det gjelder estimert avstand og tid.

Disse turene bestilles ofte i god tid, men det er endringer i siste øyeblikk f.eks. avbestillinger på grunn av sykdom. Ved hjelp av AI kan du ta hensyn til sene endringer og også øke muligheten for samkjøring, noe som sparer både tid og kjørelengde. – Anders Weiland, kundeansvarig i Attentec.

Teknologi

Python, PDDL, OPTIC med CPLEX och CLP, Open Source Routing Machine (OSRM)