智能垃圾回收下收集中心选址-路径二层优化

doi:10.3778/j.issn.1002-8331.2210-0197

摘要/Abstract

摘要： 随着技术的进步及环保意识的提升，智能垃圾箱逐渐流行起来，使得垃圾回收工作面临新考验。针对带容量约束的选址-路径问题，引入双商品流公式构建垃圾回收选址-路径多主体优化模型，其中上层智能回收企业以总成本最低为目标确定收集中心选址；下层外包运输公司依据回收阈值选择需访问的智能垃圾箱，规划回收路径并确保运输成本最小化。改进遗传算法求解该问题：上层采用聚类算法处理选址初始化；下层路径为随机生成和节约里程初始化；引入最优成本路线交叉和反向变异算子。选取Prins和Barreto算例集测试，并与BKS、GAPSO和BSA算法对比，结果与BKS的差距均值仅为0.419%；通过模拟实际案例验证智能垃圾收集路径方式可有效降低总成本，为解决智能垃圾回收背景下选址-路径问题提供决策支持。

关键词: 物联网, 选址-路径, 二层规划, 双商品流, 遗传算法

Abstract: With the rapid development of Internet of things technology and the improvement of public awareness of environmental protection, smart dustbins are gradually popular, making the waste recycling work face new challenges. Aiming at the location-routing problem with capacity constraints, a multi-agent optimization model of waste collection location-routing is constructed by introducing the two-commodity flow formulation. Smart recycling enterprise locates the collection center and aims to minimize the total cost in the upper level. Outsourcing transportation company selects the smart bins to be visited based on the recycling threshold, plans the recycling path and ensures that transportation costs are minimized in the lower level. An improved genetic algorithm is used to solve the problem: the upper layer uses clustering algorithm to determine the location of the collection center; the lower layer uses random generation and Clarke and Wright savings method to generate the initial population. And best-cost route crossover operator and inversion mutation operator are introduced. Based on Prins and Barreto benchmarks and compared with BKS, GAPSO and BSA, the average gap between the results and BKS is 0.419%. The smart waste collection routing method can effectively reduce the total cost, tested by simulating real cases, which provides decision support to solve the location-routing problem with capacity constraints in the context of smart waste collection.

Key words: Internet of things, location-routing, bi-level programming, two-commodity flow formulation, genetic algorithm（GA）

马艳芳, 贾佳鹏, 李宗敏, 闫芳. 智能垃圾回收下收集中心选址-路径二层优化[J]. 计算机工程与应用, 2024, 60(3): 309-320.

MA Yanfang, JIA Jiapeng, LI Zongmin, YAN Fang. Optimization of Location-Routing for Collection Center Under Smart Waste Collection[J]. Computer Engineering and Applications, 2024, 60(3): 309-320.

参考文献

