有能力限制的轴辐网络关键枢纽识别模型

doi:10.3969/j.issn.1007-7375.2020.02.013

工业工程 ›› 2020, Vol. 23 ›› Issue (2): 100-104,123.doi: 10.3969/j.issn.1007-7375.2020.02.013

有能力限制的轴辐网络关键枢纽识别模型

李婷婷

北京大学城市规划与设计学院，广东深圳 518055

收稿日期:2019-04-17 发布日期:2020-04-22
作者简介:李婷婷(1985-)，女，广东省人，博士后，主要研究方向为交通运输规划与管理
基金资助:
国家自然科学基金资助项目（51678004）

A Model for Identifying Critical Hubs in Capacitated Hub-and-spoke Networks

LI Tingting

School of Urban Planning and Design, Peking University, Shenzhen 518055, China

Received:2019-04-17 Published:2020-04-22

摘要/Abstract

摘要： 为识别轴辐网络的关键枢纽，考虑枢纽能力限制构建双层规划模型，基于下层模型的对偶问题将双层规划模型转化为单层规划并线性化，通过算例验证了模型的有效性。结果表明：能力限制下，模型的约束和变量数增多、求解时间变长、关键枢纽识别结果有差异；随着折扣系数或关键枢纽数量减小或惩罚成本增大，计算时间增加；惩罚成本影响关键枢纽识别结果；通过比较不同参数下的关键枢纽，可识别相对固定的关键枢纽并加强设防。

关键词: 轴辐网络, 关键枢纽识别, 双层规划模型, 能力限制

Abstract: In order to identify the critical hubs in hub-and-spoke networks, a bilevel programming model is constructed considering the capacity limitation of hubs. Based on the dual problem of the lower level model, the bilevel programming model is transformed into single-level programming and linearized. The validity of the model is verified by a numerical example. The results show that the model has larger numbers of constraints and variables, longer solution time and different results of critical hub identification under the capacitated constraints. With the reductions of discount coefficients or the number of critical hubs or the increase of penalty cost, the calculation time generally increases. Penalty cost affects the results of critical hub identification. By comparing the critical hubs with different parameters, the relatively fixed critical hubs can be identified and fortification strengthened.

Key words: hub-and-spoke network, identification of critical hubs, bilevel programming model, capacity constraints

中图分类号:

U491

李婷婷. 有能力限制的轴辐网络关键枢纽识别模型[J]. 工业工程, 2020, 23(2): 100-104,123.

LI Tingting. A Model for Identifying Critical Hubs in Capacitated Hub-and-spoke Networks[J]. Industrial Engineering Journal, 2020, 23(2): 100-104,123.

参考文献

