DRL Router: Distributional Reinforcement Learning-Based Router for Reliable Shortest Path Problems

Abstract

This article studies reliable shortest path (RSP) problems in stochastic transportation networks. The termreliabilityin the RSP literature has many definitions, e.g., 1) maximal stochastic on-time arrival probability, 2) minimal travel time with a high-confidence constraint, 3) minimal mean and standard deviation combination, and 4) minimal expected disutility. To the best of our knowledge, almost all state-of-the-art RSP solutions are designed to target one specific RSP objective, and it is very difficult, if not impossible, to adapt them to other RSP objectives. To bridge the gap, this article develops a distributional reinforcement learning (DRL)-based algorithm, namely, DRL-Router, which serves as a universal solution to the four aforementioned RSP problems. DRL-Router employs the DRL method to approximate the full travel time distribution of a given routing policy and then makes improvements with respect to the user-defined RSP objective through a generalized policy iteration scheme. DRL-Router is 1) universal, i.e., it is applicable to a variety of RSP objectives; 2) model free, i.e., it does not rely on well calibrated travel time distribution models; 3) it is adaptive with navigation objective changes; and 4) fast, i.e., it performs real-time decision making. Extensive experimental results and comparisons with baseline algorithms in various transportation networks justify both the accuracy and efficiency of DRL-Router.

Cite this work

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

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

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