考虑枢纽拥堵和网络中断影响的快递网络优化设计

doi:10.3778/j.issn.1002-8331.2403-0398

摘要/Abstract

摘要： 为缓解快递网络转运枢纽的拥堵以及降低网络中断后的影响，以传统的轴辐式网络结构为基础，考虑由于枢纽拥堵产生的拥堵代价和拥堵时间，引入备份枢纽策略保障网络能够在中断后继续运行，以最小化正常和枢纽失效下的网络总期望成本为目标，建立了考虑枢纽拥堵和失效影响的快递网络优化模型。针对选址问题特点以及传统遗传算法深度搜索能力较弱的问题，设计了具有6种邻域结构的变邻域遗传算法（variable neighborhood genetic algorithm，VNGA），并基于Turkey网络数据集进行求解。在节点数为15的算例下，VNGA与粒子群算法、模拟退火算法求解结果的平均Gap值分别为?3.99%、?2.55%。最后对模型在两种不同情形下的结果进行分析，结果表明，同时考虑枢纽拥堵和失效影响的快递网络更为可靠。

关键词: 快递网络设计, 拥堵控制, 枢纽失效, 变邻域遗传算法

Abstract: In order to alleviate the congestion of the transport hub of the express network and reduce the impact after network interruption, based on the traditional hub-and-spoke network structure and considering the congestion cost and congestion time caused by hub congestion, a backup hub strategy is introduced to ensure that the network can continue to operate after disruption, with the goal of minimizing the total expected cost of the network under normal and hub failure conditions. An optimization model of express network considering the impact of hub congestion and failure is established. Aiming at the characteristics of the location problem and the weak deep search ability of traditional genetic algorithms, a variable neighborhood genetic algorithm with 6 kinds of neighborhood structures is designed and solved based on the Turkey network dataset. The average Gap values of VNGA, particle swarm optimization and simulated annealing are ?3.99% and 2.55% respectively under the example of 15 nodes. Finally, the results of the model in two different cases are analyzed, and the results show that the express network considering the impact of hub congestion and failure is more reliable.

Key words: express network design, congestion control, hub failure, variable neighborhood genetic algorithm

田帅辉, 孙家正, 陈坚. 考虑枢纽拥堵和网络中断影响的快递网络优化设计[J]. 计算机工程与应用, 2025, 61(13): 368-377.

TIAN Shuaihui, SUN Jiazheng, CHEN Jian. Optimization Design of Express Network Considering Impact of Hub Congestion and Network Interruption[J]. Computer Engineering and Applications, 2025, 61(13): 368-377.

参考文献