[1] YANG K, YANG L, GAO Z. Hub-and-spoke network design problem under uncertainty considering financial and service issues: a two-phase approach[J]. Information Sciences, 2017, 402: 15-34
[2] FARAHANI R Z, HEKMATFAR M, ARABANI A B, et al. Hub location problems: a review of models, classification, techniques and application[J]. Computers & Industrial Engineering, 2013, 64(4): 1096-1109
[3] O'KELLY M E. Network hub structure and resilience[J]. Networks and Spatial Economics, 2015, 15: 235-251
[4] GHAFFARINASAB N, MOTALLEBZADEH A. Hub interdiction problem variants: models and metaheuristic solution algorithms[J]. European Journal of Operational Research, 2018, 267(2): 496-512
[5] SMITH J C, PRINCE M, GEUNES J. Modern network interdiction problems and algorithms[M]. New York: Springer, 2013: 1949-1988.
[6] AKSEN D, AKCA S S, ARAS N. A bilevel partial interdiction problem with capacitated facilities and demand outsourcing[J]. Computers & Operations Research, 2014, 41: 346-358
[7] LOSADA C, SCAPARRA M P, CHURCH R L, et al. The stochastic interdiction median problem with disruption intensity levels[J]. Annals of Operations Research, 2012, 201(1): 345-365
[8] LEI T L. Identifying critical facilities in hub-and-spoke networks: a hub interdiction median problem[J]. Geographical Analysis, 2013, 45(2): 105-122
[9] PARVARESH F, HUSSEINI S M, GOLPAYEGANY S A H, et al. Hub network design problem in the presence of disruptions[J]. Journal of Intelligent Manufacturing, 2014, 25(4): 755-774
[10] GHAFFARINASAB N, ATAYI R. An implicit enumeration algorithm for the hub interdiction median problem with fortification[J]. European Journal of Operational Research, 2018, 267(1): 23-39
[11] RAMAMOORTHY P, JAYASWAL S, SINHA A, et al. Multiple allocation hub interdiction and protection problems: model formulations and solution approaches[J]. European Journal of Operational Research, 2018, 270(1): 230-245
[12] CAMPBELL J F, O'KELLY M E. Twenty-five years of hub location research[J]. Transportation Science, 2013, 46(2): 153-169
[13] ADAMS W P, FORRESTER R J. A simple recipe for concise mixed 0-1 linearizations[J]. Operations Research Letters, 2005, 33(1): 55-61
[14] MCCORMICK G P. Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems[J]. Mathematical Programming, 1976, 10(1): 147-175
[15] BEASLEY J E. OR-Library[EB/OL].[2019-01-10]. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/phubinfo.html.
[16] EBERY J, KRISHNAMOORTHY M, ERNST A, et al. The capacitated multiple allocation hub location problem: formulations and algorithms[J]. European Journal of Operational Research, 2000, 120(3): 614-631
[17] CHAHARSOOGHI S K, MOMAYEZI F, GHAFFARINASAB N. An adaptive large neighborhood search heuristic for solving the reliable multiple allocation hub location problem under hub disruptions[J]. International Journal of Industrial Engineering Computations, 2017, 8(2): 191-202
[18] IBM. ILOG CPLEX Optimization studio[EB/OL].[2019-01-10]. https://www.ibm.com/products/ilog-cplex-optimization-studio/details.
[19] O'KELLY M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research, 1987, 32(3): 393-404

有能力限制的轴辐网络关键枢纽识别模型

A Model for Identifying Critical Hubs in Capacitated Hub-and-spoke Networks

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	曹涛涛, 蒋阳升, 赵斌, 姚志洪, 谭宇. 考虑多交叉口相互影响的干道相位差仿真优化研究[J]. 工业工程, 2018, 21(6): 40-45.
[2]	傅惠, 陈恺宇. 基于工作流网的应急资源配置与路径规划集成优化[J]. 工业工程, 2018, 21(5): 1-8.
[3]	王逸, 姚志洪, 蒋阳升, 赵斌, 谭宇. 基于自适应遗传算法的双环信号配时优化模型[J]. 工业工程, 2018, 21(5): 72-80.
[4]	罗孝羚, 蒋阳升, 吴奇, 姚志洪, 李思怡. 基于IC卡识别通勤客流的公交线路多模式调度[J]. 工业工程, 2018, 21(5): 81-86.
[5]	李彦瑾, 罗霞, 王莹. 考虑多节点拥堵的城市道路网级联失效仿真[J]. 工业工程, 2018, 21(4): 1-7.
[6]	姚志洪, 蒋阳升, 王逸. 车路协同环境下自适应信号配时优化模型[J]. 工业工程, 2018, 21(4): 8-14,33.
[7]	罗孝羚, 蒋阳升. 中小城市公交线网及发车频率同步优化[J]. 工业工程, 2017, 20(4): 25-30.
[8]	傅惠, 王叶飞, 陈赛飞. 面向宏观基本图的多模式交通路网分区算法[J]. 工业工程, 2020, 23(1): 1-9.
[9]	李妍峰, 龚桂琳. 基于用户异质性的旅游巴士定价研究[J]. 工业工程, 2020, 23(4): 69-74,130.
[10]	廖晔, 王顺意. 基于改进网络最大流的道路通行能力优化研究[J]. 工业工程, 2020, 23(5): 96-102.
[11]	曹振宇, 蒋阳升, 罗孝羚, 杨洁, 张姚. 中小城市直达公交网络优化[J]. 工业工程, 2020, 23(6): 117-123.
[12]	王宁, 张玉萍, 赵姣, 金子阳. 考虑碳排放及时间窗的LIRP模型与算法研究[J]. 工业工程, 2021, 24(2): 34-42.