多通路时变网络下的车辆路径问题研究

doi:10.3778/j.issn.1002-8331.2401-0466

摘要/Abstract

摘要： 针对城市道路交通拥堵造成的车辆尾气污染问题以及物流企业竞争不断加剧的现状，研究多通路时变网络下考虑客户满意度的低碳车辆路径问题。构建考虑现实路网车速时变特性的多通路时变网络；考虑客户价值的差异性，对客户进行分类并提出相应的客户满意度评价标准；建立多通路时变网络下减少碳排放、降低车辆运输成本以及提高客户满意度的问题模型。根据模型特征，提出基于模拟退火算法（simulated annealing algorithm，SA）并结合邻域搜索和禁忌搜索思想的自适应混合模拟退火算法（adaptive?hybrid?simulated?annealing?algorithm，AHSA）。采用贪婪插入法构造初始解；设计可行解和不可行解禁忌表；使用路径内和路径间两类邻域搜索算子，并提出新的搜索策略；建立自适应搜索算子选择机制，并设计权重增量控制因子。使用Solomon标准测试数据集中的多组算例对AHSA进行测试，同时与多种算法进行对比，验证了AHSA的可行性和优越性，并通过实验证明了问题模型的合理性。

关键词: 车辆路径问题（VRP）, 多通路时变网络, 低碳, 客户满意度, 模拟退火, 自适应机制

Abstract: Aiming at the problem of vehicle exhaust pollution caused by urban road congestion and the increasing competition of logistics enterprises, the low-carbon vehicle routing problem considering customer satisfaction under multi-path time-varying network is studied. The multi-path time-varying network considering the time-varying characteristics of real road speed is constructed. Considering the difference of customer value, the customers are classified, and the corresponding customer satisfaction evaluation criteria are put forward. The problem model of reducing carbon emission, reducing vehicle transportation cost and improving customer satisfaction under multi-path time-varying network is established. According to the characteristics of the model, an adaptive hybrid simulated annealing algorithm (AHSA) based on simulated annealing algorithm (SA) combined with neighborhood search and tabu search is proposed. The greedy insertion method is used to construct the initial solution. Feasible solutions and infeasible solutions tabu tables are designed. Two kinds of neighborhood search operators, intra-path and inter-path are used, and a new search strategy is proposed. An adaptive search operator selection mechanism is established, and weight increment control factors are designed. Compared with many algorithms in Solomon standard test datasets, the feasibility and superiority of AHSA are verified, and the rationality of the problem model is proved by experiments.

Key words: vehicle routing problem (VRP), multi-path time-varying network, low-carbon, customer satisfaction, simulated annealing, adaptive mechanism

李珺, 朱利圆, 李若. 多通路时变网络下的车辆路径问题研究[J]. 计算机工程与应用, 2025, 61(10): 308-319.

参考文献

