基于无容量限制的p-枢纽中位问题的随机优化

葛伟, 朱金福, 吴薇薇, 吴小欢

系统工程理论与实践 ›› 2013, Vol. 33 ›› Issue (10) : 2674-2678.

PDF(478 KB)
PDF(478 KB)
系统工程理论与实践 ›› 2013, Vol. 33 ›› Issue (10) : 2674-2678. DOI: 10.12011/1000-6788(2013)10-2674
论文

基于无容量限制的p-枢纽中位问题的随机优化

    葛伟1,2, 朱金福1, 吴薇薇1, 吴小欢1
作者信息 +

Stochastic optimization for uncapacitated p-hub median problems

    GE Wei1,2, ZHU Jin-fu1, WU Wei-wei1, WU Xiao-huan1
Author information +
文章历史 +

摘要

在枢纽网络设计时, 未来的成本和需求等参数具有不确定性. 为了使设计的网络能在各种情景下具有最优的期望成本, 提出了无容量限制的多分配严格p-枢纽中位随机优化模型. 考虑到模型本身的结构特点和复杂程度, 采用了PH分解算法结合增广拉格朗日松弛算法, 将原问题转化为若干个独立子问题来求解. 使用了基于经典算例的随机数据集合对模型和算法进行了测试, 算例结果表明尤其在情景数量较大的情况下, 算法体现出较高的效率. 同时, 通过随机解价值分析了使用随机优化模型对于该算例的意义.

Abstract

The parameters of hub-and-spoke network design are usually uncertain. In order to get the minimal expectation cost of the network for all scenarios, this paper presents a stochastic uncapacitated strict p-hub median model under the uncertainties of parameters. Based on the model with its high complexity, the progressive hedging method combined with the augmented Lagrangian relaxation is introduced to solve the model. This algorithm can divide the primal problem into several subproblems effectively. Finally, a case study based on the classical data sets shows the effect of using the combined method, and the importance of adopting stochastic optimization method by the comparison over the values of stochastic solution.

关键词

p-枢纽中位问题 / 随机优化 / PH算法 / 随机解价值

Key words

p-hub median / stochastic optimization / progressive hedging method / value of stochastic solution

引用本文

导出引用
葛伟 , 朱金福 , 吴薇薇 , 吴小欢. 基于无容量限制的p-枢纽中位问题的随机优化. 系统工程理论与实践, 2013, 33(10): 2674-2678 https://doi.org/10.12011/1000-6788(2013)10-2674
GE Wei , ZHU Jin-fu , WU Wei-wei , WU Xiao-huan. Stochastic optimization for uncapacitated p-hub median problems. Systems Engineering - Theory & Practice, 2013, 33(10): 2674-2678 https://doi.org/10.12011/1000-6788(2013)10-2674
中图分类号: F560   

参考文献

[1] 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.
[2] Campbell J F. Integer programming formulations of discrete hub location problems[J]. European Journal of Operational Research, 1994, 72: 387-405.
[3] Campbell J F. Hub location and the p-hub median problem[J]. Operations Research, 1996, 44(6): 923-935.
[4] Aykin T. The hub location and routing problem[J]. European Journal of Operational Research, 1995, 83: 200-219.
[5] Klincewicz J G. A dual algorithm for the uncapacitated hub location problem[J]. Location Science, 1996, 4(3): 173-184.
[6] Skorin-Kapov D, Skorin-Kapov J, O'Kelly M E. Tight linear programming relaxation of uncapacitated p-hub median problems[J]. European Journal of Operational Research, 1996, 94: 582-593.
[7] 姜涛. 航空公司中枢辐射航线网络鲁棒优化设计问题研究[D]. 南京: 南京航空航天大学, 2007.Jiang T. Research on robust optimization design problems of hub-and-spoke airline network[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2007.
[8] Barla P, Constantatos C. Airline network structure under demand uncertainty[J]. Transportation Research Part E, 2000, 36: 173-180.
[9] Yang T H. Stochastic air freight hub location and flight routes planning[J]. Applied Mathematical Modeling, 2009, 33(12): 4424-4430.
[10] Contreras I, Cordeau J F, Laporte G. Stochastic uncapacitated hub location[J]. European Journal of Operational Research, 2011, 212(3): 518-528.
[11] Rockafellar R T, Wets R B. Scenarios and policy aggregation in optimization under uncertainty[J]. Mathematics of Operations Research, 1991, 16: 119-147.
[12] Lokketangen A, Woodruff D. Progressive hedging and tabu search applied to mixed integer (0,1) multi-stage stochastic programming[J]. Journal of Heuristics, 1996, 2(2): 111-128.
[13] Mulvey J M, Vladimirou H. Solving multistage stochastic networks: An application of scenario aggregation[J]. Networks, 1991, 21(6): 619-643.
[14] Fan Y, Liu C. Solving stochastic transportation network protection problem using the progressive hedging-based method[J]. Networks and Spatial Economics, 2010, 10(2): 193-208.
[15] Van Slyke R, Wets R B. L-shaped linear programs with application to optimal control and stochastic programming[J]. SIAM Journal on Applied Mathematics, 1969, 17: 638-663.

基金

国家自然科学基金(71201081, 71171111); 江苏省普通高校研究生创新基金(CX10B-102Z, CXZZ11-0220); 南京航空航天大学青年科技创新基金(56Y1082); 江苏省博士后科研资助项目(0802041C)
PDF(478 KB)

Accesses

Citation

Detail

段落导航
相关文章

/