Vi anser att det stokastiska i tid ankomst (SOTA) problemet att hitta den optimala routing strategi för att nå en viss destination inom en förspecificerad tid budget och ge de första resultaten på att använda förbehandlingstekniker för att påskynda frågetiden. Vi börjar med att identifiera vissa egenskaper hos SOTA-problemet som begränsar de typer av förbearbetningstekniker som kan användas i denna inställning, och sedan definiera de stokastiska varianterna av två deterministiska kortaste väg förbearbetningstekniker som kan anpassas till SOTA-problemet, nämligen räckvidd och båge-flaggor. Vi presenterar förbehandlings- och frågealgoritmer för varje teknik, och presenterar även en förlängning till standard räckvidd baserad förbearbetningsmetod som ger ytterligare beskärning. Slutligen förklarar vi begränsningarna i detta tillvägagångssätt på grund av ineffektiviteten i förbearbetningsfasen och lägger fram ett snabbt heuristiskt förbearbetningsprogram. Numeriska resultat för San Francisco, Luxemburg och ett syntetiskt vägnät visar upp till en storleksordning förbättring i frågetiden för korta frågor, med ännu större vinster förväntas för längre frågor.
Sabran m.fl. REF visade hur förbearbetningsteknik kan användas för att ytterligare minska beräkningstiden för SOTA-problemet.
Precomputation techniques for the stochastic on-time arrival problem
{'venue': 'ALENEX', 'journal': None, 'mag_field_of_study': ['Computer Science']}