Robust shortest path problem based on multidirectional link travel time

This article introduces directional link cost to shortest path problem and demonstrates extension of its application through robust optimization approach. We show that under budget uncertainty set this problem can be formulated as a min-max formulation, which can then be reformulated as a mixed integer linear program. For this program, we present a benders algorithm as a solution algorithm which is efficient. Based on our experiment, the importance of considering directional link cost is further stated, and the effectiveness of the proposed algorithm is also proved.