基于连接成本的快递网络拥塞控制

doi:10.16381/j.cnki.issn1003-207x.2017.04.017

中国管理科学 ›› 2017, Vol. 25 ›› Issue (4): 143-151.doi: 10.16381/j.cnki.issn1003-207x.2017.04.017

基于连接成本的快递网络拥塞控制

杨从平^1,2, 郑世珏², 党永杰², 杨青²

1. 广西民族大学商学院, 广西南宁 530006;
2. 华中师范大学计算机学院, 湖北武汉 430079

收稿日期:2015-06-24 修回日期:2015-12-18 出版日期:2017-04-20 发布日期:2017-06-29
通讯作者: 杨从平(1975-),男(苗族),广西资源县人,广西民族大学商学院副教授,博士,研究方向:物流网络,E-mail:1007843722@qq.com. E-mail:1007843722@qq.com
基金资助:
国家自然科学基金资助项目（61170017）

Congestion Control of Express Delivery Network Based on Connection Cost

YANG Cong-ping^1,2, ZHENG Shi-jue², DANG Yong-jie², YANG Qing²

1. College of Business, Guangxi University for Nationalities, Nanning 530006, China;
2. School of Computer, Central China Normal University, Wuhan 430079, China

Received:2015-06-24 Revised:2015-12-18 Online:2017-04-20 Published:2017-06-29

摘要/Abstract

摘要： 本文采用图论的方法研究快递网络拥塞控制问题。通过分析快递网络流量特性，研究快递网络结构对网络传输能力的影响，平衡网络传输能力和连接成本之间的关系。首先，介绍介数的概念，考虑介数与货物流量的关系，修改了介数定义，并设计了介数的计算方法；接下来，根据介数计算公式推导快递网络传输能力与节点介数和节点能力的关系；然后，构建满足预期网络传输能力的最小连接成本拥塞控制模型，并设计了通过不断加边、重连和删除边的方法迭代寻找最优的快递网络结构；最后通过广西某快递公司的配送网络为算例验证模型和算法的有效性。研究结果显示算法能够有效地找出最优的快递网络，研究发现瓶颈节点的处理能力和介数决定网络的传输能力，网络传输能力与连接成本悖反。

关键词: 快递网络, 图论, 拥塞控制, 传输能力, 连接成本

Abstract: By adopting graph theory,congestion control of express network is studied in this paper. Through the analysis of the characteristics of the network traffic flow and the study on the effect of the structure of express network on the network transmission capability, balancing the relationship between the network transmission capability and the connection cost. First of all, the concept of betweenness is introduced. Considering the relationship between the betweenness and cargo flow, the betweenness definition is modified, and the calculation method of betweenness is designed. Next, according to the betweenness calculation formula, the relationship of express network transmission capacity, node betweenness and node capacity are derived. Then, by taking the minimum connection cost as the optimization goal, an optimization model of express delivery network with the constraint of expect transmission capacity is constructed, and an algorithm is designed to seek the network with the optimal structure by gradually adding edge, reconnecting edge and deleting edge. Finally, the example of the backbone network of an express delivery company in Guangxi province is taken to verify the effectiveness of the model and algorithm. The result of simulation indicates that the algorithm can effectively find out the optimal delivery network. Through the research, it is found that processing power and betweenness of the bottleneck node decision network transmission capacity, and there is a contradiction between network transmission capacity and connection cost.

Key words: express network, graph theory, congestion control, transmission capacity, connection cost

中图分类号:

F252.3

杨从平, 郑世珏, 党永杰, 杨青. 基于连接成本的快递网络拥塞控制[J]. 中国管理科学, 2017, 25(4): 143-151.

YANG Cong-ping, ZHENG Shi-jue, DANG Yong-jie, YANG Qing. Congestion Control of Express Delivery Network Based on Connection Cost[J]. Chinese Journal of Management Science, 2017, 25(4): 143-151.

参考文献

[1] 于宝琴,武淑萍,杜广伟. 网购快递物流服务系统测评的枝模型仿真[J]. 中国管理科学,2014,22(12):72-78.

[2] Arenas A, Díaz-Guilera A, Guimera R. Communication in networks with hierarchical branching[J]. Physical Review Letters, 2001, 86(14):3196-3199.

