考虑负效应的垃圾回收两级选址‒路径模型与算法

doi:10.11772/j.issn.1001-9081.2021111969

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (1): 289-298.DOI: 10.11772/j.issn.1001-9081.2021111969

考虑负效应的垃圾回收两级选址‒路径模型与算法

马艳芳¹, 张文¹, 李宗敏², 闫芳^3,4, 郭凌云¹

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

收稿日期:2021-11-15 修回日期:2022-05-09 发布日期:2022-06-08
通讯作者: 闫芳（1985—），女，河南开封人，副教授，博士，主要研究方向：运输配送与优化算法 email：yanfang@cqjtu.edu.cn；
作者简介:马艳芳（1986—），女，河北保定人，副教授，博士，主要研究方向：物流与供应链管理；张文（1997—），女，河南许昌人，硕士研究生，主要研究方向：物流与供应链管理；李宗敏（1987—），女，四川成都人，教授，博士，主要研究方向：决策理论与方法；郭凌云（1988—），女，山西临汾人，讲师，博士，主要研究方向：大数据营销；
基金资助:
国家自然科学基金资助项目（72174134， 72202056）；国家社会科学基金后期资助项目（21FGLB032）；河北省自然科学基金资助项目（G2020202008）；四川省哲学社会科学规划项目（SC22EZD048）。

Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect

MA Yanfang¹, ZHANG Wen¹, LI Zongmin², YAN Fang^3,4, GUO Lingyun¹

1.School of Economics and Management， Hebei University of Technology， Tianjin 300401， China
2.Business School， Sichuan University， Chengdu Sichuan 610064， China
3.School of Economics and Management， Chongqing Jiaotong University， Chongqing 400074， China
4.Chongqing Environmental and Sanitation Group Company Limited， Chongqing 401121， China

Received:2021-11-15 Revised:2022-05-09 Online:2022-06-08
Contact: YAN Fang， born in 1985， Ph. D.， associate professor. Her research interests include transportation distribution and optimization algorithm.
About author:MA Yanfang，born in 1986， Ph. D.， associate professor. Her research interests include logistics and supply chain management；ZHANG Wen， born in 1997， M. S. candidate. Her research interests include logistics and supply chain management；LI Zongmin， born in 1987， Ph. D.， professor. Her research interests include decision theory and methods；Yanfang， born in 1986， Ph. D.， associate professor. Her research interests include logistics and supply chain management；GUO Lingyun， born in 1988， Ph. D.， lecturer. Her research interests include big data marketing；
Supported by:
This work is partially supported by National Natural Science Foundation of China （72174134，72202056）， Latter Project of National Social Science Foundation of China （21FGLB032），Natural Science Foundation of Hebei Province （G2020202008），Sichuan Provincial Philosophy and Social Sciences Plan （SC22EZD048）.

摘要/Abstract

摘要： 针对生活垃圾中转站和焚烧站的选址?路径问题（LRP），考虑经济目标和垃圾设施的负面影响，设计了与风向和距离有关的负效应分段函数，构建了两级多目标选址?路径（2E-MOLRP）模型，并提出了鲸鱼优化算法（WOA）和模拟退火（SA）算法结合的非支配算法WOA-SA。首先，结合随机方法与Clarke和Wright（CW）节约算法优化初始种群；其次，采用非线性动态惯性权重系数调整收敛速度；然后，设计WOA-SA的并行结构来增强全局搜索能力；最后，使用非支配排序法得到帕累托解集。对Prins和Barreto等35个基准案例以及天津市模拟案例进行分析。结果表明，WOA-SA可以找到20个基准案例的已知最优解（BKS），且对Prins和Barreto案例的求解结果与BSK差距的平均值分别为0.37%和0.08%，具有很好的收敛性和稳定性。将所提模型和算法应用于实例，给决策者提供了三种不同方案的负效应值及经济成本的方案，以支持不同偏好决策者选择，从而减少垃圾回收物流成本和设施对环境的负面影响。

关键词: 两级选址?路径问题, 多目标优化, 负效应, 鲸鱼优化算法, 生活垃圾

