留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

受限单分配枢纽选址问题的并行蚁群算法

崔小燕,  李旭宏,  毛海军,  张永,  杨平乐

downloadPDF
文章导航 > 交通运输工程学报  > 2011 >  11(3): 74-81
崔小燕, 李旭宏, 毛海军, 张永, 杨平乐. 受限单分配枢纽选址问题的并行蚁群算法[J]. 交通运输工程学报, 2011, 11(3): 74-81. doi: 10.19818/j.cnki.1671-1637.2011.03.013
引用本文: 崔小燕, 李旭宏, 毛海军, 张永, 杨平乐. 受限单分配枢纽选址问题的并行蚁群算法[J]. 交通运输工程学报, 2011, 11(3): 74-81. doi: 10.19818/j.cnki.1671-1637.2011.03.013
shu
CUI Xiao-yan, LI Xu-hong, MAO Hai-jun, ZHANG Yong, YANG Ping-le. Parallel ant colony optimization of location problem for limited single allocation hub[J]. Journal of Traffic and Transportation Engineering, 2011, 11(3): 74-81. doi: 10.19818/j.cnki.1671-1637.2011.03.013
Citation: CUI Xiao-yan, LI Xu-hong, MAO Hai-jun, ZHANG Yong, YANG Ping-le. Parallel ant colony optimization of location problem for limited single allocation hub[J]. Journal of Traffic and Transportation Engineering, 2011, 11(3): 74-81. doi: 10.19818/j.cnki.1671-1637.2011.03.013
shu

受限单分配枢纽选址问题的并行蚁群算法

doi: 10.19818/j.cnki.1671-1637.2011.03.013
  • 1.

    东南大学 交通学院, 江苏 南京 210096

  • 2.

    江苏科技大学 计算机科学与工程学院, 江苏 张家港 215600

基金项目: 

国家自然科学基金项目 50575043

高等学校博士学科点专项科研基金项目 20090092120046

详细信息
    作者简介:

    崔小燕（1981-）, 女, 河南潢川人, 东南大学工学博士研究生, 从事现代物流与运输网络规划研究

    李旭宏（1963-）, 男, 四川自贡人, 东南大学教授, 工学博士

  • 中图分类号: U491.1

Parallel ant colony optimization of location problem for limited single allocation hub

  • 1.

    School of Transportation, Southeast University, Nanjing 210096, Jiangsu, China

  • 2.

    School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhangjiagang 215600, Jiangsu, China

