Lagrangian relaxation heuristic algorithm of arc routing problem under time-space network
-
摘要: 为减少车辆调度成本，优化车辆运输路径，在时空网络中研究路段作业车辆的弧路径问题；考虑道路出行的时变性，利用车辆运行的时间、空间特征，构建时间-空间网络，建立弧路径问题的时空网络流模型；设计了拉格朗日松弛启发式算法，引入拉格朗日乘子松弛耦合约束，构建拉格朗日松弛问题；进一步通过拉格朗日分解，把松弛问题分解为单车最短路问题；用次梯度算法更新乘子，求解拉格朗日对偶问题，并更新原问题最优解的下界；使用启发式算法获得可行解，并更新原问题最优解的上界；用六结点运输网络和Sioux-Falls网络下的算例对算法进行实证分析。计算结果表明：六结点运输网络中6个算例的上下界间隙值等于0或接近0，Sioux-Falls网络中算例2的间隙值为0.02%，其余5个算例的间隙值等于0，均可以得到质量较高的近似最优解；在最复杂的算例(15辆车，70个任务)中，算法在可接受的时间内也得到了间隙值为0的解，找出了最优的车辆路径；随着迭代次数的增加，拉格朗日乘子会逐步收敛到固定值；当车辆容量从50增加到100时，最优解从52下降到42，说明在任务数和车辆数一定时，适当增加车容量可以降低运营成本。可见，与商业求解器相比，拉格朗日松弛启发式算法的间隙值更小，求解质量更高，可以更有效地求解弧路径问题。Abstract: The arc routing problem of road operating vehicles under the time-space network was studied to reduce the vehicle dispatching cost and optimize the vehicle transportation path. In view of the time variation of road travel and the time-space characteristics of vehicle operation, a time-space network was constructed, and a time-space network flow model for the arc routing problem was built. A heuristic algorithm based on Lagrangian relaxation was designed, and the Lagrangian multipliers were introduced to relax the coupling constraints to establish the Lagrangian relaxation problem. Furthermore, the relaxation problem was decomposed into the single vehicle shortest path problem by the Lagrangian decomposition. The sub-gradient algorithm was applied to update the multipliers, solve the Lagrangian dual problem, and update the lower bound of the optimal solution for the original problem. The heuristic algorithm was employed to produce a feasible solution and update the upper bound of the optimal solution for the original problem. Empirical analysis of the algorithm was carried out in different cases under the six-node transportation network and Sioux-Falls network. Calculation results show that the values of the gap between the upper and lower bounds of the six cases in the six-node transportation network are equal to 0 or close to 0. In the Sioux-Falls network, the gap value of Case 2 is 0.02%, and those of the remaining five cases are equal to 0. The approximate optimal solution with high quality can be obtained in all cases. In the most complex case (15 vehicles, 70 tasks), a solution without gap is obtained by the algorithm in an acceptable time, and the optimal vehicle paths are calculated. With the increase of the number of iterations, the Lagrangian multipliers will become fixed through gradual convergence. When the vehicle capacity increases from 50 to 100, the optimal solution reduces from 52 to 42, which shows that when the numbers of tasks and vehicles are constant, an appropriate increase in vehicle capacity is capable of reducing operating cost. Therefore, compared with commercial solvers, the heuristic algorithm based on the Lagrangian relaxation, featuring a smaller gap value and higher solution quality, is able to solve the arc routing problem more efficiently. 7 tabs, 11 figs, 33 refs.
-
图 3 求解最短路问题的动态规划算法
Figure 3. Dynamic programming algorithm solving shortest path problem
图 8 Sioux-Falls网络中算例1车辆路径
Figure 8. Vehicle paths in example 1 for Sioux-Falls network
图 9 Sioux-Falls网络中算例2上下界变化曲线
Figure 9. Change curves of upper and lower bounds in example 2 for Sioux-Falls network
图 10 Sioux-Falls网络中6组算例间隙值变化曲线
Figure 10. Gap value change curves in six examples for Sioux-Falls network
图 11 Sioux-Falls网络中算例1拉格朗日乘子变化
Figure 11. Lagrangian multipliers changes in example 1 for Sioux-Falls network
表 1 车辆路径问题与弧路径问题对比
Table 1. Comparison of vehicle routing problem and arc routing problem
问题 服务对象 路径 应用举例 VRP 结点 哈密尔顿路径 公交车调度问题、快递送货问题、商超补货问题 ARP 路段 欧拉路径 道路检测路径规划、路面养护路径规划、洒水车路径规划 
下载: 导出CSV
表 2 客户网络、道路网络和时空网络对比
Table 2. Comparison of customer network, road network, and time-space network
网络 结点 路段 路径 有向图 交通网络信息 状态 客户网络 客户结点 集计路段 非实际路径 否 不完整 静态 道路网络 实际结点 实际路段 实际路径 是 完整 静态 时空网络 时空结点 时空路段 时空路径 是 完整 动态
下载: 导出CSV
表 3 传统静态网络模型与时空网络模型对比
Table 3. Comparison of traditional static network model and time-space network model
模型 目标函数 自变量 流平衡约束 车容量约束 任务约束 破子圈约束 静态网络模型 成本最小 xv, (i, j) 有 有 有 有 时空网络模型 成本最小 xv, (i, j, t, s) 有 有 有 无
下载: 导出CSV
表 4 TDARP块状模型结构分析
Table 4. Analysis of block structure of TDARP model
目标函数式(2) C1X1+ C2X2+ … +CvXv 流平衡约束式(3)~(5)，车容量约束式(6) 车辆1约束 车辆2约束 … 车辆v约束 任务约束式(7) 任务1约束 任务2约束 … 任务w约束
下载: 导出CSV
表 5 六结点运输网络算例求解结果
Table 5. Calculation results of examples for six-node transportation network
算例 任务数量 车辆数量 迭代次数 L* U* 间隙值/% CPU运行时间/s 1 4 2 50 22.00 22.00 0.00 8 2 7 4 100 32.94 33.00 0.18 50 3 7 5 100 37.00 37.00 0.00 66 4 10 5 100 35.00 35.00 0.00 91 5 11 8 100 49.87 50.00 0.26 123 6 13 8 100 51.94 52.00 0.12 263
下载: 导出CSV
表 6 Sioux-Falls网络算例求解结果
Table 6. Calculation results of examples for Sioux-Falls network
算例 任务数量 车辆数量 迭代次数 L* U* 间隙值/% CPU运行时间/s 1 5 2 50 68.00 68.00 0.00 27 2 15 4 100 132.97 133.00 0.02 307 3 25 6 100 348.00 348.00 0.00 642 4 35 8 100 515.00 515.00 0.00 961 5 70 10 100 724.00 724.00 0.00 1932 6 70 15 100 693.00 693.00 0.00 2005
下载: 导出CSV
表 7 车容量对算法求解结果影响
Table 7. Influence of vehicle capacity on algorithm solution result
算例 任务数量 车辆数量 车容量 迭代次数 L* U* 间隙值/% CPU运行时间/s 1 13 8 50 100 51.94 52.00 0.12 263 2 13 8 75 100 46.50 47.00 1.08 335 3 13 8 100 100 41.97 42.00 0.07 330 4 13 8 125 100 41.49 42.00 1.22 340 5 13 8 150 100 41.63 42.00 0.89 338 6 13 8 175 100 41.44 42.00 1.35 191
下载: 导出CSV
-
[1] 彭锦环, 马慧民. 带容量约束的弧路径问题: 文献综述[J]. 物流科技, 2015, 38(1): 63-66. doi: 10.3969/j.issn.1002-3100.2015.01.019PENG Jin-huan, MA Hui-min. Review of literature about capacitated arc routing problem[J]. Logistics Sci-Tech, 2015, 38(1): 63-66. (in Chinese) doi: 10.3969/j.issn.1002-3100.2015.01.019 [2] GOLDEN B L, WONG R T. Capacitated arc routing problems[J]. Networks, 1981, 11(3): 305-315. doi: 10.1002/net.3230110308 [3] MANOUSAKIS E, REPOUSSIS P, ZACHARIADIS E, et al. Improved branch-and-cut for the inventory routing problem based on a two-commodity flow formulation[J]. European Journal of Operational Research, 2021, 290(3): 870-885. doi: 10.1016/j.ejor.2020.08.047 [4] RUIZ E R Y, GARCÍA-CALVILLO I, NUCAMENDI-GUILLÉN S. Open vehicle routing problem with split deliveries: mathematical formulations and a cutting-plane method[J]. Operational Research, 2022, 22(2): 1017-1037. doi: 10.1007/s12351-020-00580-8 [5] BELENGUER J M, BENAVENT E. A cutting plane algorithm for the capacitated arc routing problem[J]. Computers and Operations Research, 2003, 30(5): 705-728. doi: 10.1016/S0305-0548(02)00046-1 [6] RIERA-LEDESMA J, SALAZAR-GONZÁLEZ J J. Solving the team orienteering arc routing problem with a column generation approach[J]. European Journal of Operational Research, 2017, 262(1): 14-27. doi: 10.1016/j.ejor.2017.03.027 [7] BODE C, IRNICH S. Cut-first branch-and-price-second for the capacitated arc routing problem[J]. Operations Research, 2012, 60(5): 1167-1182. doi: 10.1287/opre.1120.1079 [8] CORBERÁN Á, PLANA I, REULA M, et al. On the distance-constrained close enough arc routing problem[J]. European Journal of Operational Research, 2021, 291(1): 32-51. doi: 10.1016/j.ejor.2020.09.012 [9] 刘洁, 何彦锋. 城市垃圾收集车辆弧路径问题研究[J]. 成都大学学报(自然科学版), 2013, 32(4): 423-426. https://www.cnki.com.cn/Article/CJFDTOTAL-CDDD201304027.htmLIU Jie, HE Yan-feng. Research on arc routing problem of waste collection vehicles[J]. Journal of Chengdu University (Natural Science Edition), 2013, 32(4): 423-426. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CDDD201304027.htm [10] 夏梦霜. 周期性带容量限制弧路径问题研究[D]. 重庆: 重庆大学, 2009.XIA Meng-shuang. Study on periodic capacitated arc routing problem[D]. Chongqing: Chongqing University, 2009. (in Chinese) [11] 孙锡梅. 同时配送和回收需求的容量约束弧路径问题[D]. 天津: 天津大学, 2014.SUN Xi-mei. Capacitated arc routing problem with simultaneous pickups and deliveries[D]. Tianjin: Tianjin University, 2014. (in Chinese) [12] PORUMBEL D, GONCALVES G, ALLAOUI H, et al. Iterated local search and column generation to solve arc-routing as a permutation set-covering problem[J]. European Journal of Operational Research, 2017, 256(2): 349-367. doi: 10.1016/j.ejor.2016.06.055 [13] POLACEK M, DOERNER K F, HARTL R F, et al. A variable neighborhood search for the capacitated arc routing problem with intermediate facilities[J]. Journal of Heuristics, 2008, 14(5): 405-423. doi: 10.1007/s10732-007-9050-2 [14] XIAO Yi-yong, KONAK A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 88: 146-166. doi: 10.1016/j.tre.2016.01.011 [15] GENDREAU M, GHIANI G, GUERRIERO E. Time-dependent routing problems: a review[J]. Computers and Operations Research, 2015, 64: 189-197. doi: 10.1016/j.cor.2015.06.001 [16] TAGMOUTI M, GENDREAU M, POTVIN J Y. Arc routing problems with time-dependent service costs[J]. European Journal of Operational Research, 2007, 181(1): 30-39. doi: 10.1016/j.ejor.2006.06.028 [17] TAGMOUTI M, GENDREAU M, POTVIN J Y. A dynamic capacitated arc routing problem with time-dependent service costs[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(1): 20-28. doi: 10.1016/j.trc.2010.02.003 [18] DE MAIO A, LAGANÀ D, MUSMANNO R, et al. Arc routing under uncertainty: introduction and literature review[J]. Computers and Operations Research, 2021, 135: 105442. doi: 10.1016/j.cor.2021.105442 [19] SUN Jing-hao, MENG Ya-kun, TAN Guo-zhen. An integer programming approach for the Chinese postman problem with time-dependent travel time[J]. Journal of Combinatorial Optimization, 2015, 29(3): 565-588. doi: 10.1007/s10878-014-9755-8 [20] RIAHI V, HAKIM NEWTON M A, SATTAR A. A scatter search algorithm for time-dependent prize-collecting arc routing problems[J]. Computers and Operations Research, 2021, 134: 105392. doi: 10.1016/j.cor.2021.105392 [21] 石兆, 符卓. 时变网络条件下带时间窗的食品冷链配送定位—运输路径优化问题[J]. 计算机应用研究, 2013, 30(1): 183-188. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201301048.htmSHI Zhao, FU Zhuo. Distribution location routing optimization problem of food cold chain with time window in time varying network[J]. Application Research of Computers, 2013, 30(1): 183-188. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201301048.htm [22] 马华伟, 靳鹏, 杨善林. 时变车辆路径问题的启发式算法[J]. 系统工程学报, 2012, 27(2): 256-262. https://www.cnki.com.cn/Article/CJFDTOTAL-XTGC201202018.htmMA Hua-wei, JIN Peng, YANG Shan-lin. Heuristic methods for time-dependent vehicle routing problem[J]. Journal of Systems Engineering, 2012, 27(2): 256-262. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTGC201202018.htm [23] PECIN D, UCHOA E. Comparative analysis of capacitated arc routing formulations for designing a new branch-cut-and-price algorithm[J]. Transportation Science, 2019, 53(6): 1673-1694. doi: 10.1287/trsc.2019.0900 [24] TIRKOLAEE E B, ALINAGHIAN M, HOSSEINABADI A A R, et al. An improved ant colony optimization for the multi-trip capacitated arc routing problem[J]. Computers and Electrical Engineering, 2019, 77: 457-470. doi: 10.1016/j.compeleceng.2018.01.040 [25] USBERTI F L, FRANÇA P M, FRANÇA A L M. The open capacitated arc routing problem[J]. Computers and Operations Research, 2011, 38(11): 1543-1555. doi: 10.1016/j.cor.2011.01.012 [26] 佟路. 基于时空可达性的交通网络设计模型及算法研究[D]. 北京: 北京交通大学, 2017.TONG Lu. Transportation network design models and algorithms for maximizing space-time accessibility[D]. Beijing: Beijing Jiaotong University, 2017. (in Chinese) [27] NIU Hui-min, ZHOU Xue-song, TIAN Xiao-peng. Coordinating assignment and routing decisions in transit vehicle schedules: a variable-splitting Lagrangian decomposition approach for solution symmetry breaking[J]. Transportation Research Part B: Methodological, 2018, 107: 70-101. doi: 10.1016/j.trb.2017.11.003 [28] YANG Sen-yan, NING Lian-ju, SHANG Pan, et al. Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 135: 101891. doi: 10.1016/j.tre.2020.101891 [29] MAHMOUDI M, ZHOU Xue-song. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations[J]. Transportation Research Part B: Methodological, 2016, 89: 19-42. doi: 10.1016/j.trb.2016.03.009 [30] TONG Lu, ZHOU Xue-song, MILLER H J. Transportation network design for maximizing space-time accessibility[J]. Transportation Research Part B: Methodological, 2015, 81: 555-576. doi: 10.1016/j.trb.2015.08.002 [31] FU Xiao, ZUO Yu-fan, ZHANG Shan-qi, et al. Measuring joint space-time accessibility in transit network under travel time uncertainty[J]. Transport Policy, 2022, 116: 355-368. doi: 10.1016/j.tranpol.2021.12.018 [32] 李庆华. 需求可拆分的容量约束弧路径问题研究[D]. 天津: 天津大学, 2012.LI Qing-hua. Research of split delivery capacitated arc routing problem[D]. Tianjin: Tianjin University, 2012. (in Chinese) [33] FISHER M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management Science, 2004, 50(12): 1861-1871. -
点击查看大图
图(11) / 表(7)
计量
- 文章访问数: 709
- HTML全文浏览量: 115
- PDF下载量: 164
- 被引次数: 0
