Tilbake til søkeresultatene

TRANSPORT-Transport 2025

Collab II: High-performance transportation optimization through parallel and collaborative methods II

Tildelt: kr 4,0 mill.

Vi utvikler nye, parallelle optimeringsmetoder for koordinering av transport. Derved vil verktøy for transportplanlegging bli mer effektive slik at bedre transportplaner med mindre ressursbruk kan utarbeides på kortere tid. Store planleggingsoppgaver som i dag er uløselige vil kunne løses. I motsetning til dagens sekvensielle metoder vil de nye metodene fullt ut utnytte den videre utvikling i datamaskiners regnekraft som er basert på parallellisering, og automatisk tilpasse seg tilgjengelig maskinvare. Verktøy for automatisk transportplanlegging blir i stadig større grad tatt i bruk. Teknologien fører til forbedringer i form av mer koordinert transport med lavere ressursbruk og mindre bruk av ressurser til planlegging. Virkningen bestemmes i stor grad av ytelsen til optimeringsmetodene som benyttes og regnekraften til datamaskinen, fordi optimeringsproblemene som skal løses er svært regnekrevende. For mange anvendelser er det fremdeles behov for kraftigere verktøy. I mange år fikk verktøyene bedre ytelse, ikke bare på grunn av metodeforbedringer, men også som følge av en sterk økning i vanlige datamaskiners klokkefrekvens. Av teknologiske årsaker stoppet økningen for noen år siden. Datamaskinene vil fremdeles få en stor forbedring i regnekraft, men nå ved at de blir utstyrt med et økende antall kjerner for parallelle beregninger. Billige akseleratorer slik som den grafiske prosessoren (GPU) har svært stor teoretisk regnekraft fordi den har et stort antall beregningskjerner. Vanlig sekvensiell programvare kan ikke utnytte denne utviklingen. Slik programvare vil faktisk kjøre saktere enn før fordi klokkefrekvensen til de nye datamaskinene er lavere enn for gårsdagens sekvensielle maskiner. Nye, parallelle optimeringsmetoder trengs for å utnytte regnekraften i dagens og fremtidens PCer. Collab II er en videreføring av Collab. Rundt halvparten av budsjettet går til et postdoktorstipend. AKTIVITETER OG RESULTATER: Vi har utviklet en GPU basert løser for DCVRP, en variant av vehicle routing problemet (VRP) som eksempelvis er relevant for levering av varer til kunder. Ved hjelp av en approksimasjonsmetode produserer den planer av samme kvalitet som en av de mest anerkjente CPU baserte løserne i verden, men på kortere tid. Hastighetsforbedringen ser ut til å øke med størrelsen på problemet. Arbeidet ble presentert på de internasjonale konferansene NOW 2015, EURO 2015, INFORMS 2016 og ROUTE 2016. Et manuskript er sendt inn til et vitenskapelig tidsskrift (UHR Nivå 2). Vi har begynt med å utvikle en ny VRP løser, denne gangen basert på en eksakt metode. Slike metoder kan garantere at optimal løsning blir funnet, men responstiden kan være for lang i praksis for store problemer. Løseren vil utnytte både CPU og GPU til oppgaver som de er godt egnet til. Vi har implementert nøkkelfunksjonaliteten av algoritmen og tidlige eksperimenter er lovende og bekrefter antakelsene som ligger på bunnen av metoden. Allikevel kreves det fortsatt mer forskning for å heve hele algoritmen til samme nivå som mer kjente metoder. Tidligere har vi utviklet en GPU-basert løser for Handelsreisendeproblemet (TSP). Den er utprøvd eksperimentelt på standard testproblemer fra litteraturen og gir løsninger som er svært nær de beste som er funnet hittil. Et nytt standardproblem er nylig definert ved de 115.475 største byer og tettsteder i USA. Vår GPU-baserte løser har produsert en rundtur gjennom disse byene som kun er 0.1% lengre enn den best kjente. Beregningen tok bare rundt 21 timer. Arbeidet er også presentert på de internasjonale konferansene NOW 2013 in Siracusa, SOAK/NOS6 i 2013 i Göteborg og VeRoLog 2014 i Oslo. Så langt har vi publisert 5 fagartikler i anerkjente tidsskrift, og vi har holdt 19 foredrag på internasjonale faglige konferanser. Et bokkapittel med beskrivelse av hovedtema i Collab II ble publisert i en sentral fagbok innen VRP utgitt av Society for Industrial and Applied Mathematics i 2014. I stedet for å arrangere en workshop, valgte vi i 2014 å holde en tutorial om GPU-programmering innen optimering i forbindelse med den internasjonale konferansen VeRoLog på Blindern i juni www.sintef.no/verolog2014. Gruppe for optimering ved SINTEF var lokal arrangør. Som følge av henvendelse fra professor Vittorio Maniezzo ved Universitetet i Bologna hadde vi besøk av gjesteforsker Francesco Strappaveccia februar-mai 2014. Under oppholdet utviklet han GPU-baserte algoritmer for korteste vei problemet (SPP). Videre utviklet han en CPU-basert algoritme for SPP til bruk i Dynamo - SINTEFs programvare for flermodal rutefinning i dynamiske nettverk. Arbeidet inngår i Francescos PhD Thesis som han forsvarte våren 2015.

The effect of advanced ITS vehicle routing and optimal route finding software is largely determined by a combination of the power of the underlying optimization methods and the power of the computer. For many applications, there is still a large gap betwe en requirements and performance offered. SINTEF has developed efficient sequential methods for real-life variants of the Vehicle Routing Problem (VRP) and the Shortest Path Problem (SPP) in dynamic, multi-modal transportation networks. These methods are the basis for the Spider and Invent VRP/IRP solvers and the Dynamo SPP solver. Sequential methods cannot exploit modern, heterogeneous PC architectures that consist of multiple cores for task parallelism and one or more stream processing accelerators suc h as the GPU. In the recently finished Collab project, SINTEF, supported by 4 academic partners abroad, has developed new algorithms for the VRP that fully utilize multiple cores for task parallelism, and other algorithms that fully utilize stream process ing accelerators. Results have already been widely published and disseminated for commercial exploitation. In Collab II, we continue to collaborate with excellent research groups abroad. We extend the efforts on VRPs and aim at self-adaptable algorithms that fully utilize all processing units of modern PCs. Self-adaptation is important for scalability and automatic exploitation of future hardware developments. We also expand the scope to the SPP for multi-modal, dynamic transportation networks. This prob lem is key to dynamic fleet management, and also to route finding for goods transportation as well as personal travel. To ensure relevance we collaborate with DI AS (newspaper distribution), GdF Suez, Statoil, Tieto AS, and PetroOnline AS (maritime and l and based transportation of LNG and petroleum products), and the ongoing Norwegian personal travel portal project and ITS Norway (intermodal transportation).

Publikasjoner hentet fra Cristin

Ingen publikasjoner funnet

Ingen publikasjoner funnet

Budsjettformål:

TRANSPORT-Transport 2025