[1] 公安部. 全国机动车保有量达4.17亿辆驾驶人超过5亿人[EB/OL]. (2023-01-11)[2023-08-28]. https://www.gov.cn/xinwen/2023-01/11/content_5736278.htm.
Ministry of Public Security. The total number of motor vehicles in China has reached 417 million, driving more than 500 million people[EB/OL]. (2023-01-11)[2023-08-28]. https://www.gov.cn/xinwen/2023-01/11/content_5736278.htm.
[2] DEMIR E, BEKTA? T, LAPORTE G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transportation Research Part D: Transport and Environment, 2011, 16(5): 347-357.
[3] MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3): 185-200.
[4] ICHOUA S, GENDREAU M, POTVIN J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.
[5] POONTHALIR G, NADARAJAN R. A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP)[J]. Expert Systems with Applications, 2018, 100: 131-144.
[6] 付朝晖, 刘长石. 生鲜电商配送的开放式时变车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(1): 271-278.
FU Z H, LIU C S. Research on open time-dependent vehicle routing problem of fresh food E-commerce distribution[J]. Computer Engineering and Applications, 2021, 57(1): 271-278.
[7] 范厚明, 孙秀娜, 张跃光, 等. 时变路网下带混合时间窗的车辆路径问题[J]. 计算机工程与应用, 2022, 58(16): 292-302.
FAN H M, SUN X N, ZHANG Y G, et al. Vehicle routing problem with mixed time windows under time-dependent network[J]. Computer Engineering and Applications, 2022, 58(16): 292-302.
[8] 习江鹏, 张佳蕊, 董红霞, 等. 考虑需求变化与时变路网的同城货运路径优化[J]. 长安大学学报 (自然科学版), 2023, 43(4): 137-150.
XI J P, ZHANG J R, DONG H X, et al. Vehicle routing optimization of intra-city freight considering demand change and time-varying road network[J]. Journal of Chang’an University (Natural Science Edition), 2023, 43(4): 137-150.
[9] GARAIX T, ARTIGUES C, FEILLET D, et al. Vehicle routing problems with alternative paths: an application to on-demand transportation[J]. European Journal of Operational Research, 2010, 204(1): 62-75.
[10] BEHNKE M, KIRSCHSTEIN T. The impact of path selection on GHG emissions in city logistics[J]. Transportation Research Part E: Logistics and Transportation Review, 2017, 106: 320-336.
[11] 李顺勇, 但斌, 葛显龙. 多通路时变网络下低碳车辆路径优化模型与算法[J]. 计算机集成制造系统, 2019, 25(2): 454-468.
LI S Y, DAN B, GE X L. Optimization model and algorithm of low carbon vehicle routing problem under multi-graph time-varying network[J]. Computer Integrated Manufacturing Systems, 2019, 25(2): 454-468.
[12] 孔珊, 仲昭林, 张纪会. 多路径选择变速双目标物流配送路径规划[J]. 复杂系统与复杂性科学, 2022, 19(1): 74-80.
KONG S, ZHONG Z L, ZHANG J H. Bi-objective vehicle routing problems with path choice and variable speed[J]. Complex Systems and Complexity Science, 2022, 19(1): 74-80.
[13] 张晓楠, 王陆宇, 谭昕妮, 等. 时变条件下道路网的车辆路径优化[J]. 机械科学与技术, 2023, 42(11): 1919-1928.
ZHANG X N, WANG L Y, TAN X N, et al. Time-dependent vehicle routing optimization problem under road network[J]. Mechanical Science and Technology for Aerospace Engineering, 2023, 42(11): 1919-1928.
[14] SCORA G, BARTH M. Comprehensive modal emissions model (CMEM), version 3.01 user’s guide[EB/OL]. (2006-06)[2023-10-06]. https://www.cert.ucr.edu/cme-m/docs/CMEM_User_Guide_v3.01d.pdf.
[15] FRANCESCHETTI A, HONHON D, VAN WOENSEL T, et al. The time-dependent pollution-routing problem[J]. Transportation Research Part B: Methodological, 2013, 56: 265-293.
[16] HUANG Y X, ZHAO L, VAN WOENSEL T, et al. Time-dependent vehicle routing problem with path flexibility[J]. Transportation Research Part B: Methodological, 2017, 95: 169-195.
[17] 于江霞, 杜红亚, 罗太波. 基于客户分类的即时配送路径优化研究[J]. 交通运输系统工程与信息, 2020, 20(4): 202-208.
YU J X, DU H Y, LUO T B. Real-time delivery routing optimization based on customer classification[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(4): 202-208.
[18] 邱金红, 孙靖, 仲兆满. 基于配送收益均衡的多目标绿色车辆路径优化算法[J]. 控制与决策, 2023, 38(2): 365-371.
QIU J H, SUN J, ZHONG Z M. A multi-objective green vehicle routing optimization algorithm based on delivery benefit balance[J]. Control and Decision, 2023, 38(2): 365-371.