A Hybrid Genetic Algorithm for the Multiple Depot Capacitated Arc Routing Problem
This paper presents a new Hybrid Genetic Algorithm (HGA) for the Multiple Depot Capacitated Arc Routing Problem (MDCARP) with homogeneous vehicles. This algorithm improves the Traditional-Genetic Algorithm (TGA) on the basis of the Partheno-Genetic Algorithm (PGA), which can avoid the premature convergence effectively and overcome the inefficient problem of existing heuristic algorithms. The background of our study is assigning the routes of sprinklers, so computational experiments are done with the real-life data provided by the Sanitation Department of Chongqing city in china, and the computational results reveal that the proposed HGA can solve MDCARP effectively. Furthermore, two comparison experiments for the Single Depot Capacitated Arc Routing Problem (1-CARP) show that this algorithm can also solve the 1-CARP with better result and much higher efficiency than the best metaheuristic published.
Multiple Depot Capacitated Arc Routing Problem MDCARP Hybrid Genetic Algorithm
Zhengyu Zhu Xiaohua Li Yong Yang Xin Deng
Mengshuang Xia, Zhihua Xie,Jianhui Liu Computer College of Chongqing University, Chongqing 400044, P.R.China
国际会议
2007 IEEE International Conference on Automation and Lofistics
山东济南
英文
2007-08-18（万方平台首次上网日期，不代表论文的发表时间）