Efficient Stochastic Routing in PAth-CEntric Uncertain Road Networks.
Author
Andonov, Georgi
Term
4. term
Education
Publication year
2008
Submitted on
2008-06-08
Pages
17
Abstract
Dette speciale undersøger, hvordan man effektivt kan finde ruter med høj sandsynlighed for at ankomme inden for et givet tidsbudget i usikre vejnet. Vi fokuserer på SPOTAR-problemet (Shortest Path with On-Time Arrival Reliability) og anvender det stifokuserede PACE-vejnetmodel, som bevarer usikre rejsetider ikke kun for kanter, men også for hyppige stier for at udnytte afhængigheder mellem vejsegmenter. Vi udvikler en A*-baseret søgealgoritme, der bruger heuristikker til at beskære søgerummet: en baseline med euklidisk afstand, minimum rejsetid via korteste vej (SP) og Arc-Potentials. For at konstruere stærkere heuristikker studerer vi SOTA-problemet (Stochastic On-Time Arrival) og beregner en optimal routingpolitik ved hjælp af en opdateringsgraf, topologisk ordning og dynamisk programmering; beregninger genbruges på tværs af tidsbudgetter, og PACE anvendes for at øge nøjagtigheden af rejsetidsfordelinger. SOTA-politikken bruges til at generere Arc-Potentials, en forbehandling der partitionerer destinationer i regioner og mærker kanter med tærskler, som muliggør effektiv beskæring under A*-søgning. Vi diskuterer både hukommelsesforbrug og køretid: Arc-Potentials giver mulighed for at bytte plads mod tid via partitionsgranularitet, og vi varierer tidsbudgetter, kilde–destination-afstande og antal destinationsregioner i eksperimenter på et PACE-net afledt af virkelige trajektoriedata. Resultaterne indikerer, at Arc-Potentials-heuristikken guider søgningen effektivt og kan reducere søgeomkostninger, og at PACE-modellen forbedrer pålidelighedsestimeringer ved at indfange afhængigheder, sammenlignet med kant-baserede modeller.
This thesis investigates how to efficiently find routes with a high probability of arriving within a given time budget in uncertain road networks. We address the SPOTAR problem (Shortest Path with On-Time Arrival Reliability) using the path-centric PACE model, which maintains uncertain travel times not only for edges but also for frequently traveled paths to capture dependencies between road segments. We design an A*-based search algorithm that prunes the search space with heuristics: a Euclidean baseline, minimum travel-time via shortest path (SP), and Arc-Potentials. To build stronger heuristics, we study the SOTA problem (Stochastic On-Time Arrival) and compute an optimal routing policy using an update graph, topological ordering, and dynamic programming; subresults are reused across time budgets, and PACE is applied to improve travel-time distribution accuracy. The SOTA policy is then used to generate Arc-Potentials, a preprocessing that partitions destinations into regions and labels edges with thresholds to enable effective pruning during A* search. We discuss both memory and runtime: Arc-Potentials supports a controllable space–time trade-off via partition granularity, and we vary time budgets, source–destination distances, and the number of destination regions in experiments on a PACE network derived from real trajectory data. Results indicate that the Arc-Potentials heuristic guides the search effectively and reduces search effort, and that the PACE model improves reliability estimates by capturing dependencies compared with edge-centric models.
[This summary has been generated with the help of AI directly from the project (PDF)]
Documents