In this work, we investigate a generalization of the classical capacitated arc routing problem, called the Multi-depot Capacitated Arc Routing Problem (MCARP). We give exact and approximation algorithms for different variants of the MCARP. First, we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version. Second, for the multi-depot rural postman problem, i.e., a special case of the MCARP where the vehicles have infinite capacity, we develop a
Publications
- Article type
- Year
- Co-author
Year
![](/assets/img/article/article-lock.png)
Tsinghua Science and Technology 2023, 28 (5): 916-928
Published: 19 May 2023
Downloads:69
Total 1