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 vari...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(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.Lastly,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.展开更多
This paper introduces a new algorithm based on local search for the capacitated arc routing problem(CARP)and the split-delivery capacitated arc routing problem(SDCARP).We present a intermediate model to transfer CARP ...This paper introduces a new algorithm based on local search for the capacitated arc routing problem(CARP)and the split-delivery capacitated arc routing problem(SDCARP).We present a intermediate model to transfer CARP to SDCARP and then solve the two problems by an algorithm which combines the iterated local search and the memetic algorithm.We use crossovers to perform fully reproducible initializations in each local search iteration and edge-marking to save computation time.The computational results on 63 instances of standard benchmarks show that the proposed algorithm outperforms most of the existing best-known solutions obtained by other heuristics within a reasonable computing time.Furthermore,compared with the CARP solutions,our algorithm finds three optimums for the SDCARP.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11671135,11871213,11901255)the Natural Science Foundation of Shanghai(No.19ZR1411800)。
文摘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(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.Lastly,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.
文摘This paper introduces a new algorithm based on local search for the capacitated arc routing problem(CARP)and the split-delivery capacitated arc routing problem(SDCARP).We present a intermediate model to transfer CARP to SDCARP and then solve the two problems by an algorithm which combines the iterated local search and the memetic algorithm.We use crossovers to perform fully reproducible initializations in each local search iteration and edge-marking to save computation time.The computational results on 63 instances of standard benchmarks show that the proposed algorithm outperforms most of the existing best-known solutions obtained by other heuristics within a reasonable computing time.Furthermore,compared with the CARP solutions,our algorithm finds three optimums for the SDCARP.
