基于合作协同进化的多回收站点垃圾收运问题求解

doi:10.3969/j.issn.0253-2778.2020.05.018

中国科学技术大学学报 ›› 2020, Vol. 50 ›› Issue (5): 695-704.DOI: 10.3969/j.issn.0253-2778.2020.05.018

基于合作协同进化的多回收站点垃圾收运问题求解

张玉州，张子为

安庆师范大学，计算机与信息学院，安徽安庆 246133

收稿日期:2019-07-30 修回日期:2020-05-20 接受日期:2020-05-20 出版日期:2020-05-31 发布日期:2020-05-20
通讯作者: 张玉州
作者简介:张玉州（通讯作者）,男,1976生，教授.研究方向:系统建模及优化、进化计算、智能交通.E-mail: yzhzhang@mail.ustc.edu.cn
基金资助:
安徽省自然科学基金面上项目（1808085MF173，1908085MF194），安徽省高校省级自然科学研究重点项目（KJ2016A438，KJ2019A0554）资助.

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

ZHANG Yuzhou, ZHANG Ziwei

School of Computer and Information, Anqing Normal University, Anqing 246133, China

Received:2019-07-30 Revised:2020-05-20 Accepted:2020-05-20 Online:2020-05-31 Published:2020-05-20

摘要/Abstract

摘要： 随着经济的持续发展和城镇化进程的快速推进，城市生活垃圾的产出量越来越多，垃圾处理成本不断增大，其中垃圾收运成本占据相当大的比例，为此分析了一种实际生活中复杂的垃圾收运问题——多回收站点的垃圾收运问题(multi-station refuse collection problem，MSRCP)，并将其映射为多中心车辆调度问题，从而建立了以最小车辆运输费用为目标的多回收站垃圾收运问题模型.依据MSRCP的特点，设计了一种基于协同进化(cooperative co-evolutionary，CC)作为外部框架的问题求解方法. 首先使用改进聚类算法，将各垃圾收集点分配至合适的回收站点，从而将MSRCP转换成若干单回收点的垃圾收运问题.以各回收站点为中心，采用一种混合遗传算法(hybrid genetic algorithm，HGA)进行车辆路径规划.最后，以安庆市大观区生活垃圾收运为例进行了上述模型及其算法的验证，结果表明，该算法在降低复杂垃圾收运的运输费用时，具有良好的性能.

关键词: 垃圾收运问题, 多回收站点, 合作协同进化, 聚类算法, 遗传算法

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

中图分类号:

TP301

张玉州，张子为. 基于合作协同进化的多回收站点垃圾收运问题求解[J]. 中国科学技术大学学报, 2020, 50(5): 695-704.

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.

参考文献

［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]	于晓雨，毕秀春，张曙光. 配对交易的最优阈值[J]. 中国科学技术大学学报, 2020, 50(6): 784-792.
[2]	李二超，赵雨萌. 基于参考点的时变参数不可测对象PID控制器优化设计[J]. 中国科学技术大学学报, 2019, 49(2): 125-131.
[3]	王佳玉，张振宇，褚征，吴晓红. 一种基于轨迹数据密度分区的分布式并行聚类方法[J]. 中国科学技术大学学报, 2018, 48(1): 47-56.
[4]	徐雪丽，赵学靖. 稀疏谱聚类算法在高维数据上的应用[J]. 中国科学技术大学学报, 2017, 47(4): 311-319.
[5]	尤海峰，王喜玮，徐翔，王煦法. 一种多用户交互式遗传算法及其在群体设计中的应用[J]. 中国科学技术大学学报, 2010, 40(4): 425-430.

基于合作协同进化的多回收站点垃圾收运问题求解

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价