[3] Yan Gang, Zhou Tao, Hu Bo, et al. Efficient routing on complex networks[J]. Physical Review E, 2006, 73(4):046108-1-046108-5.

[4] Danila B, Yu Yong, Marsh J, et al. Optimal transport on complex networks[J]. Physical Review E, 2006, 74(4):046106-1-046106-4.

[5] 王开,周思源,张毅锋,等. 一类基于随机行走机理的优化路由改进策略[J]. 物理学报,2011,60(11):118903.

[6] 刘伟彦,刘斌. 基于加权路由策略的复杂网络拥塞控制研究[J]. 系统工程理论实践,2015,35(4):1063-1068.

[7] Wang W Xenxu, Wang Binghong, Yin Chuanyang, et al. Traffic dynamics based on local routing protocol on a scale-free network[J]. Physical Review E, 2006, 73(2):026111-1-026111-7.

[8] Echenique P, Gómez-Gardeñes J, Moreno Y. Improved routing strategies for Internet traffic delivery[J]. Physical Review E, 2004, 70(5):056105-1-056105-4.

[9] Zhang Huan, Liu Zonghua, Tang Ming, et al. An adaptive routing strategy for packet delivery in complex networks[J]. Physics letters A, 2007, 364(3-4):177-182.

[10] Zhao Liang, Lai Y C, Park K, et al. Onset of traffic congestion in complex networks[J]. Physical Review E, 2005, 71(2):026125-1-026125-8.

[11] Wu Zhixi, Peng Gang, Wong W M, et al. Improved routing strategies for data traffic in scale-free networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2008,(11):1459-1475.

[12] Ling Xiang, Hu Maobin, Du Wenbo, et al. Bandwidth allocation strategy for traffic systems of scale-free network[J]. Physics Letters A, 2010, 374(48):4825-4830.

[13] Zheng Jianfeng, Zhu Zhihong, Du Haoming, et al. Congestion and efficiency in complex traffic networks[J]. International Journal of Modern Physics C, 2013, 24(10):1350072-1-1350072-12.

[14] Liu Zhe, Hu Maobin, Jiang Rui, et al. Method to enhance traffic capacity for scale-free networks[J]. Physical Review E, 2007, 76(3):037101-1-037101-4.

[15] Zhang Guoqing, Wang Di, Li Guojie. Enhancing the transmission efficiency by edge deletion in scale-free networks[J]. Physical Review E, 2007, 76(1):017101-1-017101-4.

[16] 张国清,程苏琦. 小世界网络中的删边扩容效应[J]. 中国科学:信息科学,2012,42(2):151-160.

[17] 蔡君,余顺争. 一种有效提高无标度网络负载容量的管理策略[J]. 物理学报,2013,62(5):058901.

[18] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2):026113-1-026113-16.

[19] Huang Wei, Chow T W S. Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network[J]. Chaos, 2010, 20(3):033123.

[20] Jiang Zhongyuan, Liang Mangui, An Wenjuan. Effects of efficient edge rewiring strategies on network transport efficiency[J]. Physica A:Statistical Mechanics and its Applications, 2014, 394:379-385.

[21] 周涛,张子柯,陈关荣,等. 复杂网络研究的机遇与挑战[J]. 电子科技大学学报,2014,43(1):1-5.

[22] Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1):35-41.

[23] Barthelemy M. Betweenness centrality in large complex networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2):163-168.

基于连接成本的快递网络拥塞控制

Congestion Control of Express Delivery Network Based on Connection Cost

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 10

[1]	赵晋, 张建军, 严蔡华. 允许直达的混合轴辐式快递网络规划模型与算法研究[J]. 中国管理科学, 2016, 24(11): 58-65.
[2]	邓超, 陈学军. 基于复杂网络的金融传染风险模型研究[J]. 中国管理科学, 2014, 22(11): 11-18.
[3]	邓超, 陈学军. 基于复杂网络的金融传染风险模型研究[J]. 中国管理科学, 2014, 22(11): 11-18.
[4]	赵培忻, 张存铨, 赵炳新. 基于新型图论聚类法的物流系统多设施选址策略研究[J]. 中国管理科学, 2012, 20(6): 149-153.