Abstract: With regard to the Location-Routing Problem （LRP） of domestic waste transfer stations and incineration stations， by considering the economic objective and the obnoxious effect of waste facilities， a piecewise function of obnoxious effect related to wind direction and distance was designed， a Two-Echelon Multi-Objective LRP （2E-MOLRP） model was formulated， and a non-dominated algorithm combining Whale Optimization Algorithm （WOA） and Simulated Annealing （SA） algorithm was proposed， namely WOA-SA. Firstly， the random method and Clarke and Wright （CW） saving algorithm were used to optimize the initial population. Secondly， a nonlinear dynamic inertia weight coefficient was adopted to adjust the convergence speed of the WOA-SA. Thirdly， the global optimization ability was enhanced by designing the parallel structure of WOA-SA. Finally， the Pareto solution set was obtained by using the non-dominated sorting method. The analysis was carried out on 35 benchmark cases such as Prins and Barreto as well as a simulated case of Tianjin. The results show that the WOA-SA can find the Best Known Solution （BKS） of 20 benchmark cases， and has the mean values of the difference between the solution results and the BKSs of 0.37% and 0.08% on Prins and Barreto cases， which proves the good convergence and stability of the WOA-SA. The proposed model and algorithm were applied to the instance， and provided three schemes with different obnoxious effect values and economic costs for decision makers with different decision preferences. Therefore， the cost of waste recycling and the obnoxious effect of facilities on environment were reduced.

Key words: Two-Echelon Location-Routing Problem (2E-LRP), multi-objective optimization, obnoxious effect, Whale Optimization Algorithm (WOA), domestic waste

中图分类号:

TP301.6

马艳芳, 张文, 李宗敏, 闫芳, 郭凌云. 考虑负效应的垃圾回收两级选址‒路径模型与算法[J]. 计算机应用, 2023, 43(1): 289-298.

MA Yanfang, ZHANG Wen, LI Zongmin, YAN Fang, GUO Lingyun. Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect[J]. Journal of Computer Applications, 2023, 43(1): 289-298.

参考文献

