Shortest Path Problem with Random Rerouting
MetadataShow full item record
This paper addresses a variant of the shortest path problem with a particular type of uncertainty where the route that differs from the scheduled one might be traversed with certain probability. The shortest path problem with random rerouting is modeled as an optimization problem, where in a graph we are asked to obtain the policy that indicates the path selection at each node, such that the expected cost incurred in moving from the starting node to the destination node is minimal. A mixed-integer programming (MIP) model is constructed, and formulated into a MIP solver. With the increasing of the size of problem instances, the two-stage heuristics involved with a modified Dijkstra algorithm are designed to handle the instances where the MIP solver is failed to obtain the solution. Numerical experiments are implemented to illustrate the efficiency of the heuristics.