Improving Cost Estimation Models with Estimation Updates and road2vec: a Feature Learning Framework for Road Networks

Jepsen, Tobias Skovgaard ; Fruensgaard, Martin

4. term

Software, Master

2017

2017-06-06

45

Ruteplanlægning bygger på vejnet som vægtede grafer, hvor nøjagtige kantvægte (f.eks. rejsetid) er afgørende for kvaliteten af de foreslåede ruter. Denne afhandling adresserer to kendte svagheder i eksisterende vægtestimeringsmodeller: aggregationsmodeller kræver mange GPS-observationer pr. kant, mens parametriske modeller ikke udnytter nye observationer efter træning og er følsomme over for feature-engineering. Vores første bidrag er en generel omkostningsestimeringsramme, der Bayesiansk opdaterer en forudgående (prior) kostestimat fra en valgfri model med indsamlede GPS-observationer ved blot at gemme antal observationer og deres middelværdi; opdateringen kan udføres i konstant tid. På en rejsetidsopgave for kant-interval-par reducerer rammen MAPE med 7,43 % (1,37 procentpoint) med hele træningssættet, og næsten hele gevinsten opnås allerede med 20 % af data (−6,78 %, 1,38 procentpoint). Som andet bidrag introducerer vi road2vec, en feature-læringsramme, der overfører teknikker fra sprogmodellering til vejnet ved at lære repræsentationer af kanter og kantbeskrivelser baseret på en kant’s simple graflabel og dens omgivelser, hvilket mindsker problemet med at geodætisk fjerne, men strukturelt ens, vejsegmenter aldrig co-forekommer. Når lærte road2vec-features erstatter håndkonstruerede features i en lineær baseline, falder MAPE med 7,54 % (1,39 procentpoint) og er robust over for datanedskæring (kun +1,0 % MAPE ved reduktion fra 100 % til 20 % træningsdata). Kombinationen af road2vec i en lineær model med den Bayesianske opdateringsramme opnår MAPE 16,41 %, svarende til 9,39 % (1,70 procentpoint) lavere end en aggregationsbaseline og 10,99 % (2,03 procentpoint) lavere end en parametrisk baseline. Efter parametertuning kan road2vec-træningen gennemføres på under 10 minutter for et vejnet med 115.977 segmenter uden domænespecifik viden. Endelig viser en K-means-undersøgelse på vejnettet i Nordjylland med Calinski–Harabasz-indekset, at de lærte repræsentationer fanger strukturel lighed, bl.a. for motorveje, hovedveje i større byer og centrumgader i mindre byer. Samlet set bygger de to bidrag bro mellem aggregerende og parametriske tilgange og forbedrer både nøjagtighed og anvendelighed i omkostningsestimering for vejnet.

Modern routing relies on road networks modeled as weighted graphs, where accurate edge costs (e.g., travel times) are critical for route quality. This thesis tackles two shortcomings of current weight assignment approaches: aggregation models need many GPS observations per edge, while parametric models stop using observations after training and depend heavily on hand-crafted features. Our first contribution is a general cost estimation framework that Bayesianly updates a prior cost estimate from any model with collected GPS observations using only the count and mean of observations; updates run in constant time. On an edge–time-interval travel time task, this framework reduces MAPE by 7.43% (1.37 percentage points) with the full training set, with most gains already at 20% of data (−6.78%, 1.38 percentage points). Our second contribution, road2vec, adapts language-modeling feature learning to road networks by learning representations of edges and edge descriptors from a simple graph label and contextual surroundings, mitigating the issue that geodesically distant but structurally similar segments never co-occur. Replacing engineered features in a linear baseline with road2vec features lowers MAPE by 7.54% (1.39 percentage points) and remains robust under data reduction (only a 1.0% MAPE increase when training data drops from 100% to 20%). Combining road2vec in a linear model with the Bayesian update framework achieves a MAPE of 16.41%, improving over an aggregation baseline by 9.39% (1.70 percentage points) and over a parametric baseline by 10.99% (2.03 percentage points). After parameter tuning, road2vec embeddings for 115,977 segments train in under 10 minutes without domain knowledge. Finally, a K-means study on Northern Jutland’s road network evaluated with the Calinski–Harabasz index indicates that the learned features capture structural similarity, including clusters for motorways, major urban roads, and small-town centers. Together, these contributions bridge aggregation and parametric methods, improving both accuracy and practicality in road network cost estimation.

[This summary has been generated with the help of AI directly from the project (PDF)]

Download
View record in AAU Student Projects