Tilbake til søkeresultatene

TRANSPORT-Transport 2025

OPtimal Scheduling for next-generation intelligent TRAnsport systems.

Alternativ tittel: OPtimal Scheduling for next-generation intelligent TRAnsport systems.

Tildelt: kr 9,0 mill.

Ruteplanlegging innebærer å bestemme tider for bevegelse av kjøretøyer i transportsystemer. Det inngår i alle nivåene av planleggingsprosessen: strategisk, for å finne optimale infrastrukturinvesteringer; taktisk, for å etablere rutetabeller; og operasjonell, for å tillate omlegging av ruteplanen i sanntid ved forsinkelser og avvik. Planlegging blir utført av eksperter med lite støtte fra automatiske verktøy. For å implementere slike verktøy trenger en å utvikle optimaliseringsmetoder. Dagens metoder kan kun håndtere små systemer og scenarioer, men likevel er den enorme gevinsten av optimering allerede meget tydelig. Utfordringen er at dagens teknologi og metoder ikke skalerer godt nok. Vi trenger nye modeller og algoritmer for å løse omfattende problemer, slik som togledelse på den norske jernbanen. Vårt mål i OPSTRA var å utvikle banebrytende modeller og løsningsmetoder for planlegging innenfor transport. Disse modellene legger grunnlaget for nye verktøy som kan løse til nå uløselige problemer fra virkelige transportsystemer. I løpet av prosjektets år har vi overgått de opprinnelige målene. Vi har ferdigstilt det grunnleggende matematiske arbeidet, som har blitt publisert i tidsskrifter på nivå 2. I våre undersøkelser har P&C-metoden, et av hovedpunktene i den teoretiske utviklingen, prestert høyere enn etablerte metoder i feltet. Denne grunnleggende modellen ble utviklet for togledelse, og den første vellykkede testingen ble gjennomført på Jærbanen. Resultatene fra testen ble publisert i et ledende tidsskrift i feltet. Med utgangspunkt i dette første arbeidet har vi gått videre i flere retninger. 1. Utvidelse til nye anvendelser. Vi har tilpasset våre modeller til å angripe "hotspot"-problemet fra flygeledelse og planlegging av flytrafikk. Oppgaven er å forsinke utvalgte fly på bakken for å unngå overopphoping av fly i luftrommet. Vi observerte at vi kunne løse problemet inntil 66 ganger så raskt som med etablerte metoder. 2. Utvidelse til mer sammensatte nettverk. Vi har utvidet våre metoder til å omfatte det svært viktige problemet med togledelse på store stasjoner som Oslo S. 3. Kombinatorisk læring. Et stort fremskritt fra år 2 knytter seg til den dynamiske naturen av problemer hvor vi stadig beregner oppdaterte ruteplaner. I dette tilfellet kan vi benytte oss av informasjon fra tidligere beregninger for raskere å finne løsningen på neste problem. Det er egenheter ved P&C-metoden som muliggjør denne prosessen. Vi kaller prosessen "kombinatorisk læring", fordi algoritmen til dels lærer den kombinatoriske strukturen i problemene som løses. Kombinatorisk læring har allerede gitt tydelige resultater på realistiske problemer innen togledelse. Under arbeidet med å samle resultatene fra hovedtemaet for prosjektet har vi kommet over mange relaterte problemer. Disse har ledet til ny forskning. 1. Vår nye P&C-metode presterer over etablerte metoder innenfor vårt målområde, nemlig oppdatering av ruteplaner for tog og fly, men det er flere problemer innen transport hvor det fortsatt er bedre å bruke (videreutviklinger av) tradisjonelle fremgangsmåter. For eksempel innen maritim overvåking. 2. Å oppdage romlige konflikter mellom fartøy er sentralt innen alle automatiserte former for ruteplanlegging. Vi har utviklet en ny tilnærming basert på konfliktdiagrammer for å representere bevegelser og konflikter. 3. Det sentrale elementet i offentlig kommunikasjon, passasjeren, blir ofte oversett i ruteplanlegging. Vi har utviklet en ny tilnærming for ruteplanlegging på T-banesystemer med mål om å minimere ventetid på stasjonene. 4. Fastlåsing er en alvorlig konsekvens av dårlig planlegging i transportsystemer. Disse oppstår når en samling fartøy gjensidig hindrer hverandre i å fortsette langs planlagte ruter. Å løse opp fastlåsinger kan kreve kostbare inngrep, og må derfor unngås, men automatiserte søk etter mulige fastlåsinger er en matematisk utfordrende oppgave. Vi har utviklet effektive tilnærminger til problemet med å oppdage (og å unngå) mulige fastlåsinger: (a) tikk-formuleringen, som er en spesialisert tidsindeksert formulering; (b) en spesialisert Path&Cycle-formulering; og (c) en frittstående, rask løsningsmetode for fastlåsinger mellom to tog. 5. For omfattende nettverk som Oslo S og omegn er det ofte nødvendig å dele problemet opp i mindre deler. Vi har undersøkt en nav-eike-inndeling (hub-and-spoke decomposition), hvor delproblemene er Oslo S og, enkeltvis, linjene som leder til Oslo S. Vi jobber med utprøving av flere metoder for å sette sammen løsningene fra delproblemene. Forskningen som har blitt levert gjennom prosjektet har vært av veldig høy kvalitet. Dette seespå antallet publikasjoner i bredt annerkjente tidsskrifter på høyeste nivå. Mange av algoritmene som har blitt utviklet er nå bygget inn i verktøy for togledelse og for ruteplanlegging på operasjonelt, taktisk og strategisk nivå. Disse verktøyene har blitt uvilklet i samarbeid med Bane NOR.

