|Table of Contents|

Lagrangian relaxation heuristic algorithm of arc routing problem under time-space network(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2022年04期
Page:
273-284
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
Lagrangian relaxation heuristic algorithm of arc routing problem under time-space network
Author(s):
CHENG Lin;  NING Yi-sen;  SONG Mao-can
(School of Transportation, Southeast University, Nanjing 211189, Jiangsu, China)
Keywords:
traffic planning;  arc routing;  Lagrangian relaxation;  time-space network;  time-dependent shortest path;  dynamic programming
PACS:
U491.1
DOI:
10.19818/j.cnki.1671-1637.2022.04.021
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.

References:

[1] 彭锦环,马慧民.带容量约束的弧路径问题:文献综述[J].物流科技,2015,38(1):63-66.
PENG Jin-huan, MA Hui-min. Review of literature about capacitated arc routing problem[J]. Logistics Sci-Tech, 2015, 38(1): 63-66.(in Chinese)
[2] GOLDEN B L, WONG R T. Capacitated arc routing problems[J]. Networks, 1981, 11(3): 305-315.
[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.
[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.
[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.
[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.
[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.
[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.
[9] 刘 洁,何彦锋.城市垃圾收集车辆弧路径问题研究[J].成都大学学报(自然科学版),2013,32(4):423-426.
LIU 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)
[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.
[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.
[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.
[15] GENDREAU M, GHIANI G, GUERRIERO E. Time-dependent routing problems: a review[J]. Computers and Operations Research, 2015, 64: 189-197.
[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.
[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.
[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.
[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.
[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.
[21] 石 兆,符 卓.时变网络条件下带时间窗的食品冷链配送定位—运输路径优化问题[J].计算机应用研究,2013,30(1):183-188.
SHI 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)
[22] 马华伟,靳 鹏,杨善林.时变车辆路径问题的启发式算法[J].系统工程学报,2012,27(2):256-262.
MA 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)
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.

Memo

Memo:
-
Last Update: 2022-09-01