Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (3): 309-320.DOI: 10.3778/j.issn.1002-8331.2210-0197

• Engineering and Applications • Previous Articles     Next Articles

Optimization of Location-Routing for Collection Center Under Smart Waste Collection

MA Yanfang, JIA Jiapeng, LI Zongmin, YAN Fang   

  1. 1.School of Economics and Management, Hebei University of Technology, Tianjin 300401, China
    2.School of Business, Sichuan University, Chengdu 610064, China
    3.School of Economics and Management, Chongqing Jiaotong University, Chongqing 400074, China
    4.Chongqing Environmental & Sanitation Group, Chongqing 401137, China
  • Online:2024-02-01 Published:2024-02-01



  1. 1.河北工业大学 经济管理学院,天津 300401
    2.四川大学 商学院,成都 610064
    3.重庆交通大学 经济管理学院,重庆 400074
    4.重庆市环卫集团,重庆 401137

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)

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

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