Trajectory-Adaptive Routing in Dynamic Networks with Dependent Random Link Travel Times

He Huang · Song Gao

14 citations0/0 files storedTransportation Science

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Transportation Planning and Optimization Complexity and Algorithms in Graphs Vehicle Routing Optimization Methods

Abstract

This paper addresses the problem of finding the optimal routing policies with only trajectory information in a stochastic time-dependent network where all link travel times are temporally and spatially correlated. Two equivalent definitions are given for trajectory-adaptive routing policy. The first definition follows the mapping definition in a series of previous studies, where the trajectory information is included in the state variable. With that definition, any subpolicy of an optimal routing policy must also be optimal, and the algorithm developed in previous studies could serve as an exact solution, but the nature of the definition that trajectory information is included in the state variable determines that the number of states is prohibitively huge. Therefore, a second definition is given as a recursive definition, where the trajectory information is not included in the state variable. It is shown that, with the second definition, a subpolicy of an optimal/nondominated routing policy is not necessarily optimal/nondominated, but any subpolicy of a pure routing policy must also be pure which is a new property defined based on nondominance. An exact algorithm is designed to find optimal trajectory-adaptive routing policies based on the aforementioned property of pure routing policy. A comparison is made between the optimal trajectory-adaptive routing policies and the optimal paths in the same test networks to investigate the benefit of being adaptive. The results show that the benefit of being adaptive to trajectory information is more significant with a higher risk aversion, a higher correlation, and/or a larger network. The online appendix is available at https://doi.org/10.1287/trsc.2016.0691 .

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 14 citations exist upstream.

References

1986The Fastest Path through a Network with Random Time-Dependent Travel Times 2000Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks 2009Shortest path problem considering on-time arrival probability 2005Optimal routing policy problems in stochastic time-dependent networks 2005Arriving on Time 2000Adaptive least-expected time paths in stochastic, time-varying transportation and data networks 2005Shortest paths in stochastic networks with correlated link costs 2011Reliable shortest path finding in stochastic networks with spatial correlated link travel times

Cited by

2021On scenario construction for stochastic shortest path problems in real road networks 2021Optimal Routing Policy for a Mixed Traffic Flow of Connected Vehicles and Regular Vehicles with En-route Information 2024Reliable Routing Strategies on Urban Transportation Networks 2021Activity-travel scheduling in stochastic multi-state supernetworks with spatial and temporal correlations 2021Reliable trajectory-adaptive routing strategies in stochastic, time-varying networks with generalized correlations

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.