带固定轴线成本的轴辐式网络设计问题

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 88-96.

带固定轴线成本的轴辐式网络设计问题

翁克瑞¹

1. 中国地质大学（武汉）经济管理学院, 武汉 430074

收稿日期:2011-03-15 修回日期:2011-10-31 出版日期:2012-03-15 发布日期:2012-03-15
通讯作者: 翁克瑞 E-mail:wengkerui@gmail.com
基金资助:
国家自然科学基金项目(71102151), 中央高校专项基金(CUG090113)

The Stability of the Solutions of Optimization Hub-and-Spoke Network Design Problem with Fixed Hub Arc Costs

WENG Ke-Rui¹

1. School of Economics & Management, China University of Geosciences, Wuhan, 430074, China

Received:2011-03-15 Revised:2011-10-31 Online:2012-03-15 Published:2012-03-15
Contact: kerui weng E-mail:wengkerui@gmail.com

摘要/Abstract

摘要： 带固定轴线成本的轴辐式网络设计问题广泛应用于第三方物流、邮政和航空运输等领域. 现有研究主要考虑了枢纽站的节点成本, 本研究则强调合并运输的固定轴线成本. 固定轴线成本的必要性在于：轴辐式网络中的轴线运输需要借助更大型的运输工具, 因此必须支付固定成本. 建立了该问题的混合整数规划模型, 探讨了最优解特征, 并构造了求解问题的拉格朗日松驰算法, 实验显示算法具有非常好的求解效率与求解质量. 同时, 还讨论了一个重要的扩展问题：增加O-D流的绕道约束, 绕道约束常常应用于快递运输和应急物流等领域. 在局部修改原算法的基础上提供了扩展问题的求解方案.

关键词: 轴辐式网络, 轴线, 合并运输, 拉格朗日

Abstract: Hub-and-Spoke network design problem with fixed hub arc cost has a wide range of applications within the third party logistics, postal services and airline transportation. Current researches concentrated on hub location while this paper emphasizes on the fixed hub arc costs which reflects a fact that the transportation on hub arc must be provided with large-scale vehicles and therefore pay extra fixed costs. This paper constructs a mixed 0-1 integer programming model, and provided a heuristic algorithm based on Lagrangian relaxation。 We also extend the problem by add the route distance constraint which is very important on emergency logistics and express delivery. We solve the extended problem by modifying the original algorithm.

Key words: hub-and-spoke network, hub arc, collaborative transportation, Lagrangian

翁克瑞. 带固定轴线成本的轴辐式网络设计问题[J]. 运筹学学报, 2012, 16(1): 88-96.

WENG Ke-Rui. The Stability of the Solutions of Optimization Hub-and-Spoke Network Design Problem with Fixed Hub Arc Costs[J]. Operations Research Transactions, 2012, 16(1): 88-96.

参考文献

Filipovic V, Kratica J, Tosic D, et al. GA Inspired Heuristic for Uncapacitated Single Allocation Hub Location Problem. Applications of Soft Computing, 2009, 58:149--158.
Koksalan M, Soylu B. Bicriteria p-Hub Location Problems and Evolutionary Algorithms. Informs Journal on Computing, 2010, 22(4): 528-542.
Koksalan M, Soylu B. Bicriteria p-Hub Location Problems and Evolutionary Algorithms. Informs Journal on Computing, 2010, 22(4): 528-542.
翁克瑞. 轴辐式物流网络设计的选址与路线优化研究, 电子科技大学出版社, 2009.
Silva M B, Cunha C B. New simple and efficient heuristics for the uncapacitated single allocation hub location problem. Computers & Operations Research, 2009,36(12) :3152-3165.
Rodriguez-Martin I, Salazar-Gonzalez J.J. A local branching heuristic for the capacitated fixed-charge network design problem. Computers & Operations Research, 2010, 37(3): 575-581.
Randall M. Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation. Computational Optimization and Applications, 2008, 39(2): 239-261.
Contreras I, Diaz J A, Fernandez E. Lagrangean relaxation for the capacitated hub location problem with single assignment. Or Spectrum, 2009, 31(3): 483-505.
Correia I, Nickel S, Saldanha-da-Gama F. The capacitated single-allocation hub location problem revisited: A note on a classical formulation. European Journal Of Operational Research, 2010, 207(1): 92-96.
Correia I, Nickel S, Saldanha-da-Gama F. Single-assignment hub location problems with multiple capacity levels. Transportation Research Part B-Methodological, 2010, 4: 1047-1066.
Puerto J, Ramos A B, Rodriguez-Chia AM. Single-allocation ordered median hub location problems. Computers & Operations Research, 2011, 38(2): 559-570.
Chen J F. The Uncapacitated Hub Location Problem with Allocation Constraints. Proceedings of the Eighth International Conference on Information and Management Sciences:Series of Information and Management Sciences, 2009, 8: 30-35.
Eiselt H A, Marianov V. A conditional p-hub location problem with attraction functions. Computers & Operations Research, 2009, 36(12): 3128-3135.
Campbell J F, Ernst A T, Krishnamoorthy M. Hub arc location problems: Part I - IntrO-Duction and results. Management Science, 2005, 51: 1540-55.
Campbell J F, Ernst A T, Krishnamoorthy M. Hub Arc location problems: Part II - Formulations and optimal algorithms. Management Science, 2005, 51: 1556-71.
Campbell J F. Hub location for time definite transportation Computers & Operations Research, 2009, 36(12): 3107-3116.
Camargo R S, Miranda J R G, Luna H P. Benders Decomposition for Hub Location Problems with Economies of Scale. Transportation Science, 2009, 43(1): 86-97.
Held M, Wolfe P, Crowder H. Validation of Subgradient Optimization[J]. Mathematical Programming, 1974, 6: 62-88.

[1]	梁仁莉, 白延琴. 求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法[J]. 运筹学学报, 2019, 23(2): 86-94.
[2]	张惠珍, 魏欣, 马良. 求解无容量设施选址问题的半拉格朗日松弛新方法[J]. 运筹学学报, 2015, 19(4): 37-47.
[3]	朱婷婷，陈伟，陈娟娟，孙文浩. 一类连续可分离背包问题的直接算法[J]. 运筹学学报, 2013, 17(1): 44-58.
[4]	文再文,印卧涛,刘歆,张寅. 压缩感知和稀疏优化简介[J]. 运筹学学报, 2012, 16(3): 49-64.