[1] O’KELLY M E, KIM H, KIM C. Internet reliability with realistic peering[J]. Environment and Planning B: Planning and Design, 2006, 33(3): 325-343.
[2] 杨珺, 邵路路, 刘舒佶. 考虑延迟惩罚的轴辐式枢纽网络中断问题研究[J]. 交通运输系统工程与信息, 2014, 14(3): 117-125.
YANG J, SHAO L L, LIU S J. Facility interdiction problem based on hub-and-spoke network with delay penalty[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 117-125.
[3] AN Y, ZHANG Y, ZENG B. The reliable hub-and-spoke design problem: models and algorithms[J]. Transportation Research Part B: Methodological, 2015, 77: 103-122.
[4] AZIZI N, CHAUHAN S, SALHI S, et al. The impact of hub failure in hub-and-spoke networks: mathematical formulations and solution techniques[J]. Computers & Operations Research, 2016, 65: 174-188.
[5] AFIFY B, RAY S, SOEANU A, et al. Evolutionary learning algorithm for reliable facility location under disruption[J]. Expert Systems with Applications, 2019, 115: 223-244.
[6] 郑长江, 胡欢, 杜牧青. 考虑枢纽失效的多式联运快递网络结构设计[J]. 吉林大学学报(工学版), 2023, 53(8): 2304-2311.
ZHENG C J, HU H, DU M Q. Design of multimodal express delivery network structure considering hub failure[J]. Journal of Jilin University (Engineering and Technology Edition), 2023, 53(8): 2304-2311.
[7] 李东, 晏湘涛, 匡兴华. 考虑设施失效的军事物流配送中心选址模型[J]. 计算机工程与应用, 2010, 46(11): 3-6.
LI D, YAN X T, KUANG X H. Location model for military logistics distribution centers considering facilities failure[J]. Computer Engineering and Applications, 2010, 46(11): 3-6.
[8] 黄志文, 李鸿旭, 钟元芾, 等. 不确定条件下战时应急物资配送中心选址研究[J]. 计算机工程与应用, 2023, 59(4): 269-279.
HUANG Z W, LI H X, ZHONG Y F, et al. Study on emergency distribution center location in wartime under uncertainty[J]. Computer Engineering and Applications, 2023, 59(4): 269-279.
[9] ELHEDHLI S, HU F X. Hub-and-spoke network design with congestion[J]. Computers & Operations Research, 2005, 32(6): 1615-1632.
[10] GHODRATNAMA A, ARBABI H R, AZARON A. A bi? objective hub location-allocation model considering congestion[J]. Operational Research, 2020, 20(4): 2427-2466.
[11] 黄务兰, 张涛, 张玥杰. 基于拥堵控制的轴辐式快递主干网规划[J]. 系统工程, 2018, 36(11): 86-96.
HUANG W L, ZHANG T, ZHANG Y J. The design of hub-and-spoke express transportation network considering congestion control[J]. Systems Engineering, 2018, 36(11): 86-96.
[12] ALUMUR S A, NICKEL S, ROHRBECK B, et al. Modeling congestion and service time in hub location problems[J]. Applied Mathematical Modelling, 2018, 55: 13-32.
[13] 王帮俊, 吴艳芳. 考虑枢纽点失效和拥堵情形的轴辐式物流网络设计研究[J]. 工业工程与管理, 2019, 24(2): 15-22.
WANG B J, WU Y F. The hub-and-spoke network design addressing hub reliable and congestion[J]. Industrial Engineering and Management, 2019, 24(2): 15-22.
[14] HUANG L L, TAN Y, GUAN X. Hub-and-spoke network design for container shipping considering disruption and congestion in the post COVID-19 era[J]. Ocean & Coastal Management, 2022, 225: 106230.
[15] AZIZI N, SALHI S. Reliable hub-and-spoke systems with multiple capacity levels and flow dependent discount factor[J]. European Journal of Operational Research, 2022, 298(3): 834-854.
[16] O’KELLY M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research, 1987, 32(3): 393-404.
[17] 王臻杰, 张得志, 秦进, 等. 考虑运输规模效应与网络拥堵的中欧班列运输网络优化[J]. 铁道学报, 2021, 43(11): 18-28.
WANG Z J, ZHANG D Z, QIN J, et al. Transportation network optimization of China railway express considering transportation scale effect and congestion[J]. Journal of the China Railway Society, 2021, 43(11): 18-28.
[18] AZIZI N. Managing facility disruption in hub-and-spoke networks: formulations and efficient solution methods[J]. Annals of Operations Research, 2019, 272(1): 159-185.
[19] GHAFFARINASAB N, MOTALLEBZADEH A, JABARZADEH Y, et al. Efficient simulated annealing based solution approaches to the competitive single and multiple allocation hub location problems[J]. Computers & Operations Research, 2018, 90: 173-192.
[20] 徐涛, 吴志帅, 卢敏, 等. 面向拥堵问题的枢纽航线网络优化模型[J]. 系统工程与电子技术, 2020, 42(11): 2553-2559.
XU T, WU Z S, LU M, et al. Optimization model of hub-and-spoke network for congestion problem[J]. Systems Engineering and Electronics, 2020, 42(11): 2553-2559.