1 LIU Z Y， LI Z， CHEN W M， et al. Path optimization of medical waste transport routes in the emergent public health event of COVID-19： a hybrid optimization algorithm based on the immune-ant colony algorithm［J］. International Journal of Environmental Research and Public Health， 2020， 17（16）： No.5831. 10.3390/ijerph17165831
2 BABAEE TIRKOLAEE E， ABBASIAN P， WEBER G W. Sustainable fuzzy multi-trip location-routing problem for medical waste management during the COVID-19 outbreak［J］. Science of the Total Environment， 2020， 756： No.143607. 10.1016/j.scitotenv.2020.143607
3 赵佳虹，凌雅婷. 新冠疫情下医疗废物管理的选址?分配优化［J］. 交通科技与经济， 2020， 22（6）： 1-7， 22. ZHAO J H， LING Y T. The optimization of medical waste location-allocation under the COVID-19 epidemic［J］. Technology and Economy in Areas of Communications， 2020， 22（6）： 1-7， 22.
4 JACOBSEN S K， MADSEN O B G. A comparative study of heuristics for a two-level routing-location problem［J］. European Journal of Operational Research， 1980， 5（6）： 378-387. 10.1016/0377-2217(80)90124-1
5 MARQUES G， SADYKOV R， DESCHAMPS J C， et al. An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem［J］. Computers and Operations Research， 2020， 114： No.104833. 10.1016/j.cor.2019.104833
6 DARVISH M， ARCHETTI C， COELHO L C， et al. Flexible two-echelon location routing problem［J］. European Journal of Operational Research， 2019， 277（3）： 1124-1136. 10.1016/j.ejor.2019.04.002
7 AMIRI M， AMIN S H， TAVAKKOLI-MOGHADDAM R. A Lagrangean decomposition approach for a novel two-echelon node-based location-routing problem in an offshore oil and gas supply chain［J］. Transportation Research， 2019， 128（8）： 96-114. 10.1016/j.tre.2019.05.014
8 马艳芳，应斌，周晓阳，等. 基于冲突合作关系的生鲜选址?路径多主体优化模型与算法［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 and Practice， 2020， 40（12）： 3194-3209.
9 胡大伟，刘成清，胡卉.等. 基于低碳视角的两阶段开放式选址路径问题——油车与电动车对比［J］. 系统工程理论与实践， 2020， 40（12）： 3230-3242. HU D W， LIU C Q， HU H， et al. The two echelon open location routing problem based on low carbon perspective — fuel vehicles vs electric vehicles［J］. Systems Engineering — Theory and Practice， 2020， 40（12）： 3230-3242.
10 XIN X， JIANG Q Q， LI S H， et al. Energy-efficient scheduling for a permutation flow shop with variable transportation time using an improved discrete whale swarm optimization［J］. Journal of Cleaner Production， 2021， 293： No.126121. 10.1016/j.jclepro.2021.126121
11 ZENG N Y， SONG D D， LI H， et al. A competitive mechanism integrated multi-objective whale optimization algorithm with differential evolution ［J］. Neurocomputing， 2021， 432： 170-182. 10.1016/j.neucom.2020.12.065
12 董海，吴瑶，齐新娜. 基于改进鲸鱼优化算法的血液供应链网络多目标鲁棒优化设计［J］. 计算机应用， 2021， 41（10）： 3063-3069. 10.11772/j.issn.1001-9081.2020111729 DONG H， WU Y， QI X N. Multi-objective robust optimization design of blood supply chain network based on improved whale optimization algorithm［J］. Journal of Computer Applications， 2021， 41（10）： 3063-3069. 10.11772/j.issn.1001-9081.2020111729
13 TERAN-SOMOHANO A， SMITH A E. Locating multiple capacitated semi-obnoxious facilities using evolutionary strategies［J］. Computers and Industrial Engineering， 2019， 133： 303-316. 10.1016/j.cie.2019.05.014
14 MIRJALILI S， LEWIS A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95： 51-67. 10.1016/j.advengsoft.2016.01.008
15 KIRKPATRICK S， GELATT C D， Jr.， VECCHI M P. Optimization by simulated annealing［J］. Science， 1983， 220（4598）： 671-680. 10.1126/science.220.4598.671
16 MAFARJA M M， MIRJALILI S. Hybrid whale optimization algorithm with simulated annealing for feature selection［J］. Neurocomputing， 2017， 260： 302-312. 10.1016/j.neucom.2017.04.053
17 张顶学，关治洪，刘新芝. 一种动态改变惯性权重的自适应粒子群算法［J］. 控制与决策， 2008， 23（11）： 1253-1257. 10.3321/j.issn:1001-0920.2008.11.011 ZHANG D X， GUAN Z H， LIU X Z. Adaptive particle swarm optimization algorithm with dynamically changing inertia weight［J］. Control and Decision， 2008， 23（11）： 1253-1257. 10.3321/j.issn:1001-0920.2008.11.011
18 DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. 10.1109/4235.996017
19 NGUYEN V P， PRINS C， PRODHON C. A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem［J］. Engineering Applications of Artificial Intelligence， 2012， 25（1）： 56-71. 10.1016/j.engappai.2011.09.012
20 BARRETO S， FERREIRA C， PAIX?O J， et al. Using clustering analysis in a capacitated location-routing problem［J］. European Journal of Operational Research， 2007， 179（3）： 968-977. 10.1016/j.ejor.2005.06.074
21 NGUYEN V P， PRINS C， PRODHON C. Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking［J］. European Journal of Operational Research， 2012， 216（1）： 113-126. 10.1016/j.ejor.2011.07.030
22 PICHKA K， BAJGIRAN A H， PETERING M E H， et al. The two echelon open location routing problem： mathematical model and hybrid heuristic［J］. Computers and Industrial Engineering， 2018， 121： 97-112. 10.1016/j.cie.2018.05.010
23 FAN H M， WU J X， LI X， et al. Presenting a multi-start hybrid heuristic for solving the problem of Two-Echelon Location-Routing Problem with Simultaneous Pickup and Delivery （2E-LRPSPD）［J］. Journal of Advanced Transportation， 2020， 2020： No.9743841. 10.1155/2020/9743841
24 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］. 4OR — A Quarterly Journal of Operations Research， 2006， 4（3）： 221-238. 10.1007/s10288-006-0001-9
25 ALMOUHANNA A， QUINTERO-ARAUJO C L， PANADERO J， et al. The location routing problem using electric vehicles with constrained distance［J］. Computers and Operations Research， 2020， 115： No.104864. 10.1016/j.cor.2019.104864

[1]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[2]	孙林, 黄金旭, 徐久成. 基于邻域容差互信息和鲸鱼优化算法的非平衡数据特征选择[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1842-1854.
[3]	金苍宏, 邵育华, 何琴芳. 基于自适应群组重排的长尾推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1122-1128.
[4]	李兴佳, 杨秋辉, 洪玫, 潘春霞, 刘瑞航. 基于历史数据和多目标优化的测试用例排序方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 221-226.
[5]	张翔宇, 杨阳, 冯国徽, 秦川. 基于多目标优化的加密图像可逆信息隐藏[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1716-1723.
[6]	张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1516-1523.
[7]	张京, 朱爱红. 基于遗传算法和粒子群优化的列车自动驾驶速度曲线优化方法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 599-605.
[8]	郭潇, 李春山, 张宇跃, 初佃辉. 基于自适应多目标强化学习的服务集成方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3500-3505.
[9]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[10]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[11]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[12]	马晓航, 廖灵霞, 李智, 秦斌, 赵涵捷. 基于动态混合超时的软件定义网络多目标优化[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3658-3665.
[13]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[14]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.
[15]	童林, 官铮. 改进鲸鱼优化支持向量机的交通流量模糊粒化预测[J]. 计算机应用, 2021, 41(10): 2919-2927.

考虑负效应的垃圾回收两级选址‒路径模型与算法

Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics