Abstract
The capacitated arc routing problem (CARP) has important research significance in the area of vehicle routing services. We study a multi-depot green capacitated arc routing problem by minimizing economic cost, makespan and carbon emission cost, and then, present a modified memetic algorithm for multi-depot (MMAMD) that aims to solve the problem efficiently. According to the characteristics of multi-depots in this paper, a specific encoding scheme via the two-dimensional array and the dynamic adjustment strategy of boundary arcs between depots are proposed. By combining ant colony algorithm with local search, we present an ant colony local search strategy with extended neighborhood search for the memetic algorithm. The experimental results show that the proposed algorithm which is used to solve the model is effective, which can provide a reference for waste clearing decision.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Tirkolaee, E.B., Alinaghian, M., Hosseinabadi, A.A.R., Sasi, M.B., Sangaiah, A.K.: An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem. Comput. Electr. Eng. 77, 457–470 (2019)
Golden, B.L., Wong, R.T.: Capacitated arc routing problems. Networks 11(3), 305–315 (1981)
Lacomme, P., Prins, C., Ramdane, C.W.: Competitive memetic algorithms for Arc Routing Problems. Ann. Oper. Res. 131(4), 159–185 (2004). https://doi.org/10.1023/B:ANOR.0000039517.35989.6d
Pia, A.D., Filippi, C.: A variable neighborhood descent algorithm for a real waste collection problem with mobile depots. Intl. Trans. Oper. Res. 13(2), 125–141 (2006)
Liu, T., Jiang, Z., Geng, N.: A genetic local search algorithm for the multi-depot heterogene-ous fleet capacitated arc routing problem. Flex. Serv. Manuf. J. 26(4), 540–564 (2012). https://doi.org/10.1007/s10696-012-9166-z
Krushinsky, D., Woensel, T.V.: An approach to the asymmetric multi-depot capacitated arc routing problem. Eur. J. Oper. Res. 244(1), 100–109 (2015)
Erfan, T., Ali, H., Mehdi, S., Arun, S., Jin, W.: A hybrid genetic algorithm for multi-trip Green Capacitated Arc Routing Problem in the scope of urban services. Sustainability 10(5), 1366–1378 (2018)
Ge, X., Miao, G., Tan, B.: Research on optimization modeling and algorithm of open pollution path problem. Ind. Eng. Manage. 20(4), 46–53 (2015)
Mei, Y., Tang, K., Yao, X.: Decomposition-based memetic algorithm for multiobjective Capacitated Arc Routing Problem. IEEE Trans. Evol. Comput. 15(2), 151–165 (2011)
Shang, R., Dai, K., Jiao, L., Stolkin, R.E.: Improved memetic algorithm based on route distance grouping for multiobjective large scale Capacitated Arc Routing Problems. IEEE Trans. Cybern. 46(4), 1000–1013 (2017)
Amberg, A., Domschke, W., Vob, S.: Multiple center capacitated arc routing problems: a tabu search algorithm using capacitated trees. Eur. J. Oper. Res. 124(2), 360–376 (2000)
Zhu, Z., et al.: A hybrid genetic algorithm for the multiple depot capacitated arc routing problem. In: 2007 IEEE International Conference on Automation and Logistics, pp. 2253–2258. IEEE (2007)
Li, Y., Soleimani, H., Zohal, M.: An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. J. Clean Prod. 10(227), 1161–1172 (2019)
Bi, Z.S., Zheng, J.B., Cai, G.Y.: Multi-vehicle vehicle routing problem based on high-dimensional multi-objective optimization. Comput. Digit. Eng. 45(07), 1298–1304 (2017)
He, Z., Yen, G.: Visualization and performance metric in many-objective optimization. IEEE Trans. Evol. Comput. 20(3), 386–402 (2016)
Jiang, S., Ong, Y.S., Zhang, J.: Consistencies and contradictions of performance metrics in multiobjective optimization. IEEE Trans. Cybern. 44(12), 2391–2404 (2014)
Acknowledgements
This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant No. 61976242, in part by the Opening Project of Guangdong Province Key Laboratory of Computational Science at the Sun Yat-sen University under Grant No. 2018002, in part by the Open Fund of Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education under Grant No. IPIU2019003, and in part by the State Key Program of National Natural Science of China under Grant No. 61836009.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Cao, B., Li, R., Chen, S. (2020). A Modified Memetic Algorithm for Multi-depot Green Capacitated Arc Routing Problem. In: Pan, L., Liang, J., Qu, B. (eds) Bio-inspired Computing: Theories and Applications. BIC-TA 2019. Communications in Computer and Information Science, vol 1159. Springer, Singapore. https://doi.org/10.1007/978-981-15-3425-6_59
Download citation
DOI: https://doi.org/10.1007/978-981-15-3425-6_59
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-3424-9
Online ISBN: 978-981-15-3425-6
eBook Packages: Computer ScienceComputer Science (R0)