A Hybrid Learning Approach to Stochastic Routing
Author
Pedersen, Simon Aagaard
Term
4. term
Education
Publication year
2019
Submitted on
2019-08-16
Pages
16
Abstract
Stadigt mere tilgængelige trajektoriedata gør det muligt at beskrive trafikale forhold i detaljer. Vi modellerer et usikkert vejnet som en graf, hvor hvert vejsegment har en rejsetidsfordeling (mulige tider med tilhørende sandsynligheder). Vi undersøger probabilistisk budgetruteplanlægning, som søger den rute, der med størst sandsynlighed når frem inden for en given tidsramme. En central opgave er at udlede fordelingen for en hel rutes rejsetid ud fra segmenternes fordelinger. Metoder baseret på konvolution antager typisk uafhængighed mellem segmenter, men det holder ofte ikke i praksis (fx kan trængsel på ét segment påvirke nabosegmenter), hvilket reducerer nøjagtigheden. Vi foreslår en hybrid tilgang, der kombinerer konvolution med maskinlæringsbaseret estimering for at tage højde for afhængigheder mellem fordelinger og dermed forbedre nøjagtigheden. Dernæst præsenterer vi en effektiv rutealgoritme, der udnytter den hybride tilgang og anvender beskæringsteknikker til tidligt at frasortere usandsynlige ruter, så beregningen forbliver hurtig. Empiriske studier på et omfattende sæt af virkelige trajektorier belyser løsningens egenskaber og indikerer, at den er praktisk anvendelig.
Increasingly available trajectory data makes it possible to capture traffic conditions in detail. We model an uncertain road network as a graph where each road segment has a travel time distribution (possible times with associated probabilities). We study probabilistic budget routing, which seeks the path with the highest probability of arriving within a given time budget. A key operation is to derive a route’s travel time distribution from the distributions of its segments. Methods based on convolution typically assume independence between segments, but this often fails in practice (e.g., congestion on one segment affects its neighbors), which reduces accuracy. We propose a hybrid approach that combines convolution with machine-learning-based estimation to account for dependencies between distributions and thereby improve accuracy. We then present an efficient routing algorithm that leverages the hybrid approach and uses pruning techniques to discard unlikely routes early, keeping computation fast. Empirical studies on a substantial real-world trajectory set examine the properties of the method and indicate that it is practical.
[This abstract was generated with the help of AI]
Documents