ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

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

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

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2020.05.018
  • Received Date: 30 July 2019
  • Accepted Date: 20 May 2020
  • Rev Recd Date: 20 May 2020
  • Publish Date: 31 May 2020
    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.

    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.
    • FullText(HTML)
  • loading
    • References(23)
  • [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.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.)
    Recommended articles
    TrendMD
    Volume 50 Issue 5 page: 695-704
    Cover

    Article Metrics

    Article views (48) PDF downloads(270)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return