中国管理科学 >
2025 , Vol. 33 >Issue 10: 86 - 97
DOI: https://doi.org/10.16381/j.cnki.issn1003-207x.2023.0050
基于分类垃圾收运时效性的多周期多车舱路径优化研究
收稿日期: 2023-01-10
修回日期: 2023-03-11
网络出版日期: 2025-10-24
基金资助
国家自然科学基金项目(62573245);教育部哲学社会科学实验室专项基金项目(H0124709);南开大学亚洲研究中心项目(AS2405)
A Multi-period Multi-compartment Vehicle Routing Problem for Sorted-waste Collection with Timeliness
Received date: 2023-01-10
Revised date: 2023-03-11
Online published: 2025-10-24
随着城市生活垃圾量的急剧增加,分类收运正逐渐成为垃圾分类政策有效实施的关键。本文针对分类垃圾收运的时效性、收运车辆的多舱性等特征,以总成本最小为目标,构建了多周期多车舱垃圾分类收运车辆路径优化模型。根据问题特性,提出了一种基于两阶段的改进自适应大邻域搜索算法。其中,设计了周期相似算子以调整垃圾收运周期,联合收运插入算子以优化周期内多舱车收运路径。最后,通过不同规模算例和实际案例进行对比分析,验证了模型和算法的有效性及高效性。
关键词: 分类垃圾收运; 多周期; 多车舱; 自适应大邻域搜索算法
肖建华 , 张文雪 , 潘钰雅 , 肖久红 , 牛云云 . 基于分类垃圾收运时效性的多周期多车舱路径优化研究[J]. 中国管理科学, 2025 , 33(10) : 86 -97 . DOI: 10.16381/j.cnki.issn1003-207x.2023.0050
With the acceleration of urbanization and the enhancement of material living standards, abundant human activities have generated massive urban domestic waste, which has brought severe challenges and threats to sustainable social development and human health. Consequently, many municipal governments in China have successively promulgated policies to promote the implementation of waste sorting. Especially, sorted-waste collection, as an indispensable part of waste sorting, has attracted more attention from the academic community over recent years.In this paper, a novel multi-period sorted-waste collection routing optimization problem for multi-compartment vehicles (MPMCVRP) is proposed, with the objective of minimizing cost. Specially, the MPMCVRP takes into account the advantages of heterogeneous fleets and the difference in storage times between distinct wastes due to their unique properties, thereby making the route planning more realistic. To solve the proposed model, an extended two-stage adaptive large neighborhood search algorithm (EALNS) is developed. In the EALNS, a new period similarity operator is designed to adjust the waste collection period, and a new joint collection insertion operator is presented to optimize the within-period multi-compartment vehicle collection path.To confirm the effectiveness of the EALNS, it is compared with CPLEX on small-scale benchmarks, followed by comparison with the classical heuristic algorithms on medium- and large-scale benchmarks. Furthermore, a series of comparison experiments is implemented to demonstrate the significance of the MPMCVRP from the perspective of employing multi-compartment vehicles and multi-period joint planning. Finally, the proposed MPMCVRP and EALNS are used in a real case to confirm their practicability. In summary, a good foundation for further research is provided.
| [1] | 李明月, 李俐频, 左薇, 等. 基于GIS与改进蚁群算法的垃圾收运路径规划[J]. 环境工程学报, 2022, 16(7): 2388-2396. |
| Li M Y, Li L P, Zuo W, et al. Garbage collection and transportation path planning based on GIS and improved ant colony algorithm[J]. Chinese Journal of Environmental Engineering, 2022, 16(7): 2388-2396. | |
| [2] | 牟能冶, 程驰尧, 蒋尔伟, 等. 基于多车型多行程的城市生活垃圾分类运输路径优化[J]. 安全与环境学报, 2022, 22(4): 2199-2208. |
| Mu N Y, Cheng C Y, Jiang E W, et al. Urban solid waste classification and transportation path optimization based on multi-vehicle and multi-journey[J]. Journal of Safety and Environment, 2022, 22(4): 2199-2208. | |
| [3] | Reed M, Yiannakou A, Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem[J]. Applied Soft Computing, 2014, 15: 169-176. |
| [4] | Henke T, Speranza M G, W?scher G. The multi-compartment vehicle routing problem with flexible compartment sizes[J]. European Journal of Operational Research, 2015, 246(3): 730-743. |
| [5] | Henke T, Speranza M G, W?scher 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. |
| [6] | Erdem M. Optimisation of sustainable urban recycling waste collection and routing with heterogeneous electric vehicles[J]. Sustainable Cities and Society, 2022, 80: 103785. |
| [7] | Yang J, Tao F, Zhong Y. Dynamic routing for waste collection and transportation with multi-compartment electric vehicle using smart waste bins[J]. Waste Management & Research, 2022, 40(8): 1199-1211. |
| [8] | 孙丽君, 周雅娴, 滕玥, 等. 多车舱车辆路径问题的研究现状与发展[J].系统工程理论与实践,2021,41(6): 1535-1546. |
| Sun L J, Zhou Y X, Teng Y, et al. Multi-compartment vehicle routing problem: Status and perspectives[J]. Systems Engineering-Theory & Practice, 2021, 41(6): 1535-1546. | |
| [9] | Ostermeier M, Henke T, Hübner A, et al. Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions[J]. European Journal of Operational Research, 2021, 292(3): 799-817. |
| [10] | 闫芳, 张燕红, 柴福良. 垃圾分类背景下城市生活垃圾多级转运网络优化[J]. 重庆师范大学学报(自然科学版), 2022, 39(4): 1-11. |
| Yan F, Zhang Y H, Chai F L. Multi-stage transport network optimization of considering the municipal solid waste classification[J]. Journal of Chongqing Normal University (Natural Science), 2022, 39(4): 1-11. | |
| [11] | Aydemir-Karadag A. Bi-objective adaptive large neighborhood search algorithm for the healthcare waste periodic location inventory routing problem[J]. Arabian Journal for Science and Engineering, 2022,47(3): 3861-3876. |
| [12] | 尚春剑, 马良, 刘勇. 垃圾分类下带时间窗异构周期性混合车辆路径问题模型及算法[J]. 系统工程, 2021, 39(6): 131-145. |
| Shang C J, Ma L, Liu Y. The model and algorithm of heterogeneous periodic hybrid vehicle routing problem with time window under garbage classification[J]. Systems Engineering, 2021, 39(6): 131-145. | |
| [13] | Elbek M, W?hlk S. A variable neighborhood search for the multi-period collection of recyclable materials[J]. European Journal of Operational Research, 2016, 249(2): 540-550. |
| [14] | Shaw P. Using constraint programming and local search methods to solve vehicle routing problems[M]//Maher M, Puget J F. Principles and Practice of Constraint Programming— CP98, Berlin, Heidelberg: Springer Berlin Heidelberg, 1998: 417-431. |
| [15] | Fang Z, Tu W, Li Q, et al. A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems[J]. International Journal of Geographical Information Science, 2013, 27(4): 741-764. |
| [16] | Hübner A, Ostermeier M. A multi-compartment vehicle routing problem with loading and unloading costs[J]. Transportation Science, 2018, 53(1): 282-300. |
| [17] | Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4): 455-472. |
| [18] | Alinaghian M, Shokouhi N. Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search[J]. Omega, 2018, 76: 85-99. |
| [19] | Mancini S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: Formulation and adaptive large neighborhood search based matheuristic[J].Transportation Research Part C: Emerging Technologies, 2016, 70: 100-112. |
| [20] | Coelho L C, Cordeau J F, Laporte G. The inventory-routing problem with transshipment[J]. Computers & Operations Research, 2012, 39(11): 2537-2548. |
| [21] | Gu W, Cattaruzza D, Ogier M, et al. Adaptive large neighborhood search for the commodity constrained split delivery VRP[J]. Computers & Operations Research, 2019, 112: 104761. |
| [22] | Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581. |
| [23] | Cornillier F, Boctor F F, Laporte G, et al. A heuristic for the multi-period petrol station replenishment problem[J]. European Journal of Operational Research, 2008, 191(2): 295-305. |
| [24] | Hemmelmayr V C, Doerner K F, Hartl R F. A variable neighborhood search heuristic for periodic routing problems[J].European Journal of Operational Research, 2009, 195(3): 791-802. |
| [25] | Popovi? D, Vidovi? M, Radivojevi? G. Variable Neighborhood Search heuristic for the Inventory Routing Problem in fuel delivery[J]. Expert Systems with Applications, 2012, 39(18): 13390-13398. |
/
| 〈 |
|
〉 |