Time-dependent Vehicle Routing Optimization Problem Under Road Network
-
摘要: 针对车辆路径优化问题在现实中涉及的时变旅行时间特征和道路网络因素，研究时变条件下基于道路网的车辆路径优化问题。首先，考虑车辆旅行速度的时变特征，构建旅行速度的分段函数，采用跨时域的方法利用离散速度计算动态旅行时间；其次，基于关键节点的概念简化道路网络，克服车辆路径问题在考虑道路网时存在的维度灾问题。基于以上，结合时变旅行时间和基于关键点构建的道路网路，建立以总旅行时间最小为目标的优化模型；根据问题特征，设计蚁群算法求解；以西安市未央区桶装水配送区域实例进行测试，验证模型和算法的有效性，分析不同速度-时间变化模式和车辆出发时间的敏感性。Abstract: Aiming at the time-dependent feature and road network in vehicle routing problem, this paper studies time-dependent vehicle routing optimization under road network. First, considering the time-dependent travel speed, we construct the piecewise function on vehicle travel speed, and based on that, we could calculate dynamically the travel time by using cross time-domain method; Second, using the concept of key road nodes, we simplify the road network to overcome the curse of dimensionality of the vehicle routing optimization problem under road network. Based on the above two, we consider both time-dependent travel time and the simplified road network with key nodes, and establish an optimization model with the objective of minimizing the total travel time. Then, we design ant colony algorithm to solve the model. Finally, we test an example of barreled water delivery service in Weiyang District of Xi′an to verify the effectiveness of the model and algorithm. Additionally, the sensitivity on vehicle speed and departure time is analyzed.
-
Key words:
- vehicle routing problem /
- road network /
- time-dependent networks /
- ant colony algorithm
-
图 15 早高峰速度时间变化（错峰出行）
Figure 15. Speed during morning peak time span (staggered shifts)
图 16 晚高峰速度时间变化（错峰出行）
Figure 16. Speed during evening peak time span (staggered shifts)
图 18 早高峰速度时间变化图（尾号限行）
Figure 18. Speed during morning peak time span (license plate restrictions)
图 19 晚高峰速度时间变化图（尾号限行）
Figure 19. Speed during evening peak time span (license plate restrictions)
表 1 符号定义
Table 1. Definition of notations
符号 属性 $ 1 $ 配送中心 $ C $ 所有客户的集合 $ N $ 所有路节点的集合$,N = 1 \cup C \cup N_0$ $N_0$ 非需求点的网络节点集合，即车辆可以
在该点改变行驶路线$ E $ 边集合，$ e(i,j) \in E $ $ {J}_{ij} $ 弧$ e(i,j) $的距离 $ {t}_{ij} $ 车辆在弧上$ e(i,j) $行驶的总旅行时间 $ {a}_{i} $ 车辆到达客户i的时间 $ {d}_{i} $ 车辆离开客户i的时间 $ {x}_{ij} $ 车辆从节点i行驶至节点j，则$ {x_{ij}} = 1 $ $ {y}_{i} $ 车辆驶过节点i则$ {y_i} = 1 $ $ {s}_{ij}^{L} $ 车辆在第L时间段在弧$ e(i,j) $上行驶的速度 $ {t}_{ij}^{L} $ 车辆在第L时间段在弧$ e(i,j) $上行驶的时间 $ {F}_{ij}^{L} $ 车辆在第L时间段以速度$ {s}_{ij}^{L} $在弧$ e(i,j) $上行驶的距离 
下载: 导出CSV
表 2 不同出发时间算例的目标函数值表
Table 2. Objective function values for instances ofdifferent departure time
出发时间 07:00 08:00 09:00 10:00 行驶时间/min 141 138 100 91
下载: 导出CSV
-
[1] 吴宗胜, 傅卫平. 移动机器人全局路径规划的模拟退火-教与学优化算法[J]. 机械科学与技术, 2016, 35(5): 678-685.WU Z S, FU W P. SA and teaching-learning-based optimization algorithmfor mobile robots global path planning[J]. Mechanical Science and Technology for Aerospace Engineering, 2016, 35(5): 678-685. (in Chinese) [2] 巫光福, 万路萍. 粒子群算法优化机器人路径规划的研究[J]. 机械科学与技术, 2022, 41(11): 1759-1764.WU G F, WAN L P. Research on improved particle swarm optimization algorithm for robot path planning[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(11): 1759-1764. (in Chinese) [3] 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. doi: 10.1016/S0377-2217(02)00147-9 [4] 范厚明, 张跃光, 田攀俊, 等. 时变路网下异型车辆动态配置与路径优化[J]. 系统工程理论与实践, 2022, 42(2): 455-470.FAN H M, ZHANG Y G, TIAN P J, et al. Dynamic vehicle routing problem of heterogeneous fleets with time-dependent networks[J]. Systems Engineering-Theory & Practice, 2022, 42(2): 455-470. (in Chinese) [5] 李金名, 倪炎榕, 郑宇, 等. 面向第三方物流配送的道路网建模及应用[J]. 计算机集成制造系统, 2009, 15(9): 1765-1769.LI J M, NI Y R, ZHENG Y, et al. Road network modeling and application oriented to third-party logistics distribution[J]. Computer Integrated Manufacturing Systems, 2009, 15(9): 1765-1769. (in Chinese) [6] MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3): 185-200. doi: 10.1287/trsc.26.3.185 [7] HILL A V, BENTON W C. Modelling intra-city time-dependent travel speeds for vehicle scheduling problems[J]. Journal of the Operational Research Society, 1992, 43(4): 343-351. doi: 10.1057/jors.1992.49 [8] 李妍峰, 李军, 高自友. 时变网络环境下旅行商问题研究[J]. 系统工程学报, 2010, 25(5): 585-591.LI Y F, LI J, GAO Z Y. Traveling salesman problem in time varying network[J]. Journal of Systems Engineering, 2010, 25(5): 585-591. (in Chinese) [9] 唐金环, 戢守峰, 沈贵财. 时变网络下考虑碳排放的车辆路径优化[J]. 系统工程, 2015, 33(9): 37-44.TANG J H, JI S F, SHEN G C. Vehicle routing optimization with carbon emissions considered under time-varying network[J]. Systems Engineering, 2015, 33(9): 37-44. (in Chinese) [10] 赵志学, 李夏苗. 时变交通下生鲜配送电动车辆路径优化方法[J]. 交通运输系统工程与信息, 2020, 20(5): 218-225.ZHAO Z X, LI X M. Electric vehicle route optimization for fresh logistics distribution based on time-varying traffic congestion[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(5): 218-225. (in Chinese) [11] 刘长石, 申立智, 盛虎宜, 等. 考虑交通拥堵规避的低碳时变车辆路径问题研究[J]. 控制与决策, 2020, 35(10): 2486-2496.LIU C S, SHEN L Z, SHENG H Y, et al. Research on low-carbon time-dependent vehicle routing problem with traffic congestion avoidance approaches[J]. Control and Decision, 2020, 35(10): 2486-2496. (in Chinese) [12] 侯登凯, 范厚明, 任晓雪. 时变路网下多中心混合车队联合配送车辆路径优化[J]. 大连海事大学学报, 2022, 48(1): 11-22.HOU D K, FAN H M, REN X X. Vehicle routing optimization of multi-center hybrid fleet joint distribution under time-varying road network[J]. Journal of Dalian Maritime University, 2022, 48(1): 11-22. (in Chinese) [13] 李妍峰, 高自友, 李军. 动态网络车辆路径派送问题研究[J]. 管理科学学报, 2014, 17(8): 1-9.LI Y F, GAO Z Y, LI J. Dynamic vehicle routing and dispatching problem[J]. Journal of Management Sciences in China, 2014, 17(8): 1-9. (in Chinese) [14] 李妍峰, 高自友, 李军. 基于实时交通信息的城市动态网络车辆路径优化问题[J]. 系统工程理论与实践, 2013, 33(7): 1813-1819.LI Y F, GAO Z Y, LI J. Vehicle routing problem in dynamic urban network with real-time traffic information[J]. Systems Engineering-Theory & Practice, 2013, 33(7): 1813-1819. (in Chinese) [15] 葛显龙, 张慧. 城市实时交通路网车辆路径优化问题研究[J]. 工业工程与管理, 2018, 23(3): 140-149.GE X L, ZHANG H. Study on the optimization of vehicle routing problem in urban real time traffic network[J]. Industrial Engineering and Management, 2018, 23(3): 140-149. (in Chinese) [16] 陈迎欣. 基于改进蚁群算法的车辆路径优化问题研究[J]. 计算机应用研究, 2012, 29(6): 2031-2034.CHEN Y X. Study on VRP based on improved ant colony optimization[J]. Application Research of Computers, 2012, 29(6): 2031-2034. (in Chinese) [17] 陈秀娟, 高更君, 冯媛媛. 基于改进蚁群算法的逆向物流车辆路径优化[J]. 制造业自动化, 2019, 41(5): 46-49.CHEN X J, GAO G J, FENG Y Y. Optimization of reverse logistics vehicle path based on improved ant colony algorithm[J]. Manufacturing Automation, 2019, 41(5): 46-49. (in Chinese) -
点击查看大图
图(20) / 表(2)
计量
- 文章访问数: 141
- HTML全文浏览量: 40
- PDF下载量: 19
- 被引次数: 0
