Using Incomplete Information for Complete Weight Annotation of Road Networks

Bin Yang, Manohar Kaul, Christian Søndergaard Jensen

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

43 Citationer (Scopus)

Resumé

We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective.
OriginalsprogEngelsk
TidsskriftI E E E Transactions on Knowledge & Data Engineering
Vol/bind26
Udgave nummer5
Sider (fra-til)1267-1279
Antal sider13
ISSN1041-4347
DOI
StatusUdgivet - 10 jun. 2014

Fingerprint

Travel time
Gas emissions
Greenhouse gases
Global positioning system
Trajectories
Costs
Vehicle routing
Topology

Citer dette

@article{9274c80cbdef46c3a89967361be2cd2d,
title = "Using Incomplete Information for Complete Weight Annotation of Road Networks",
abstract = "We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective.",
author = "Bin Yang and Manohar Kaul and Jensen, {Christian S{\o}ndergaard}",
year = "2014",
month = "6",
day = "10",
doi = "10.1109/TKDE.2013.89",
language = "English",
volume = "26",
pages = "1267--1279",
journal = "I E E E Transactions on Knowledge & Data Engineering",
issn = "1041-4347",
publisher = "IEEE",
number = "5",

}

Using Incomplete Information for Complete Weight Annotation of Road Networks. / Yang, Bin; Kaul, Manohar; Jensen, Christian Søndergaard.

I: I E E E Transactions on Knowledge & Data Engineering, Bind 26, Nr. 5, 10.06.2014, s. 1267-1279.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Using Incomplete Information for Complete Weight Annotation of Road Networks

AU - Yang, Bin

AU - Kaul, Manohar

AU - Jensen, Christian Søndergaard

PY - 2014/6/10

Y1 - 2014/6/10

N2 - We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective.

AB - We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective.

U2 - 10.1109/TKDE.2013.89

DO - 10.1109/TKDE.2013.89

M3 - Journal article

VL - 26

SP - 1267

EP - 1279

JO - I E E E Transactions on Knowledge & Data Engineering

JF - I E E E Transactions on Knowledge & Data Engineering

SN - 1041-4347

IS - 5

ER -