拥塞型中转站选址设计和容量决策问题

系统管理学报 ›› 2015, Vol. 24 ›› Issue (2): 215-223.

拥塞型中转站选址设计和容量决策问题

胡丹丹1，杨珺2，杨超2

1.中南民族大学管理学院，武汉430074；2.华中科技大学管理学院，武汉430074

收稿日期:2013-11-19 修回日期:2014-05-19
作者简介:胡丹丹（1983-），女，讲师。研究方向为网络优化，科学决策等。E-mail: hudandan1224@163.com
基金资助:
国家自然科学基金资助项目（71320107001,71172093）；教育部人文社会科学研究青年基金资助项目(11YJC630063)

On Location and Capacity Decisions of Transportation Hubs with Congestion

HU Dan-dan1，YANG Jun2, YANG Chao2

1. School of Management, South-central University for Nationalities, Wuhan 430074, China; 2. School of Management, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2013-11-19 Revised:2014-05-19

摘要/Abstract

摘要： 提出了拥塞型中转站选址和设计优化模型，设施设计包括设施容量和流量分配。已知各个O-D对产生的需求量分布函数，将中转站模拟成M/M/1的排队系统，建立了以设施选址成本、交通成本、拥塞成本和容量成本之和最小的非线性混合整数规划。根据容量为连续变量和离散变量两种不同的情况，提出了两种拉格朗日松弛算法求解。最后，通过大规模算例验证了算法的有效性，并比较了两种情况下的成本。

关键词: 拥塞设施, 选址-分配, 容量选择, 启发式算法

Abstract: This paper develops optimization models for transportation hub with congestion to simultaneously optimize location and design decisions, including capacity and flow allocation. It is assumed that the distribution function of demand between each O-D pair is given. Congestion at hub is modeled as a network of M/M/1 queues and the problem is formulated as a nonlinear mixed-integer program that explicitly minimizes location, congestion, capacity acquisition, and transportation costs. For continuous and discrete capacity decisions, heuristics based on Lagrangian relaxation to handle large size instances are presented. Computational experiments are performed to verify the effectiveness of the algorithms. The results of the two models are compared as well.

胡丹丹1，杨珺2，杨超2. 拥塞型中转站选址设计和容量决策问题[J]. 系统管理学报, 2015, 24(2): 215-223.

参考文献

[1]       O’Kelly, M E. A quadratic integer program for the location of interacting hub facilities[J]. Eur. J. Oper. Res. 1987, 32(3): 393–404.
[2]       Mayer C, Sinai T. Network effects, congestion externalities, and air traf?c delays: Or why not all delays are evil[J]. Amer. Econom. Rev., 2003, 93(4): 1194–1215.
[3]       Pels E, Verhoef E T. The economics of airport congestion pricing[J]. J. Urban Econom., 2004, 55(2): 257–277.
[4]       Aykin T. Lagrangian-relaxation based approaches to capacitated hub-and-spoke network design problem[J]. Eur. J. Oper. Res., 1994, 79(3): 501–523.
[5]       Ebery J, Krishnamoorthy M, Ernst A, Bolanf N. The capacitated multiple allocation hub location problem: Formulations and algorithms[J]. Eur. J. Oper. Res., 2000, 120(3): 614–631.
[6]       Sasaki M, Fukushima M. On the hub-and-spoke model with arc capacity constraints[J]. J. Oper. Res. Soc. Japan, 2003, 46(4): 409–428.
[7]       Guldmann J M, Shen G. A general mixed integer nonlinear optimization model for hub network design[J]. Working paper, Department of City and Regional Planning, The Ohio State University, Columbus, 1997.
[8]       Marianov V, Serra D. Location models for airline hubs behaving as M/D/c queues[J]. Comput. Oper. Res., 2003, 30(7): 983–1003.
[9]       Elhedhli S, Hu F X. Hub-and-spoke network design with congestion[J]. Comput. Oper. Res., 2005, 32(6): 1615–1632.
[10]    Elhedhli S, Wu H, A Lagrangean Heuristic for Hub-and-Spoke System Design[J]. INFORMS Journal on Computing, 2010, 22(2): 282–296.
[11]    Huang S, Batta R and Nagi R. Variable capacity sizing and selection of connections in a facility layout[J]. IIE Trans, 2003, 35: 49–59.
[12]    Huang S, Batta R and Nagi R. Distribution Network Design: Selection and Sizing of Congested Connections[J]. Naval Research Logistics, 2005, 52: 701-712.
[13]    Silva F, Serra D. Incorporating waiting time in competitive location models[J]. Networks and Spatial Economics, 2007, 7(1): 63-76.
[14]    Daskin M S. A maximum expected covering location model: formulation, properties and heuristic solution[J]. Transportation Science, 1983, 17(1): 48–70.
[15]    Iannoni A P, Morabito R, Saydam C. An optimization approach for ambulance location and the districting of the response segments on highways[J]. European Journal of Operational Research, 2009, 195: 528–542.
[16]    Zhang L, Rushton G. Optimizing the size and locations of facilities in competitive multi-site service systems[J]. Computers & Operations Research, 2008, 35(2): 327-338.
[17] 胡丹丹, 杨超, 杨珺. 带有目标顾客定位的排队选址问题[J]. 系统管理学报, 2010(2): 215-221.
[18]    Boffey B, Galvao R, and Espejo L. A review of congestion models in the location of facilities with immobile servers[J]. European Journal of Operational Research, 2007, 178(3): 643–662.
[19]    Armony M, Plambeck E, Seshadri S. Sensitivity of optimal capacity to customer impatience in an unobservable M/M/S queue (Why you shouldn't shout at the DMV)[J]. Manufacturing & Service Operations Management, 2009, 11(1): 19-32.
[20]    Daskin M S, Coullard C R, Shen Z.-J.M. An inventory-location model: Formulation, solution algorithm and computational results[J]. Annals of Operations Research, 2002,110 : 83–106.
[21]    Daskin M S. Network and discrete location: models, algorithms, and applications[M]. John Wiley & Sons, 2011.
[22]    Amiri A. The design of service systems with queueing time cost, workload capacities and backup service[J]. European Journal of Operational Research, 1998, 104: 201-217.
[23]    Agnihothri S R, Narasimhan S and Pirkul H. An assignment problem with queueing time cost[J]. Naval Research Logistics, 1990, 37: 231-244.
[24]Berman O, Drezner Z. Location of congested capacitated facilities with distance-sensitive demand[J]. IIE Transactions, 2006, 38(3): 213-221.