多约束条件下城市道路环卫车优化配置与路径规划

doi:10.16097/j.cnki.1009-6744.2022.05.028

交通运输系统工程与信息 ›› 2022, Vol. 22 ›› Issue (5): 273-284.DOI: 10.16097/j.cnki.1009-6744.2022.05.028

多约束条件下城市道路环卫车优化配置与路径规划

聂庆慧¹，龙秀江¹，梁程¹，夏井新²，欧吉顺^*1

1. 扬州大学，建筑科学与工程学院，江苏扬州 225127；2. 东南大学，智能运输系统研究中心，南京 211189

收稿日期:2022-07-27 修回日期:2022-08-28 接受日期:2022-08-31 出版日期:2022-10-25 发布日期:2022-10-22
作者简介:聂庆慧(1986- )，女，江苏扬州人，讲师，博士。
基金资助:
国家自然科学基金；全国统计科学研究项目。

Optimal Allocation and Routing of Sanitation Vehicles on Urban Roads Under Multiple Constraints

NIE Qing-hui¹, LONG Xiu-jiang¹, LIANG Cheng¹, XIA Jing-xin², OU Ji-shun^*1

1. College of Architectural Science and Engineering, Yangzhou University, Yangzhou 225127, Jiangsu, China; 2. Intelligent Transportation System Research Center, Southeast University, Nanjing 211189, China

Received:2022-07-27 Revised:2022-08-28 Accepted:2022-08-31 Online:2022-10-25 Published:2022-10-22
Supported by:
National Natural Science Foundation of China (71871005)；National Statistical Science Research Program of China (2020LY049)。

摘要/Abstract

摘要： 为有效解决当前城市环卫车调度决策过度依赖人工主观经验造成的车辆配置不合理和作业效率低下问题，本文提出一种多约束条件下的城市道路环卫车优化配置与路径规划方法。通过综合考虑环卫车在现实作业中的作业时限、服务次数、行驶速度和车辆退出节点等多种约束条件，将物理道路网络拓展为时空网络，刻画车辆在路网上的时空运行轨迹，进而将环卫车优化配置与路径规划问题从数学上描述为带多类约束条件的弧路径问题(Arc Routing Problem, ARP)。在此基础上，构建以车辆配置与出行总成本最小化为目标函数的环卫车优化配置与路径规划模型，并通过设计分支定价算法精确求解模型。将所提方法应用于苏州工业园区19个区域路网的环卫车辆配置与调度管理，从经济成本、作业效率和环保效益这3方面评估所提方法的可行性和有效性。结果表明：本文所提方法能够显著节约环卫运营成本，提升环卫车辆作业效率；同时，可有效降低环卫车辆碳排放量，形成良好的经济和社会效益，为智慧环卫提供了行之有效的新方案。

关键词: 交通工程, 组合优化, 分支定价, 弧路径问题, 时空网络, 智慧环卫

Abstract: To avoid unreasonable vehicle allocation caused by excessive manual experience in the urban sanitation vehicle dispatching problem, this paper proposes an approach for optimal allocation and routing of sanitation vehicles on urban roads under multiple constraints. First, multiple constraints in sanitation vehicle routing are comprehensively considered, including operation time limit, service time limit on links, driving speed limit, and vehicle exiting of the road network. The travel trajectory of each vehicle is described from time and space dimensions by expanding the physical road network into a time- space network. The optimal allocation and routing of sanitation vehicles are then described as an Arc Routing Problem (ARP) with multiple constraints. A mathematical model for minimizing the total vehicle ownership cost and travel time cost is developed. A branch-and-price algorithm is designed to solve the model accurately. The proposed approach was evaluated using 19 realistic instance networks in Industrial Park, Suzhou, China. The feasibility and effectiveness of the proposed approach were validated from three aspects, including economic cost, operational efficiency, and environmental benefit. The experimental results show that the proposed approach can significantly save the cost of sanitation operation and management while improving the travel efficiency of sanitation vehicles. Meanwhile, it is also capable of reducing carbon emissions effectively, forming good economic and social benefits and therefore providing a potential solution for smart sanitation.

Key words: traffic engineering, combinatorial optimization, branch-and-price, arc routing problem, time-space network, smart sanitation

中图分类号:

U491.1

聂庆慧, 龙秀江, 梁程, 夏井新, 欧吉顺. 多约束条件下城市道路环卫车优化配置与路径规划[J]. 交通运输系统工程与信息, 2022, 22(5): 273-284.

