The dynamic shortest path problem with anticipation

The dynamic shortest path problem with anticipation

0.00 Avg rating0 Votes
Article ID: iaor20084692
Country: Netherlands
Volume: 176
Issue: 2
Start Page Number: 836
End Page Number: 854
Publication Date: Jan 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: markov processes, communications
Abstract:

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.

Reviews

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