For research. The basic model studied in the project is the only recent genuine alternative to the classical ones. This opens up for new research directions. With more than 15 scientists active in foreign institutions, the project allowed to build a strong international network and to disseminate the new ideas in the scientific community worldwide. For trade and industry. First, modeling and algorithmic developments carried out in the project are currently being implemented in software tools which will allow a significant reduction of workload for human operators and improvements in the quality of the plans. Better plans will imply greater satisfaction for transport customers and reduced environmental impact. The methodologies can be exported to other transportation modes (maritime transportation, drones, AGV), and to other real-life applications, for instance in the context of industrial production (for sequencing and scheduling processes on machines).

Our objective is to develop ground-breaking mathematical models and solution methods for scheduling problems in transport. They will provide the foundations for new tools capable of tackling yet unsolvable instances arising in real-life systems. The expected impact is remarkable, in terms of reduced costs, congestion and operators workload, improved reliability, punctuality, resilience to disruptions and quality of service. Scheduling consists in timing the movements of vehicles in transport systems. It appears at all level of the planning process: Strategical, to identify optimal infrastructure investments; Tactical, to establish robust timetables ensuring coordination among different modes of transport; Operational, to allow re-planning in real-time to recover from delays and disruptions. Scheduling is performed by experts with little support from automatic tools. To implement such tools one needs to develop optimization methods. Current methods can only tackle small instances, still already showing the tremendous impact of optimization on system performance. The current technology does not scale well. We need new models/algorithms to tackle large scale instances of scheduling problems arising, e.g., in dispatching large networks as the Norwegian railway (as required by Jernbaneverket in a current tender); or in coordinating multiple transport modes in freight corridors (e.g. Kiruna-Narvik-Rotterdam). Our research will be founded on three solid legs: 1. Very recently, our group developed a new, ground-breaking approach to scheduling problems in transport, which differs substantially from previous approaches. 2. We led research activities in international award winning projects on scheduling in railway and aviation, defining the state-of-the-art for these applications 3. We dispose of a large set of real-life instances from different applications: multi-mode transport in freight corridors, infrastructure planning in railway, surface scheduling in aviation.

Publikasjoner hentet fra Cristin

Ingen publikasjoner funnet

Ingen publikasjoner funnet

Budsjettformål:

TRANSPORT-Transport 2025