NIE Qing-hui, LONG Xiu-jiang, LIANG Cheng, XIA Jing-xin, OU Ji-shun. Optimal Allocation and Routing of Sanitation Vehicles on Urban Roads Under Multiple Constraints[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 273-284.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/10.16097/j.cnki.1009-6744.2022.05.028

http://www.tseit.org.cn/CN/Y2022/V22/I5/273

参考文献

[1] 柴获, 何瑞春, 苏江省, 等. 求解双目标带时间窗车辆路径问题的蚁群算法[J]. 交通运输系统工程与信息, 2018, 18(4): 156-162. [CHAI H, HE R C, SU J S, et al. An ant colony optimization for the bi-objective vehicle routing problem with time windows on mutilgrap[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 156-162.]

[2] BIANCHESSI N, CORBERAN Á, PLANA I, et al. The min-max close-enough arc routing problem[J]. European Journal of Operational Research, 2022, 300(3): 837-851.

[3] CHEN L, HA M H, LANGEVIN A, et al. Optimizing road network daily maintenance operations with stochastic service and travel times[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 64: 88- 102.

[4] QUIRION-BLAIS O, LANGEVIN A, TREPANIER M. A case study of combined winter road snow plowing and deicer spreading[J]. Canadian Journal of Civil Engineering, 2017, 44(12): 1005-1013.

[5] WILLEMSE E J, JOUBERT J W. Efficient local search strategies for the mixed capacitated arc routing problems under time restrictions with intermediate facilities[J]. Computers & Operations Research, 2019, 105: 203-225.

[6] HUANG S H, LIN T H. Using ant colony optimization to solve periodic arc routing problem with refill points[J]. Journal of Industrial and Production Engineering, 2014, 31(7): 441-451.

[7] CHEN L, GENDREAU M, HA M H, et al. A robust optimization approach for the road network daily maintenance routing problem with uncertain service time [J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 85: 40-51.

[8] RIAUELME-RODRIGUEZ J P, GAMACHE M, LANGEVIN A. Periodic capacitated arc-routing problem with inventory constraints[J]. Journal of the Operational Research Society, 2014, 65(12): 1840-1852.

[9] MOFID-NAKHAEE E, BARZINPOUR F. A multicompartment capacitated arc routing problem with intermediate facilities for solid waste collection using hybrid adaptive large neighborhood search and whale algorithm[J]. Waste Management & Research, 2019, 37 (1): 38-47.

[10] 陈博晓, 陈璐. 带服务水平和容量约束的区域规划问题研究[J]. 工业工程与管理, 2017, 22(4): 120-126. [CHEN B X, CHEN L. Capacitated service sector designing model algorithm with service level constraints [J]. Industrial Engnieering and Management, 2017, 22 (4): 120-126.]

[11] 边展, 徐奇, 靳志宏. 带时间窗的甩挂运输路径优化问题研究[J]. 交通运输系统工程与信息, 2018, 18(2): 183-193, 207. [BIAN Z, XU Q, JIN Z H. Optimization on the truck-trailer routing problem with time window constraints[J]. Journal of Traffic and Transportation Engineering, 2018, 18(2): 183-193, 207.]

[12] JIN J G, MENG Q, WANG H. Feeder vessel routing and transshipment coordination at a congested hub port[J]. Transportation Research Part B: Methodological, 2021, 151: 1-21.

[13] CORBERAN Á, EGLESE R, HASLE G, et al. Arc routing problems: A review of the past, present, and future[J]. Networks, 2021, 77(1): 88-115.

[14] 江苏省住房和城乡建设厅. 城市道路环卫机械化作业质量标准(DGJ32/TJ 172-2014)[S]. 南京: 江苏凤凰科学技术出版社, 2014. [Jsszfhcxxst Jiangsu Gov Cn. Quality standard for environmental sanitation mechanized operation of city road (DGJ32/TJ 172-2014) [S]. Nanjing: Phoenix Science Press, 2014.]

[15] 中华人民共和国住房和城乡建设部. 城市道路工程设计规范(CJJ37-2012)[S]. 北京: 中国建筑工业出版社, 北京市市政工程设计研究院, 2016. [Ministry of Housing and Urban-Rural Development the People's Republic of China. Code for design of urban road engineering (CJJ37-2012)[S]. Beijing: China Architecture & Building Press, Beijing General Municipal Engineering Design & Research Institute, 2016.

[16] BARTH M, SCORA G, YOUNGLOVE T. Modal emissions model for heavy-duty diesel vehicles[J]. Transportation Research Record, 2004, 1880(1): 10-20.

[17] DEMIR E, BEKTAS T, LAPORTE G. An adaptive large neighborhood search heuristic for the pollution-routing problem[J]. European Journal of Operational Research, 2012, 223(2): 346-359.

[18] 蔡博峰, 朱松丽, 于胜民, 等.《IPCC 2006 年国家温室气体清单指南 2019 修订版》解读[J]. 环境工程, 2019, 37(8): 1-11. [CAI B F, ZHU S L, YU S M, et al. The interpretation of 2019 refinement to the 2006 IPCC guidelines for national greenhouse gas inventory[J]. Environmental Engineering, 2019, 37(8): 1-11.]

多约束条件下城市道路环卫车优化配置与路径规划

Optimal Allocation and Routing of Sanitation Vehicles on Urban Roads Under Multiple Constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	郭凤香, 曲思柔, 万华森, 陈瑶, 李京阳. 分心驾驶研究文献计量学分析[J]. 交通运输系统工程与信息, 2022, 22(6): 26-39.
[2]	马书红, 陈西芳, 武亚俊, 邵恒, 张俊杰. 基于可达性的城市群交通网络公平性分析[J]. 交通运输系统工程与信息, 2022, 22(6): 51-59.
[3]	单肖年, 万长薪, 李志斌, 张小丽, 曹昌衡. 智能网联环境下多车道异质交通流建模与仿真[J]. 交通运输系统工程与信息, 2022, 22(6): 74-84.
[4]	陈丰, 赵岁阳, 宋明涛. 考虑路面车辙的自动驾驶卡车高速公路车道管理策略研究[J]. 交通运输系统工程与信息, 2022, 22(6): 95-104.
[5]	吕彪, 谢智宇, 康宇翔, 赵雨萌. 基于动态分流元胞传输模型的城市道路网络韧性评估[J]. 交通运输系统工程与信息, 2022, 22(6): 134-143.
[6]	朱兴林, 姚亮, 刘泓君, 叶拉森∙库肯, 艾力∙斯木吐拉. 考虑驾驶风格差异的高原公路危险路段识别研究[J]. 交通运输系统工程与信息, 2022, 22(6): 172-182.
[7]	戢晓峰, 戴秉佑, 普永明, 郝京京. 基于生存分析的山区双车道公路超车持续时间模型[J]. 交通运输系统工程与信息, 2022, 22(6): 183-190.
[8]	覃文文, 李欢, 李武, 谷金晶, 戢晓峰. 货车驾驶人驾驶行为与行车安全研究进展[J]. 交通运输系统工程与信息, 2022, 22(5): 55-74.
[9]	徐进, 杨子邈, 陈钦, 陈正委. 基于电子不停车收费数据的山区高速公路车速分布与车型分类研究[J]. 交通运输系统工程与信息, 2022, 22(5): 75-84.
[10]	马庆禄, 牛圣平, 曾皓威, 段学锋. 网联环境下混合交通流偶发拥堵演化机理研究[J]. 交通运输系统工程与信息, 2022, 22(5): 97-106.
[11]	胡立伟, 吕一帆, 赵雪亭, 薛宇, 张成杰, 雷国庆, 刘凡. 基于数据驱动的交通事故伤害程度影响因素及其耦合关系研究[J]. 交通运输系统工程与信息, 2022, 22(5): 117-124.
[12]	林培群, 曾维嘉, 周楚昊, 庞崇浩. 新冠疫情防控对大湾区高速公路运输的影响分析[J]. 交通运输系统工程与信息, 2022, 22(5): 318-327.
[13]	焦朋朋, 李汝鉴, 王健宇, 葛浩菁, 陈越. 考虑潜在类别的老年行人交通事故严重程度致因分析[J]. 交通运输系统工程与信息, 2022, 22(5): 328-336.
[14]	袁振洲, 陈思媛, 吴玥琳, 李浩然, 肖清榆. 考虑行驶时间不确定性的合乘路径鲁棒优化方法[J]. 交通运输系统工程与信息, 2022, 22(5): 233-242.
[15]	任其亮, 徐韬, 程龙春. 基于射频数据的道路交通流路径识别优化模型[J]. 交通运输系统工程与信息, 2022, 22(4): 89-95.