Lagrangian relaxation heuristic algorithm of arc routing problem under time-space network

The arc routing problem of road operating vehicles under the time-space network was studied to reduce the vehicle dispatching cost and optimize the vehicle transportation path. In view of the time variation of road travel and the time-space characteristics of vehicle operation, a time-space network was constructed, and a time-space network flow model for the arc routing problem was built. A heuristic algorithm based on Lagrangian relaxation was designed, and the Lagrangian multipliers were introduced to relax the coupling constraints to establish the Lagrangian relaxation problem. Furthermore, the relaxation problem was decomposed into the single vehicle shortest path problem by the Lagrangian decomposition. The sub-gradient algorithm was applied to update the multipliers, solve the Lagrangian dual problem, and update the lower bound of the optimal solution for the original problem. The heuristic algorithm was employed to produce a feasible solution and update the upper bound of the optimal solution for the original problem. Empirical analysis of the algorithm was carried out in different cases under the six-node transportation network and Sioux-Falls network. Calculation results show that the values of the gap between the upper and lower bounds of the six cases in the six-node transportation network are equal to 0 or close to 0. In the Sioux-Falls network, the gap value of Case 2 is 0.02%, and those of the remaining five cases are equal to 0. The approximate optimal solution with high quality can be obtained in all cases. In the most complex case (15 vehicles, 70 tasks), a solution without gap is obtained by the algorithm in an acceptable time, and the optimal vehicle paths are calculated. With the increase of the number of iterations, the Lagrangian multipliers will become fixed through gradual convergence. When the vehicle capacity increases from 50 to 100, the optimal solution reduces from 52 to 42, which shows that when the numbers of tasks and vehicles are constant, an appropriate increase in vehicle capacity is capable of reducing operating cost. Therefore, compared with commercial solvers, the heuristic algorithm based on the Lagrangian relaxation, featuring a smaller gap value and higher solution quality, is able to solve the arc routing problem more efficiently. 7 tabs, 11 figs, 33 refs.