Lagrangian relaxation-based decomposition approaches for the capacitated arc routing problem in the state-space-time network

ABSTRACT

We study the capacitated arc routing problem in the state-space-time network. A multi-commodity network flow model is formulated in the state-space-time network. Two Lagrangian relaxation-based decomposition methods are developed to tackle this problem. By dualizing the coupling constraints to the objective function, the Lagrangian relaxed problem (LR) can be decomposed into several routing subproblems in the state-space-time network. Then we extend quadratic penalty terms to the LR and obtain an augmented Lagrangian relaxed problem (ALR). By applying the alternating direction method of multipliers and linearization techniques, we decompose the ALR into a sequence of routing subproblems. We solve these subproblems of LR and ALR by a time-dependent dynamic programming algorithm. Feasible solutions are produced according to the result of the LR or ALR. The Lagrangian multipliers are updated by the subgradient optimization method. We implement the proposed methods in three networks, showing that the ALR-based method has better performance.

KEYWORDS:

• Capacitated arc routing problem
• State-space-time network
• Lagrangian relaxation
• alternating direction method of multipliers
• symmetry break

Acknowledgments

This research is supported by the National Natural Science Foundation of China (No. 52172318 and 52131203). Additionally, we are also thankful to anonymous referees for their constructive feedbacks in leading to the current form of this article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [52172318]; Natural Science Foundation of Jilin Province [52131203].