More Information

    摘要
  • 摘要: 研究了受限单分配枢纽选址问题的特点, 以网络运输总成本和固定设施费用之和为最小化目标函数, 建立了具有较少变量的混合整数线性规划模型, 应用并行蚁群算法对模型进行求解, 并结合澳大利亚邮政数据进行选址仿真试验。计算结果表明: 对于最难求解的50个节点的双紧约束问题, 算法运算时间为3.59 s, 远低于已有的其他算法; 各算例的运算偏差不大于0.09%。可见, 并行蚁群算法具有良好的求解效率和计算稳定性。

     

    Abstract: The characteristics of location problem for limited single allocation hub were analyzed. The sum of total network transportation costs and fixed facility costs was taken as the minimum objective function, and a mixed integer linear programming model with fewer variables was set up. Parallel ant colony optimization (P-ACO) was used to solve the model, and correlative simulation test was carried out combined with Australia post data. Calculation result indicates that for the most difficult problem with 50 nodes and double tight constraints, the computational time of proposed model is 3.59 s, which is minimum compared with the other algorithms, and the calculation errors are not more than 0.09%. So, P-ACO has good solution efficiency and calculational stability.

     

    • HTML全文

  • 图  1  单分配轴-辐式网络

    Figure  1.  Single allocation hub-and-spoke network

    下载: 全尺寸图片 幻灯片

    图  2  多分配轴-辐式网络

    Figure  2.  Multiple allocation hub-and-spoke network

    下载: 全尺寸图片 幻灯片

    图  3  与最优解群组交流

    Figure  3.  Communication with best solution group

    下载: 全尺寸图片 幻灯片

    图  4  与相邻最近群组相互交流

    Figure  4.  Mutual communication between nearest group pairs

    下载: 全尺寸图片 幻灯片

    图  5  在环形结构内交流

    Figure  5.  Communication in ring structure

    下载: 全尺寸图片 幻灯片

    图  6  错位群组交流

    Figure  6.  Communication among dislocation groups

    下载: 全尺寸图片 幻灯片

    图  7  算法流程

    Figure  7.  Algorithm flow

    下载: 全尺寸图片 幻灯片

    表  1  计算结果

    Table  1.   Calculation results

    问题 已知最优解 本文最优解 枢纽节点 枢纽节点与非枢纽节点的分配关系
    10LL 224 250.05 224 250.05 3, 4, 7 3, 4, 3, 4, 7, 4, 7, 7, 7, 7
    10LT 250 992.26 250 992.26 1, 4, 5, 10 1, 4, 5, 4, 5, 4, 10, 10, 10, 10
    10TL 263 399.94 263 399.94 4, 5, 10 5, 4, 5, 4, 5, 4, 10, 10, 10, 10
    10TT 263 399.94 263 399.94 4, 5, 10 5, 4, 5, 4, 5, 4, 10, 10, 10, 10
    20LL 234 690.96 234 690.96 7, 14 7, 7, 7, 7, 7, 7, 7, 7, 14, 7, 7, 14, 14, 14, 14, 14, 14, 14, 14
    20LT 253 517.40 253 517.40 10, 14 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 14, 14, 10, 10, 14, 14, 14
    20TL 271 128.18 271 128.18 7, 19 7, 7, 7, 7, 7, 7, 7, 7, 19, 7, 7, 7, 19, 19, 19, 19, 19, 19, 19, 19
    20TT 296 035.40 296 035.40 1, 10, 19 1, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 19, 10, 19, 19, 19, 19
    25LL 238 977.95 238 977.95 8, 18 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18
    25LT 276 372.50 276 372.50 9, 16, 25 9, 9, 9, 9, 9, 16, 9, 9, 9, 9, 16, 16, 25, 25, 25, 16, 16, 25, 25, 25
    25TL 310 317.64 310 317.64 9, 23 9, 9, 9, 9, 9, 23, 9, 9, 9, 9, 23, 23, 9, 9, 9, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23
    25TT 348 369.15 348 369.15 9, 16, 25 9, 9, 9, 9, 9, 16, 9, 9, 9, 9, 16, 16, 9, 9, 9, 16, 16, 25, 25, 25, 16, 16, 25, 25, 25
    40LL 241 955.71 241 955.71 11, 29 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 29, 11, 11, 11, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
    40LT 272 218.32 272 218.32 14, 26, 30 14, 14, 14, 14, 14, 14, 14, 14, 26, 26, 14, 14, 14, 14, 14, 14, 26, 26, 26, 14, 14, 14, 14, 14, 26, 26, 26, 30, 26, 30, 30, 26, 26, 26, 26, 26, 30, 30, 30
    40TL 298 919.01 298 919.01 14, 19 14, 19, 14, 14, 14, 14, 14, 14, 19, 19, 19, 14, 14, 14, 14, 14, 19, 19, 19, 19, 19, 14, 14, 14, 19, 19, 19, 19, 19, 19, 19, 14, 19, 19, 19, 19, 19, 19, 19, 19
    40TT 354 874.10 354 874.10 14, 19, 40 14, 14, 14, 14, 14, 14, 14, 14, 19, 14, 14, 14, 14, 14, 14, 14, 19, 19, 19, 14, 19, 14, 14, 14, 19, 19, 19, 40, 19, 40, 40, 40, 19, 19, 19, 40, 40, 40, 40, 40
    50LL 238 520.59 238 520.59 15, 35 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 35, 35, 35, 35, 15, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35
    50LT 272 897.49 272 897.49 6, 26, 32, 46 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 32, 32, 32, 6, 6, 26, 26, 26, 26, 26, 32, 32, 32, 26, 26, 26, 26, 26, 26, 26, 32, 32, 32, 32, 46, 46, 26, 26, 26, 26, 32, 32, 32, 32, 46, 46, 46, 46, 46, 26
    50TL 319 015.77 319 015.77 3, 24 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 24, 3, 24, 3, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24
    50TT 417 440.99 417 440.99 6, 26, 28, 28 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 28, 28, 28, 26, 26, 26, 26, 26, 26, 28, 28, 28, 28, 26, 26, 26, 48, 26, 48, 26, 28, 28, 28, 48, 26, 26, 48, 48, 48, 48, 48, 48, 48
    下载: 导出CSV

    表  2  结果对比

    Table  2.   Comparison of results

    问题规模 并行蚁群算法 蚁群算法 混合模拟退火算法 模拟退火算法 拉格朗日松弛算法
    计算时间/s 计算平均偏差/% 计算时间/s 计算平均偏差/% 计算时间/s 计算平均偏差/% 计算时间/s 计算平均偏差/% 计算时间/s 计算平均偏差/%
    10LL 0.03 0.00 0.01 0.00 0.07 0.00 0.19 0.00 0.03 0.00
    10LT 0.03 0.00 0.00 0.00 0.06 0.00 0.21 0.00 0.03 0.00
    10TL 0.03 0.00 0.01 0.00 0.07 0.00 0.15 0.00 0.06 0.00
    10TT 0.03 0.00 0.00 0.00 0.04 0.00 0.17 0.00 0.05 0.00
    20LL 0.06 0.00 0.36 0.00 0.20 0.00 0.65 0.00 0.38 0.00
    20LT 0.07 0.00 0.17 0.00 0.10 0.00 0.63 0.00 1.64 0.83
    20TL 0.07 0.00 0.33 0.00 0.19 0.00 0.53 0.00 0.19 0.00
    20TT 0.08 0.00 0.79 0.00 0.26 0.00 0.66 0.51 0.16 0.00
    25LL 0.33 0.00 0.84 0.00 0.43 0.00 1.05 0.00 1.97 0.00
    25LT 0.41 0.00 1.26 0.00 0.34 0.00 1.07 0.05 2.55 0.04
    25TL 0.49 0.00 1.04 0.00 0.34 0.00 1.12 0.00 1.05 0.00
    25TT 1.01 0.02 0.83 0.00 0.41 0.23 1.15 0.42 2.47 0.34
    40LL 2.22 0.00 5.61 0.00 1.27 0.00 2.66 0.00 7.24 0.07
    40LT 2.28 0.00 9.46 0.00 2.14 0.00 2.78 0.29 6.81 0.08
    40TL 2.34 0.09 6.83 0.00 1.46 0.00 2.92 0.00 1.59 0.00
    40TT 2.65 0.00 145.50 0.00 2.98 0.00 3.13 2.59 11.39 0.50
    50LL 3.25 0.00 15.46 0.00 2.30 0.00 4.30 0.00 13.00 0.00
    50LT 3.42 0.04 281.00 0.00 7.39 0.00 4.88 0.40 63.98 0.43
    50TL 3.25 0.00 31.50 0.00 2.34 0.00 5.63 0.08 20.02 0.80
    50TT 3.59 0.09 18 583.50 0.00 4.60 0.09 5.91 1.32 77.16 2.93
    下载: 导出CSV
    • 参考文献(17)
  • [1] HORNER M W, O'KELLY M E. Embedding economies of scale concepts for hub network design[J]. Journal of Transport Geography, 2001, 9 (4): 255-265. doi: 10.1016/S0966-6923(01)00019-9
    [2] 李阳. 轴辐式网络理论及应用研究[D]. 上海: 复旦大学, 2006.

    LI Yang. Research on hub and spoke network theory and its application[D]. Shanghai: Fudan University, 2006. (in Chinese)
    [3] ALUMUR S, KARA B Y. Network hub location problem: the state of the art[J]. European Journal of Operational Research, 2008, 190 (1): 1-21. doi: 10.1016/j.ejor.2007.06.008
    [4] ERNST A T, KRISHNAMOORTHY M. Solution algorithms for the capacitated single allocation hub location problem[J]. Annals of Operations Research, 1999, 86 (0): 141-159.
    [5] RANDALL M. Solution approaches for the capacitated single allocation hub location problem using ant colony optimization[J]. Computational Optimization Applications, 2008, 39 (2): 239-261. doi: 10.1007/s10589-007-9069-1
    [6] COSTA M D G, CAPTIVO M E, CLIMACO J. Capacitated single allocation hub location problem—a bi-criteria approach[J]. Computers and Operations Research, 2008, 35 (11): 3671-3695. doi: 10.1016/j.cor.2007.04.005
    [7] CHEN J F. A heuristics for the capacitated single allocation hub location problem[J]. Lecture Notes in Electrical Engineering, 2008 (5): 185-196.
    [8] CONTRERAS I, DIAZ J A, FERNANDEZ E. Lagrangean relaxation for the capacitated hub location problem with single assignment[J]. OR Spectrum, 2009, 31 (3): 483-505. doi: 10.1007/s00291-008-0159-y
    [9] 邓亚娟, 陈小鸿, 杨超. 需求不确定的枢纽辐射式航线网络设计[J]. 交通运输工程学报, 2009, 9 (6): 69-75. doi: 10.3969/j.issn.1671-1637.2009.06.014

    DENG Ya-juan, CHEN Xiao-hong, YANG Chao. Hub-and-spoke airline network design with uncertainty demand[J]. Journal of Traffic and Transportation Engineering, 2009, 9 (6): 69-75. (in Chinese) doi: 10.3969/j.issn.1671-1637.2009.06.014
    [10] DORIGO M, GANBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1 (1): 53-66. doi: 10.1109/4235.585892
    [11] MULLEN R J, MONEKOSSO D, BARMAN S, et al. A review of ant algorithms[J]. Espert Systems with Applications, 2009, 36 (6): 9608-9617.
    [12] CHEN C H, TING C J. Combining lagrangian heuristic and ant colony systemto solve the single source capacitated facility location problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2008, 44 (6): 1099-1122. doi: 10.1016/j.tre.2007.09.001
    [13] 刘臣奇, 李梅娟, 陈雪波. 基于蚁群算法的拣选作业优化问题[J]. 系统工程理论与实践, 2009, 29 (3): 179-185. doi: 10.3321/j.issn:1000-6788.2009.03.025

    LIU Chen-qi, LI Mei-juan, CHEN Xue-bo. Order picking problem based on ant colony algorithm[J]. Systems Engineering—Theory and Practice, 2009, 29 (3): 179-185. (in Chinese) doi: 10.3321/j.issn:1000-6788.2009.03.025
    [14] CHUS C, RODDICKJ F, PANJ S. Ant colony system with communication strategies[J]. Information Sciences, 2004, 167 (1/2/3/4): 63-76.
    [15] ELLLABIB I, CALAMAI P, BASIR O. Exchange strategies for multiple ant colony system[J]. Information Sciences, 2007, 177 (5): 1248-1264.
    [16] RANDALL M, LEWIS A. A parallel implementation of ant colony opti mization[J]. Journal of Parallel and Distributed Computing, 2002, 62 (9): 1421-1432.
    [17] 葛春景, 王霞, 关贤军. 应急服务设施轴辐网络布局的λ-鲁棒优化[J]. 工业工程与管理, 2010, 15 (6): 45-50, 57. https://www.cnki.com.cn/Article/CJFDTOTAL-GYGC201006012.htm

    GE Chun-jing, WANG Xia, GUAN Xian-jun. λ-robust optimization of emergent service facilities hub-and-spoke network response for large-scale emergency[J]. Industkial Engineering and Management, 2010, 15 (6): 45-50, 57. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GYGC201006012.htm
    • 相关文章
    • 施引文献
  • 资源附件(0)
  • 加载中
WeChat 点击查看大图
图(7) / 表(2)
计量
  • 文章访问数:  543
  • HTML全文浏览量:  43
  • PDF下载量:  598
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-01-26
  • 刊出日期:  2011-06-25

目录

    /

    返回文章
    返回

    版权所有《交通运输工程学报》编辑部陕ICP备05001904号-1

    地址：陕西省 西安市 南二环 路中段 长安大学《交通运输工程学报》编辑部（710064） 电话：029-82334388 Email：jygc@chd.edu.cn

    访问总数:今日访问:

    本系统由 北京仁和汇智信息技术有限公司 开发    百度统计