Abstract:In this paper, the constrained shortest path problem of traffic network with the assumption that the road passage time is a random variable is studied. The 0-1 integer programming model is established to find out the path of the minimum expected travel time. In addition to flow balance and section capacity constraints, unique path selection constraints are introduced to ensure that only the optimal path can be generated in the end. Then, a Lagrange relaxation method is proposed to relax the difficult constraints and the relaxation model is decomposed into two subproblems. In order to minimize the difference between upper and lower bounds, an algorithm framework is designed, which combines the subgradient algorithm, label correction algorithm and -shortest path algorithm to find the approximate optimal solution. Finally, the framework is applied to xinluo District of Longyan city for calculation test. The results show that the proposed algorithm can find high quality solutions with small relative gaps, and the validity of the proposed algorithm is verified.