Dual Dynamic Programming for the Mean Standard Deviation Canadian Traveller Problem

Page view(s)
55
Checked on Jan 10, 2025
Dual Dynamic Programming for the Mean Standard Deviation Canadian Traveller Problem
Title:
Dual Dynamic Programming for the Mean Standard Deviation Canadian Traveller Problem
Journal Title:
IEEE Transactions on Vehicular Technology
Publication Date:
18 July 2022
Citation:
Guo, H., Shi, R., Rus, D., & Yau, W.-Y. (2022). Dual Dynamic Programming for the Mean Standard Deviation Canadian Traveller Problem. IEEE Transactions on Vehicular Technology, 1–15. https://doi.org/10.1109/tvt.2022.3191490
Abstract:
This paper studies the mean standard deviation (mean-std) Canadian traveller problem (CTP). Different from the canonical CTP, which aims at minimizing the traveller's expected travel time, while considering edge breakdown probabilities, we introduce the reliability version of CTP, which tries to find a routing policy with the minimal linear combination of the travel time's mean and standard deviation. With the recent development of internet-of-things (IoT) technology, the transportation network's edges' travel-time statistics, i.e., mean and standard deviation, as well as the traversal probabilities, are available to the end users. With those information, we propose a dual dynamic programming (DDP) method, which simultaneously estimates the first-order and the second-order moments of a given decision-list (DL) policy, and thereby makes improvements towards to the optimal one through the generalized policy iteration (GPI) scheme. We construct an open source benchmark environment to evaluate the performance of different mean-std CTP solutions, and show that the DDP method outperforms state of the arts in a range of transportation networks.
License type:
Publisher Copyright
Funding Info:
This research / project is supported by the National Research Foundation - RIE2020 - Advanced Manufacturing and Engineering
Grant Reference no. : A1687b0033
Description:
© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
ISSN:
1939-9359
0018-9545
Files uploaded:

File Size Format Action
tvt-dl-ddp-final-amended.pdf 6.96 MB PDF Open