Shortest path problem with re-routing en-route

ABSTRACTSHORTEST PATH PROBLEM WITH RE-ROUTINGEN-ROUTEBanu KarakayaM.S. in Industrial EngineeringSupervisor: Asst. Prof. Osman AlpAugust, 2008In this study, we examine the shortest path problem under the possibility of"re-routing" when an arc that is being traversed is blocked due to reasons such asroad and weather conditions, congestion, accidents etc. If an incident occurs alongthe arc being traversed, the vehicle either waits until all effects of the incidentare cleared and then follows the same path thereafter, or returns to the startingnode of that arc and follows an escape route to the destination node, the lattercourse of action is called as "re-routing". Also, we consider that this arc is notvisited again throughout the travel along the network when an incident occursand the alternative of not following this arc after the event is chosen. We proposea labeling algorithm to solve this specific problem. Then, a real case problem isanalyzed by the proposed algorithm and several numerical studies are conductedin order to assess the sensitivity of the probability and travel time parameters.