Ruttplanering med AI

Bakgrund

Östgötatrafiken ansvarar dagligen för ca 5500 beställningsresor av bland annat färdtjänst, sjukresor och skolskjuts i hela Östergötland. För att genomföra alla dessa resor på ett effektivt sätt, med hänsyn till resenärernas behov och rättigheter, krävs det stöd i form av administration av bokningar och planering av rutter. Därför vill Östgötatrafiken undersöka och testa hur nya tekniker inom AI kan användas för att förenkla och förbättra arbetet med ruttplanering. Attentec har tittat närmare på hur vi kan skapa kostnadseffektiva ruttplaner.

Lösning

Attentec formulerade och modellerade problemet som ett ‘Vehicle Routing Problem with Time Windows’ (VRPTW) för att dra nytta av moderna planerare inom AI-fältet automatisk planering.

Tillsammans med Östgötatrafiken beskrevs en domän som definierar regler och begränsningar som en slutgitlig plan måste ta hänsyn till. Lösningens använder en extern geografi för att uppskatta avstånd och restid mellan platser som en planerare sedan använder för att, med hjälp av optimeringsmjukvara, iterativt söka efter lösningar (planer) som minimerar den totala kostnaden med avseende på uppskattat avstånd och tid.

Dessa resor bokas ofta i god tid, men det sker ändringar i sista minuten t.ex. avbokningar beroende på sjukdom. Med hjälp av AI kan man ta hänsyn till sena förändringar och också öka möjligheten till samåkning vilket sparar både tid och körsträcka. – Anders Weiland, kundansvarig på Attentec.

Teknik

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

Lärdomar

Automatisk planering är ett pågående forskningsområde inom artificiell intelligens (AI), med kopplingar mot schemaläggning och optimering. I grund och botten handlar automatisk planering om att hitta en plan som uppfyller ett måltillstånd, givet ett nuvarande tillstånd. Tanken är att beskriva hur världen ser ut, hur vi vill att den skall se ut samt vad som går att göra i världen, och låta en planerare söka reda på en sekvens av lämpliga handlingar med hjälp av olika, smarta söktekniker. Det ger oss en rad positiva fördelar i fallet med automatisk ruttplanering såsom att det till exempel är enkelt att planera om, det finns möjlighet till simuleringar och att alla fordon och resenärer tas hänsyn till. Från förstudien tas flera lärdomar, såsom att samplanering är ett fantastiskt sätt att minska kostnader och att det är viktigt att hålla nere antalet “states” för att hitta en plan inom rimlig tid. Vidare är fältet i ständig utveckling och det finns redan nu flera andra planerare att testa och utvärdera.

Vill du veta hur man skapar affärsnytta med AI-lösningar? Läs denna artikel.