Vi presenterar en ny teknik för snabb beräkning av rutten som maximerar sannolikheten för ankomst i tid i stokastiska nätverk, även känd som den väg-baserade stokastiska vid ankomst (SOTA) problem. Vi utnyttjar lösningen på det policybaserade SOTA-problemet, som är av pseudopolynomisk tids komplexitet i tidsbudgeten för resan, som en heuristisk för att effektivt beräkna den optimala vägen. Vi introducerar också Arc-Potentials, en förlängning till Arc-Flags förbearbetningsalgoritm, vilket förbättrar effektiviteten i grafen förbearbetning och minskar beräkningstiden. Slutligen presenterar vi omfattande numeriska resultat som visar effektiviteten i vår algoritm och observera att dess drifttid när det gäller policyn (som effektivt kan erhållas med hjälp av förbehandling) nästan alltid är linjär i längden på den optimala vägen för våra testnätverk.
Lösning av SPOTAR-problemet baserat på policybaserad SOTA som heuristisk presenteras REF.
Tractable Pathfinding for the Stochastic On-Time Arrival Problem
{'venue': 'LNCS 9685 (SEA 2016) 231-245', 'journal': None, 'mag_field_of_study': ['Computer Science']}