无容量约束单分配轴-辐式物流网络设计

交通运输系统工程与信息 ›› 2010, Vol. 10 ›› Issue (5): 175-181 .

无容量约束单分配轴-辐式物流网络设计

崔小燕¹;李旭宏^*1; 毛海军¹;张永¹;杨平乐²

1.东南大学交通学院，南京 210096；2. 江苏科技大学张家港校区基础部，江苏张家港 215600

收稿日期:2010-01-19 修回日期:2010-06-22 出版日期:2010-10-25 发布日期:2010-10-25
通讯作者: 李旭宏
作者简介:崔小燕（1981-），女，河南省潢川人，博士生.
基金资助:
教育部博士点基金（20090092120046）

Design of Uncapacitated Hub-and-Spoke Logistics Networks with Single Allocation

CUI Xiao-yan¹, LI Xu-hong¹, MAO Hai-jun¹, ZHANG Yong¹, YANG Ping-le²

1. Transportation College, Southeast University, Nanjing 210096, China; 2. Department of Basic Courses, Zhangjiagang Campus of Jiangsu University of Science and Technology, Zhangjiagang 215600, Jiangsu, China

Received:2010-01-19 Revised:2010-06-22 Online:2010-10-25 Published:2010-10-25
Contact: LI Xu-hong

摘要/Abstract

摘要： 针对无容量约束的单分配轴-辐式物流网络设计问题的特点，为其建立了单分配p-枢纽中位模型，并提出了一种基于蚁群算法的启发式求解算法. 该算法分两步实现：首先利用蚁群算法来确定网络中枢纽节点的位置，然后用另一种启发式算法将非枢纽节点分配给枢纽节点，同时，将一种基于6种邻域结构的变邻域搜索算法作为蚁群算法的局域搜索策略以提升算法的全局搜索能力，并加快收敛速度. 最后结合澳大利亚邮政数据进行了算例仿真实验，并对蚁群算法中参数的合理设置进行了测试分析，实验结果表明,该算法在求解此问题时有着良好的有效性和较快的求解效率.

关键词: 物流工程, p-枢纽中位, 蚁群算法, 变邻域搜索算法, 轴-辐式物流网络

Abstract: In this paper, an uncapacitated single allocation p-hub median model is developed considering the characters of the uncapacitated hub-and-spoke logistics networks. A heuristic algorithm based on ant colony system is presented to solve the mathematic formulation. The ant colony system is applied to locate the hub nodes, and then a heuristics algorithm is used to assign the non-hub nodes to the hub nodes. Meanwhile, a variable neighborhood search algorithm with six neighborhood structures is implemented as the local search procedure for the ant colony system to improve the overall search ability of this algorithm and speed up the convergence process. Finally, a computational experiment is performed with the AP data set, and a test is carried out for the reasonable selection of the parameters in ant colony system. The experimental results indicate the algorithm is feasible to the problem and has good efficiency in finding the optimization solution.

Key words: logistics engineering, p-hub median, ant colony algorithm, variable neighborhood search, hub-and-spoke logistics networks

中图分类号:

U491

崔小燕,李旭宏, 毛海军,张永,杨平乐. 无容量约束单分配轴-辐式物流网络设计[J]. 交通运输系统工程与信息, 2010, 10(5): 175-181 .

