This paper investigates the mean standard deviation shortest path problem in large scale stochastic transportation networks and proposes a graph embedding and approximate dynamic programming (GE-ADP) method. GE-ADP employs the graph embedding technique to represent the nodes of a graph with fixed $d$ -dimensional vectors, and in the meanwhile, establishes extended Bellman equations to describe the recursive relationships of both the first-order and second-order moments of travel time for all the nodes, when given a deterministic routing policy. Approximate dynamic programming (ADP) is used to evaluate the performance of the given routing policy, and an improved policy is derived, thereafter. The process of policy evaluation and policy improvement loops until the optimal policy is reached. Both theoretical analysis and simulation results show the efficiency of the proposed algorithm when compared with state of the arts, and GE-ADP offers a flexible trade-off parameter $(d)$ between the algorithm's accuracy and efficiency.
Graph Embedding and Approximate Dynamic Programming for the Reliable Shortest Path Problem
2021-09-19
1102301 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Implementation Issues for the Reliable A Priori Shortest Path Problem
Online Contents | 2009
|Implementation Issues for the Reliable a Priori Shortest Path Problem
Transportation Research Record | 2009
|