[1] WAWALE S G, SHABAZ M, MEHBODNIYA A, et al. Biomedical waste management using IoT tracked and fuzzy classified integrated technique[J/OL]. Human-centric Computing and Information Sciences (2022-07-15) [2022-11-08]. https://doi.org/10.22967/HCIS.2022.12.032.
[2] ALQAHTANI F, AL-MAKHADMEH Z, TOLBA A, et al. Internet of things-based urban waste management system for smart cities using a cuckoo search algorithm[J]. Cluster Computing, 2020, 23(3): 1769-1780.
[3] PARDINI K, RODRIGUES J J P C, DIALLO O, et al. A smart waste management solution geared towards citizens[J]. Sensors, 2020, 20(8): 2380.
[4] RAMOS T R P, DE MORAIS C S, BARBOSA-PóVOA A P. The smart waste collection routing problem: alternative operational management approaches[J]. Expert Systems with Applications, 2018, 103: 146-158.
[5] GUTIERREZ J M, JENSEN M, HENIUS M, et al. Smart waste collection system based on location intelligence[J]. Procedia Computer Science, 2015, 61: 120-127.
[6] GILARDINO A, ROJAS J, MATTOS H, et al. Combining operational research and life cycle assessment to optimize municipal solid waste collection in a district in Lima (Peru)[J]. Journal of Cleaner Production, 2017, 156: 589-603.
[7] 马艳芳, 应斌, 周晓阳, 等. 基于冲突合作关系的生鲜选址-路径多主体优化模型与算法[J]. 系统工程理论与实践, 2020, 40(12): 3194-3209.
MA Y F, YING B, ZHOU X Y, et al. Multi-agent optimization model and algorithm for perishable food location-routing problem with conflict and coordination[J]. Systems Engineering-Theory & Practice, 2020, 40(12): 3194-3209.
[8] LEITE M R C O, BERNARDINO H S, GON?ALVES L B. A variable neighborhood descent with ant colony optimization to solve a bilevel problem with station location and vehicle routing[J]. Applied Intelligence, 2022, 52(7): 7070-7090.
[9] CHEN Y, BOUFERGUENE A, SHEN Y, et al. Bilevel decision-support model for bus-route optimization and accessibility improvement for seniors[J]. Journal of Computing in Civil Engineering, 2020, 34(2): 04019057.
[10] 任新惠, 王佳雪, 王梦琦. 考虑动态能耗的无人机配送选址路径规划研究[J]. 计算机工程与应用，2023，59（13）：273-280.
REN X H, WANG J X, WANG M Q. Research on drone distribution location-path planning considering dynamic energy consumption[J]. Computer Engineering and Applications，2023，59（13）：273-280.
[11] 万孟然, 叶春明, 董君, 等. 考虑备灾的双层规划应急资源调度选址路径优化模型与算法[J]. 计算机应用研究, 2021, 38(10): 2961-2967.
WAN M R, YE C M, DONG J, et al. Bi-level programming location-routing optimization model and algorithm for emergency resource scheduling considering preparedness[J]. Application Research of Computers, 2021, 38(10): 2961-2967.
[12] BLAZQUEZ C, PAREDES-BELMAR G. Network design of a household waste collection system: a case study of the commune of Renca in Santiago, Chile[J]. Waste Management, 2020, 116: 179-189.
[13] ARAGHI M E T, TAVAKKOLI-MOGHADDAM R, JOLAI F, et al. A green multi-facilities open location-routing problem with planar facility locations and uncertain customer[J]. Journal of Cleaner Production, 2021, 282: 124343.
[14] ZHOU L, LIN Y, WANG X, et al. Model and algorithm for bilevel multisized terminal location‐routing problem for the last mile delivery[J]. International Transactions in Operational Research, 2019, 26(1): 131-156.
[15] 王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.
WANG D P, XU Z, YANG C. Study on location-routing problem of logistics distribution based on two-stage heuristic algorithm[J]. Operations Research and Management Science, 2017, 26(4): 70-75.
[16] JAMMELI H, ARGOUBI M, MASRI H. A bi-objective stochastic programming model for the household waste collection and transportation problem: case of the city of Sousse[J]. Operational Research, 2021, 21(3): 1613-1639.
[17] OMBUKI B, ROSS B J, HANSHAR F. Multi-objective genetic algorithms for vehicle routing problem with time windows[J]. Applied Intelligence, 2006, 24(1): 17-30.
[18] ABDALLAH A M F M, ESSAM D L, SARKER R A. On solving periodic re-optimization dynamic vehicle routing problems[J]. Applied Soft Computing, 2017, 55: 1-12.
[19] BALDACCI R, HADJICONSTANTINOU E, MINGOZZI A. An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation[J]. Operations Research, 2004, 52(5): 723-738.
[20] Hà M H, BOSTEL N, LANGEVIN A, et al. An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices[J]. European Journal of Operational Research, 2013, 226(2): 211-220.
[21] Hà M H, BOSTEL N, LANGEVIN A, et al. An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size[J]. Computers & Operations Research, 2014, 43: 9-19.
[22] ZHAO J, KE G Y. Incorporating inventory risks in location-routing models for explosive waste management[J]. International Journal of Production Economics, 2017, 193: 123-136.
[23] MA Y, ZHANG W, FENG C, et al. A bi-level multi-objective location-routing model for municipal waste management with obnoxious effects[J]. Waste Management, 2021, 135: 109-121.
[24] MENDOZA J E, MEDAGLIA A L, VELASCO N. An evolutionary-based decision support system for vehicle routing: the case of a public utility[J]. Decision Support Systems, 2009, 46(3): 730-742.
[24] 梁静, 许波, 葛宇. 基于改进蛙跳策略的 Map-Reduce 作业调度算法[J]. 计算机应用研究, 2013, 30(7): 1999-2002.
LIANG J, XU B, GE Y. Map-Reduce job scheduling algorithm based on improved shuffled frog leaping strategy[J]. Application Research of Computers, 2013, 30(7): 1999-2002.
[26] PRINS C, PRODHON C, CALVO R W. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking[J]. A Quarterly Journal of Operations Research, 2006, 4(3): 221-238.
[27] BARRETO S, FERREIRA C, PAIXAO J, et al. Using clustering analysis in a capacitated location-routing problem[J]. European Journal of Operational Research, 2007, 179(3): 968-977.
[28] VINCENT F Y, NORMASARI N M E, CHEN W H. Location-routing problem with time-dependent demands[J]. Computers & Industrial Engineering, 2021, 151: 106936.
[29] SOLTANI A R, TAWFIK H, GOULERMAS J Y, et al. Path planning in construction sites: performance evaluation of the Dijkstra, A?, and GA search algorithms[J]. Advanced Engineering Informatics, 2002, 16(4): 291-303.