Solving multi-station refuse collection problem based on cooperative co-evolutionary algorithm

doi:10.3969/j.issn.0253-2778.2020.05.018

Abstract

Abstract: With the continuous development of the economy and the rapid advancement of urbanization, the amount of refuse produced nationwide is rapidly increasing, and the cost for refuse processing is in turn on the rise, with refuse collection occupying an increasing proportion of it. A complex refuse collection problem is investigated, i.e., the multi-station refuse collection problem (MSRCP). The MSRCP is mapped to the multi-depot vehicle routing problem (MDVRP), and a model for MSRCP with the goal of minimum vehicle transportation cost is established. According to the characteristics of MSRCP, an approach based on Cooperative Co-evolutionary (CC) as external framework is designed for the problem. Firstly, the improved clustering algorithm is used to assign each collection point to the appropriate station. Then, a hybrid genetic algorithm (HGA) is designed for the vehicle routing problem (VRP) with the stations as the depots and MSRCP being divided into some VRPs. Finally, the refuse collection in Daguan District of Anqing City was taken as an example to verify the model and its algorithm, The results show that the proposed algorithm is effective in reducing transportation cost of complex refuse collection problems.

Key words: refuse collection problem, multi-stations, cooperative co-evolutionary, clustering algorithm, genetic algorithm

CLC Number:

TP301

ZHANG Yuzhou, ZHANG Ziwei. Solving multi-station refuse collection problem based on cooperative co-evolutionary algorithm[J]. Journal of University of Science and Technology of China, 2020, 50(5): 695-704.

References

［1］
WILSON B G, BAETZ B W. Modeling municipal solid waste collection systems using derived probability distributions Ⅰ: Model development[J]. Journal of Environmental Engineering, 2001, 127(11): 1031-1038.
[2] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[3] MOLINA J C, EGUIA I, RACERO J. Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood tabu search algorithm: A case study[J]. Top, 2019, 27(2): 253-287.
[4] YAAKOUBI O E, BENABDOUALLAH M, BOJJI C. Heuristic approaches for waste containers location problem and waste collection routes optimisation in an urban area[J]. International Journal of Environment and Waste Management, 2018, 21(4): 269-286.
[5] BENJAMIN A M, BEASLEY J E. Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities[J]. Computers & Operations Research, 2010, 37(12): 2270-2280.
[6] BENJAMIN A M, BEASLEY J E. Metaheuristics with disposal facility positioning for the waste collection VRP with time windows[J]. Optimization Letters, 2013, 7(7): 1433-1449.
[7] AKHTAR M, HANNAN M A, BEGUM R A. Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization[J]. Waste Management, 2017, 61(3): 117-128.
[8] MCLEOD F, ERDOGAN G, CHERRETT T. Dynamic collection scheduling using remote asset monitoring: Case study in the UK charity sector[J]. Transportation Research Record, 2013, 2378(2378): 65-72.
[9] 马华伟, 靳鹏, 杨善林. 时变车辆路径问题的启发式算法[J]. 系统工程学报, 2012, 27(2): 256-262.
[10] HENKE T, SPERANZA M G, WAESCHER G. A branch-and-cut algorithm for the
multi-compartment vehicle routing problem with flexible compartment sizes[J]. Annals of Operations Research, 2019, 275(2): 321-338.
[11] RENAUD J, LAPORTE G, BOCTOR F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23(3): 229-235.
[12] 王勇, 任音吉, 刘永. 基于多中心车辆路径问题的收益分配优化研究[J]. 交通运输系统工程与信息, 2018, 18(3):214-221.
[13] 许争争, 唐加福. 基于交汇点协作的车辆调度问题的两阶段算法[J]. 系统工程学报, 2013, 28(5): 573-580.
[14] 于滨, 靳鹏欢, 杨忠振. 两阶段启发式算法求解带时间窗的多中心车辆路径问题[J]. 系统工程理论与实践, 2012, 32(8): 1793-1800.
[15] LUO J, LI X, CHEN M R. Multi-phase meta-heuristic for multi-depots vehicle routing problem[J]. Journal of Software Engineering and Applications, 2013, 6(03): 82-86.
[16] POTTER A M, JONG K A. A cooperative co-evolutionary approach to function optimization[C]. Proceedings of the 3rd International Conference on Parallel Problem Solving from Nature, 1994: 249-257.
[17] MEI Y, OMIDVAR M N, LI X. A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization[J]. ACM Transactions on Mathematical Software, 2016, 42(2): 1-24.
[18] CHANDRA R, FREAN M, ZHANG M J. A memetic framework for cooperative coevolution of recurrent neural networks[C]. Neural Networks (IJCNN), Proceedings of the 2011 International Joint Conference on Neural Networks, 2011: 673-680.
[19] OMIDVAR M N, YANG M, MEI Y. DG2: A faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(6): 929-942.
[20] OLIVEIRA F B D, ENAYATIFAR R, SADAEI H J. A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J]. Expert Systems with Applications, 2016, 43: 117-130.
[21] VIDAL T, CRAINIC T G, GENDREAU M. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems[J]. Operations Research, 2012, 60(3): 611-624.
[22] 张凯波, 李斌. 合作型协同演化算法研究进展[J]. 计算机工程与科学, 2014, 36(4): 674-684.
[23] GIOSA I D, TANSINI I L, VIERA I O. New assignment algorithms for the multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2002, 53(9): 977-984.

()
()

[1]	YU Xiaoyu, BI Xiuchun, ZHANG Shuguang. Optimal threshold of pairs trading [J]. Journal of University of Science and Technology of China, 2020, 50(6): 784-792.
[2]	LI Erchao, ZHAO Yumeng. Optimizing design of PID controller with time varying undetectable changes based on multiple reference points [J]. Journal of University of Science and Technology of China, 2019, 49(2): 125-131.
[3]	WANG Jiayu, ZHANG Zhenyu, CHU Zheng, WU Xiaohong. A trajectory data density partition based distributed parallel clustering method [J]. Journal of University of Science and Technology of China, 2018, 48(1): 47-56.
[4]	XU Xueli, ZHAO Xuejing. Application of sparse spectral clustering algorithm in high-dimensional data [J]. Journal of University of Science and Technology of China, 2017, 47(4): 311-319.
[5]	ZHANG Zhenya, ZHANG Meng, XIE Chenlei,ZHANG Zhaoxiang, FANG Qiansheng. Research on leakage location of secondary water distribution networks [J]. Journal of University of Science and Technology of China, 2017, 47(4): 336-341.
[6]	YOU Haifeng, WANG Xiwei, XU Xiang, WANG Xufa. A multi-user interactive genetic algorithm and its application in group design [J]. Journal of University of Science and Technology of China, 2010, 40(4): 425-430.