CUI Xiao-yan, LI Xu-hong, MAO Hai-jun, ZHANG Yong, YANG Ping-le. Design of Uncapacitated Hub-and-Spoke Logistics Networks with Single Allocation[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 10(5): 175-181 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18054.shtml

http://www.tseit.org.cn/CN/Y2010/V10/I5/175

参考文献

［1］姚志刚,周伟,王元庆. 轴-辐式运输网络的范围经济问题［J］.交通运输系统工程与信息,2009, 9(1):24-27. ［YAO Z G, ZHOU W, WANG Y Q. Economies of scope of hub and spoke transportation network［J］. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(1):24-27.］
［2］Kratica J, Stanimirovic Z, Tosic D, et al. Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem［J］. European Journal of Operational research, 2007(182):15-28. 
［3］O’Kelly M E. A quadratic integer program for the location of interacting hub facilities［J］. European Journal of Operational Research, 1987(32): 393–404. 
［4］Campell J F. Integer programming formulations of discrete hub location problems［J］. European Journal of Operational Research, 1994(72):387-405. 
［5］Skorin-Kapov D, Skorin-Kapov J. On tabu search for the location interacting hub facilities［J］. European Journal of Operational Research, 1994(73):502-509. 
［6］Ernst A T, Krishnamoorthy M. Efficient algorithms for the uncapacitated single allocation p-hub median problem［J］. Location Science, 1996, 4(3):139-154. 
［7］Perez M, Almeida F, Moreno-Vega J M. Genetic algorithm with multistart search for the p-hub median problem［C］// Proceedings of the 24th EUROMICRO Conference EUROMICRO’98, IEEE Computer Society, 2000:702–707. 
［8］Perez M, Rodri’guez F A, Moreno-Vega J M. On the use of the path relinking for the p-hub median problem ［C］. Evolutionary Computation in Combinatorial Optimization, 2004 (3004): 155–164. 
［9］Perez M, Rodri’guez F A, Moreno-Vega J M. A hybrid VNS-path relinking for the p-hub median problem［J］. IMA Journal of Management Mathematics, 2007, 18(2):157-171. 
［10］Wolf S, Merz P. Evolutionary local search for the super-peer selection problem and the p-hub median problem［C］. Lecture Notes in Computer Science, 2007(4771):1-15. 
［11］Dorigo M, Gambardella 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. 
［12］Dorigo M, Caro M D, Gambardella L M. Ant algorithms for discrete optimization［J］. Artificial Life, 1999, 5(2):137-172. 
［13］Randall M. Solution approaches for the capacitated single allocation hub location problem using ant colony optimization［J］. Computational Optimization Applications，2008(39):239-261. 
［14］Roli A, Blum C, Dorigo M. ACO for maximal constraint satisfaction problem［C］. In: Fourth Meta-heuristics International Conference, 2001:187-191. 
［15］Alumur S, Kara B Y. Network hub location problem: the state of the art［J］. European Journal of Operational Research, 2008(190):1-21. 
［16］Chen J F, Wu T H. A note on solution of the uncapacitated single allocation p-hub median problem［J］. Journal of the Chinese Institute of Industrial Engineers, 2008, 25(1):11-17. 
［17］Hansen P, Mladenovic N, Perez J A M. Variable neighborhood search: methods and applications［J］. 4OR A Quarterly Journal of Operations Research, 2008, 6(4):319-360. 
［18］Ernst A T, Krishnamoorthy M. Solution algorithms for the capacitated single allocation hub location problem［J］. Annals of Operations Research, 1999(86):141-159. 
［19］Besasley J. http://people.brunel.ac.uk/~mastjjb/jeb/info.html［DB］. OR-Library. 2005.

[1]	张英贵, 姚璎华, 高全, 雷定猷. 铁路集装箱混合货物平衡装载布局优化模型与算法[J]. 交通运输系统工程与信息, 2022, 22(2): 214-222.
[2]	姜晓红, 陈莎, 张毅. 物流企业碳排放总量与效率测算方法[J]. 交通运输系统工程与信息, 2022, 22(2): 313-321.
[3]	周小祥, 黄承锋. 农村物流末端共配联盟演化博弈及稳定性研究[J]. 交通运输系统工程与信息, 2022, 22(1): 265-272.
[4]	王清斌, 于江宁, 郑建风. 甩挂运输模式下新增运输任务的干扰管理模型[J]. 交通运输系统工程与信息, 2021, 21(6): 160-166.
[5]	柳伍生, 李旺, 周清, 迭纤. “无人机-车辆”配送路径优化模型与算法[J]. 交通运输系统工程与信息, 2021, 21(6): 176-186.
[6]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[7]	奇格奇, 张子贤, 卫振林, 李宝文. 基于语义挖掘的快递运输货品风险评价研究[J]. 交通运输系统工程与信息, 2021, 21(4): 248-255.
[8]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.
[9]	杨华龙，辛禹辰，高浩然. 随机扰动项呈离散分布的库存路径和定价问题的模型与算法[J]. 交通运输系统工程与信息, 2021, 21(2): 211-216.
[10]	辛禹辰，施胜男，杨华龙. 基于订单拆分的线上到线下连锁门店配送优化模型[J]. 交通运输系统工程与信息, 2020, 20(5): 212-217.
[11]	赵志学，李夏苗. 时变交通下生鲜配送电动车辆路径优化方法[J]. 交通运输系统工程与信息, 2020, 20(5): 218-225.
[12]	于江霞，杜红亚，罗太波. 基于客户分类的即时配送路径优化研究[J]. 交通运输系统工程与信息, 2020, 20(4): 202-208.
[13]	刘杰，黎浩东，张萌. 基于点线能力约束的多层级节点协同布局优化模型及算法研究[J]. 交通运输系统工程与信息, 2020, 20(2): 107-113.
[14]	吴玥琳，袁振洲，陈秋芳，肖清榆，王文成，魏来. 考虑轨迹相似度的综合客运枢纽出租车合乘方法研究[J]. 交通运输系统工程与信息, 2020, 20(2): 188-195.
[15]	尹小庆，莫宇迪，董陈晨，林云. 考虑行程时间可靠性的城市冷链末端配送站选址研究[J]. 交通运输系统工程与信息, 2019, 19(6): 176-183.