The dynamic shortest path problem with anticipation

The dynamic shortest path problem with anticipation

Authors: Thomas, B.W.; White III, C.C.

European Journal of Operational Research - 2007 Volume 176, Pages 836-854

Mobile communication technologies enable truck drivers to keep abreast of changing traffic conditions in real-time. We assume that such communication capability exists for a single vehicle traveling from a known origin to a known destination where certain arcs en route are congested, perhaps as the result of an accident. Further, we know the likelihood, as a function of congestion duration, that congested arcs will become uncongested and thus less costly to traverse. Using a Markov decision process, we then model and analyze the problem of constructing a minimum expected total cost route from an origin to a destination that anticipates and then responds to changes in congestion, if they occur, while the vehicle is en route. We provide structural results and illustrate the behavior of an optimal policy with several numerical examples and demonstrate the superiority of an optimal anticipatory policy, relative to a route design approach that reflects the reactive nature of current routing procedures. © 2005 Elsevier B.V. All rights reserved.

https://doi.org/10.1016/j.ejor.2005.09.019

Cite as:

@article{Thomas_2007,
	doi = {10.1016/j.ejor.2005.09.019},
	url = {https://doi.org/10.1016%2Fj.ejor.2005.09.019},
	year = 2007,
	month = {jan},
	publisher = {Elsevier {BV}},
	volume = {176},
	number = {2},
	pages = {836--854},
	author = {Barrett W. Thomas and Chelsea C. White},
	title = {The dynamic shortest path problem with anticipation},
	journal = {European Journal of Operational Research}
}



    Leave a Reply

    Your email address will not be published. Required fields are marked *

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close