p-枢纽中位问题与服务设备配置的联合优化模型

汪 瑜，车 通，张培文

-枢纽中位问题与服务设备配置的联合优化模型

汪 瑜，车 通，张培文

（中国民航飞行学院，机场工程与运输管理学院，四川 广汉 618307）

传统枢纽网络设计方法忽略了服务设备网络配置对于枢纽网络设计方案的影响。为了提高枢纽网络与服务设备之间的相互适应能力，并降低枢纽网络设计成本，以枢纽选址、各OD对路径及各边上配置的服务设备类型及其数量选择为决策变量，结合各边上预期服务设备最大数量及各类设备服务总时间限制等因素，构建-枢纽中位问题与服务设备配置的联合优化数学模型。选取2016年国内航空运输业中“9个城市、4种机型、72个OD对”数据进行验证，结果表明：与传统方法相比，该方法的枢纽网络设计成本降低了1.34%，且两者相互适应能力更强。另外，各边上预期配置的服务设备最大数量及各类设备服务总时间限制是影响两者相互适应能力的重要因素。

-枢纽中位；服务设备配置；枢纽网络；联合优化模型；OD对

0 引 言

-枢纽中位问题要求确定未来计划区域内个枢纽节点的位址、枢纽与非枢纽之间的连接关系以及各OD（Origin-Destination）流的运输路径。该问题是枢纽网络设计的核心并被广泛应用于航空、物流、邮政和电信等行业。针对该问题，早期的研究成果主要集中于对该类问题建模技巧的探讨[1-4]。随后的研究则更多关注于枢纽网络的规模经济性，并采用设置枢纽节点之间边上的折扣因子来对枢纽网络模型施加影响[5-9]。还有部分学者针对枢纽网络设计环境的不确定性，将枢纽网络设计参数（如单位流成本、OD流需求量等）视为随机变量，并从风险控制的角度研究枢纽网络的鲁棒优化设计（如区间鲁棒优化[10]、随机优化[11]）问题[12-17]。

上述方法在研究枢纽网络设计时，需要预先知道未来网络的边成本和各OD对流量等网络设计参数，但在实际枢纽网络设计时，网络上的边成本取决于该边上配置的服务设备类型及其数量，例如物流、航空和邮政等行业中任意两地间的服务成本取决于其配置的运输工具类型及其频次，又如电信业中两地间的数据传输成本则取决于其铺设的线缆类型及其数量。面对这样的情况，上述研究过程中仅使用折扣因子试图体现网络各边上所配置的服务设备类型及其数量的差异，很可能会导致与实际网络设计结果有较大的偏差，并产生次优的枢纽网络方案。因此，近期的研究则集中在枢纽网络规模经济性基础上，通过引入服务设备固定成本来探讨枢纽网络设计方法[18-21]。然而，仅仅将服务设备固定成本视为一个已知的网络设计参数，很难体现出网络的边成本和该边上所配置的服务设备类型及其数量的关系。事实上，枢纽网络设计过程中各OD对的运输路径决定了网络各边上所承载的OD对类型及其流量，并由此决定了实现网络设计成本最小的各边上所需配置的服务设备类型及其数量。这一决策结果又反过来确定了网络中实际的边成本，进而又会影响枢纽网络的设计结果。因此枢纽网络设计与服务设备配置是相互影响的两类决策问题。

鉴于此，本文首先给出带有枢纽设置成本的-枢纽中位问题数学模型，并分析服务设备配置决策与-枢纽中位问题的相互关系；然后，以枢纽选址、各OD对路径及各边上配置的服务设备类型及其数量选择为决策变量，结合各边上预期服务设备最大数量及各类设备服务总时间限制等因素，构建-枢纽中位问题与服务设备配置的联合优化数学模型；最后，采用国内航空运输城市对数据验证该方法的有效性。

1 问题描述与模型结构

1.1 p-枢纽中位问题与模型结构

在枢纽网络中，任意两个节点之间的单位流成本通常与距离成正比，且满足三角形边长不等式关系[21]。因此枢纽节点之间必然采用直达运输方式，而非枢纽与枢纽节点之间转运的次数不会超过二次。采用CAMPBELL四下标模型[3]表达方式，该问题可以表述如下：

式中，目标函数（1）为枢纽网络设计成本（运输成本和枢纽设置成本）最小化；约束（2）规定了枢纽节点的设置数量；约束（3）规定了任一OD对流量的转运必须要在枢纽节点上完成；约束（4）规定了任一OD对流量的运输任务必须全部完成；约束（5）和（6）规定了任一OD对的起点和终点有且只有一个枢纽时，如果需要中转至多只能中转一次，而当起点和终点都是枢纽时则只能采取直达运输。上面两式不仅限定了不同类型节点之间OD对流量的转运方式，而且还限定了这种转运方式的路径表达形式：当节点和都为枢纽时，其左端项中的变量必须全部为零，导致该OD对的路径形式被限定在———；当节点和中一个为枢纽、一个为非枢纽时，左端项中必有一个变量全部为零，导致该OD对的路径形式被限定在———或———。式（7）和（8）为变量类型和取值范围。

在没有汇运、转运和分运功能[22]的非枢纽网络中，各边的单位流成本是由服务该边的设备类型及其数量，以及边上仅服务于对应OD对的流量决定。但在枢纽网络中，其他OD对因汇运、转运和分运而流经该边，并导致该边上的流量增加而可以采用更大承载能力的设备服务（即“规模经济”）。正是如此，式（1）~（8）采用折扣因子来表示这种规模经济性。这一方法虽然可行，但忽略了网络边上的单位流成本c是由流经该边上的所有类型OD对及其流量（如式（9）右手项分母所示），以及配置的服务设备类型及其数量所产生的运输总成本（如式（9）右端项分子所示）共同决定这一关系。因此，传统方法在进行枢纽设计时往往会产生次优、甚至不可行的枢纽网络设计方案：

上式中分母表示任一边（，）可能在作汇运、转运和分运功能时，所有OD对流经该边的总流量。

1.2 联合优化问题与模型结构

式（9）去分母后转换为新的联合规划目标函数：

上式左端是网络中任一边（，）的流服务成本，等于该边上单位流成本乘以流经该边的所有OD对的流量之和；右端是关于该边服务成本的另一种表达方式，即用该边上所采用的服务设备类型及其数量所产生的服务成本来表示。对于网络中的服务总成本，可在式（10）基础上对所有边上的服务成本进行累计求和获取，如下式所示：

简化后，改写为下式：

为了探究边界条件的影响,我们还模拟了整个灌装体约束在钢壳中的情况。由于钢壳是热的良导体,温度结果与不加钢壳情况差别不大(数据从略)。应力结果比较在图6中(蓝线),可见加了边界钢壳约束后,芯片中拉应力有所减小,但焊点中的压应力有所增大。

故联合优化模型的目标函数式（1）可以改写如下：

联合优化模型的约束条件则由式（2）~（8），以及式（16）~（19）组成：

2 算例分析

选取航空运输业客运吞吐量排名靠前的9个城市（依次用序号1~9来表示）进行验证分析。9个城市各航线上机型（分别为150、200、250和300座位级）的单位运输成本和各机型机队的最大服务能力来自于国内某航空公司2016年生产运营数据，如表1所示。

表1 各机型飞机小时运营成本和最大生产能力

Tab.1 Hourly operation costs of each aircraft type and maximum service ability

9个城市对间的OD对客流量和期望飞行时间如表2所示，其数据来源于2016年国际航空运输协会MIDT（Market Information Data Types）。

表3给出了城市间航班运行频次（数据主要来源于SRS（Schedules Reference Service）航班计划）。本文将表3中的航班运行频次用作各边上预期配置的服务设备数量。

表2 城市之间的客流量和飞行时间

Tab.2 Passenger flow volumes and flight time between 9 cities

注：（）中代表客流量，单位为万人次；代表期望飞行时间，单位为h。

表3 城市之间航班班次

Tab.3 The number of flights between 9 cities

9个城市的枢纽机场建设成本由《中国民用航空第十三个五年规划》和2016年民航业发展统计公报汇总，并按照各城市机场的年旅客吞吐量占比，采用一定的比例修正获得[23，24]，具体如表4所示。

表4 枢纽建设成本

Tab.4 Construction costs of each hub airport

2.1 结果分析与对比

（1）联合决策结果。借助GUROBI求解器，算例在可接受时间范围内收敛，结果如表5所示。枢纽位址为{1，2，4}，网络运力配置方案如表6所示，总成本为769.36亿元。

（2）传统方法决策结果。首先利用航线运力配置方法[25]获取各边选用机型及其频次，由此获取单位流成本；其次将其作为网络设计参数，再利用式（1）~（8）进行枢纽网络设计（各个折扣因子如表5第1列所示），然后再据此进行航线运力优化配置决策，计算结果如表5所示。当=1.0，=0.8，=1.0时，枢纽网络方案为{1，2，8}，与联合决策的枢纽网络方案不同，基于此网络方案进行运力优化配置，预计总成本为779.86亿元，比联合决策模型的总成本高10.50亿元。整个航线运力配置方案如表7所示。当=0.8，=0.4，=0.8时，枢纽网络方案为{1，2，8}。但是基于后两个网络方案进行航线运力优化配置时，由于受航线上最大飞行频次和各机型飞机最大生产能力限制，导致无可行运力配置方案，即不能满足所有OD对客流量。

表5 两种方法的结果对比

Tab.5 Result comparison of two approaches

注：=0.8，=0.4，=0.8时，无法计算总成本。

表6 联合决策网络方案

Tab.6 Integrated decision network scheme

注：a中代表机型编号，代表相应机型飞机飞行频次占比。

表7 传统方法的网络方案（=1.0，=0.8，=1.0）

Tab.7 Network scheme for traditional approach（α=1.0，β=0.8，γ=1.0）

注：a中代表机型编号，代表相应机型飞机飞行频次占比。

（3）计算结果对比。对比以上数据可以发现，传统方法先进行枢纽网络设计后进行航线运力配置，会出现机型与航线适应度不高，甚至会出现无可行运力配置方案，原因主要在于式（1）~（8）的枢纽网络模型进行网络规划时仅考虑平均单位流成本和通过折扣因子反映规模经济性，这与实际最优的航线运力配置方案及成本差异较大。因此，本文所建立的联合决策方法优于传统方法。

2.2 网络参数的灵敏度分析

航线上预期配置的服务设备数量和各机型机队最大服务能力分别是指在考虑各航线及其相连节点空域和机场时刻资源，以及因飞机维修、飞行人力资源等因素制约时，预估的最大飞行频次和各类机型机队最大可用飞行时间，且两者对联合决策结果有着深刻影响。

为了分析上述因素对于枢纽网络方案的影响，本文以算例中的航线最大飞行频次为基准，分别对比基准的120%、100%和80%网络方案差异，具体结果如表8所示。对比120%F和100%F相对应的枢纽网络方案可以发现，虽然枢纽位址未发生变化，但因航线上飞行频次限制减弱而使得部分OD对路线发生改变，导致总运输成本降低了。对比80%F和100%F相对应的枢纽网络方案可以发现，由于航线最大飞行频次限制更加严格，使得枢纽位址发生改变，同时总运输成本也增加了。

表8 航线最大飞行频次对枢纽网络方案的影响

Tab.8 Impact of maximum flight frequency on hub network scheme

以算例中的各类机型机队最大可用飞行时间为基准，分别对比基准的120%、100%和80%网络方案差异，具体结果如表9所示。

表9 各类机型机队最大飞行时间对枢纽网络方案的影响

Tab.9 Impact of maximum flight time for each type of aircraft fleet on hub network scheme

因此，上述两个因素的估计值影响着枢纽网络设计方案，在枢纽网络设计工作中必须考虑航线上预期配置的服务设备数量和各机型机队最大服务能力限制，才能使设计的枢纽网络方案更利于未来实际的运营，从而为公司带来更好的效益。

3 结 论

本文提出了-枢纽中位问题和服务设备配置的联合优化数学模型，该模型本质上是在枢纽网络设计阶段考虑服务设备配置决策，并以服务所有OD对流量总成本最小为目标函数，综合考虑枢纽网络设计阶段的制约因素，以及服务设备配置决策阶段的资源限制条件。算例研究结果表明，该模型可以使得枢纽网络与服务设备配置之间的相互适应性更高，并使得决策结果更加符合实际要求。需要说明的是，各类资源限制因素变化都可能对枢纽网络设计方案产生影响，因此本文讨论了主要影响因素如何影响枢纽网络设计与服务设备配置决策结果，后续可进一步研究基于各指标值变动的枢纽网络设计与运力配置联合决策问题。

[1] 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.

[2] SKORIN-KAPOV D, SKORIN-KAPOV J, O’Kelly M E. Tight linear programming relaxations of uncapacitated p-hub median problems [J]. European Journal of Operational Research, 1996, 94 (3): 582-593.

[3] CAMPBELL J F. Hub location and the p-hub median problem [J]. Operations Research, 1996, 44 (6): 923-934.

[4] ERNST A T, KRISHNAMOORTHY M. An exact solution approach based on shortest-paths for p-hub median problems [J]. INPORMS Journal on Computing, 1998, 10 (2): 149-161.

[5] O’KELLY M E, BRYAN D, SKORIN-KAPOV D, et al. Hub network design with single and multiple allocation: a computational study [J]. Location Science, 1996, 4 (3): 125-138.

[6] 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.

[7] WOJAHN O W. Airline network structure and the gravity model [J]. Transportation Research Part E, 2001, 37 (4): 267-279.

[8] ELHEDHLI F S, HU X. Hub-and-spoke network design with congestion [J]. Computers & Operations Research, 2005, 32 (6): 1615-1632.

[9] CAMARGO R S D, MIRANDA G, LUNA H P. Benders decomposition for the uncapacitated multiple allocation hub location problem [J]. Computers and Operations Research, 2008, 35 (4): 1047-1064.

[10] 吴小欢, 朱金福, 吴薇薇. 航线网络区间型相对鲁棒优化设计[J]. 系统工程学报, 2012, 27 (1): 69-78.

[11] 葛伟, 朱金福, 吴薇薇, 等. 基于无容量限制的-枢纽中位问题的随机优化[J]. 系统工程理论与实践, 2013, 33 (10): 2674-2678.

[12] Conde E. Minmax regret location-allocation problem on a network under uncertainty [J]. European Journal of Operational Research, 2007, 179 (3): 1025-1039.

[13] KAZEMIAN I, AREF S. Hub location under uncertainty: a minimax regret model for the capacitated problem with multiple allocations [J]. International Journal of Supply Chain & Inventory Management, 2017, 2 (1): 1-19.

[14] O’KELLY M E, LUNA H P L, CAMARGO R S D, et al. Hub location problems with price sensitive demands [J]. Networks and Spatial Economics, 2015, 15 (4): 917-945.

[15] GHADERI A, RAHMANIANI R. Meta-heuristic solution approaches for robust single allocation p-hub median problem with stochastic demands and travel times [J]. The International Journal of Advanced Manufacturing Technology, 2016, 82 (9): 1627-1647.

[16] MERAKLI M, YAMAN H, Mannering F. Robust intermodal hub location under polyhedral demand uncertainty [J]. Transportation Research Part B (Methodological) , 2016, 86 (1): 66-85.

[17] 张锦, 秦东. 快递企业配送网络的鲁棒性及其提升对策研究[J]. 交通运输工程与信息学报, 2018 (3): 7-13.

[18] QIN Z, GAO Y. Uncapacitated p-hub location problem with fixed costs and uncertain flows [J]. Journal of Intelligent Manufacturing, 2017, 28 (1): 1-12.

[19] CAMPBELL J F, De MIRANDA G, De CAMARGO R S, et al. hub location and network design with fixed and variable costs[C]// Hawaii International Conference on System Sciences. 2015: 1059-1067.

[20] O'KELLY M E, CAMPBELL J F, CAMARGO R S D, et al. multiple allocation hub location model with fixed arc costs [J]. Geographical Analysis, 2015, 47 (1): 73-96.

[21] GHODRATNAMA A, ARBABI H R, AZARON A. A bi˗objective hub location-allocation model considering congestion [J]. Operational Research, 2018: 1-40.

[22] 朱金福. 航空运输规划[M]. 西安: 西北工业大学出版社, 2008: 238-240.

[23] 中国民用航空局, 国家发展和改革委, 交通运输部. 中国民用航空发展第十三个五年规划[R]. 北京: 中国民用航空局, 2016.

[24] 中国民用航空局. 2016年民航行业发展统计公报[R]. 北京: 中国民用航空局, 2017.

[25] 孙宏, 张培文, 汪瑜. 基于航线网络运力优化分配的机队规划方法[J]. 西南交通大学学报, 2010, 45 (1): 111-115.

An Integrated Optimization Model of-hub Median Problem and Service Facility Configuration

WANG Yu, CHE Tong, ZHANG Pei-wen

(School of Airport Engineering and Transportation Management, Civil Aviation Flight University of China, Guanghan 618307, China)

Traditional network design approach neglected the impact of network-wide location of service facility configuration on hub network designing scheme. In order to improve the mutual adaptability between hub network scheme and service facility configuration, the selections including the location of hubs, the itinerary of OD pairs and the allocation of both types and number of service facilities on each link were considered as the decision variables. The limitations of the maximum expected number of service facilities deploying on each link and the total service time of each facility type were treated as constraints. Then an integrated mathematical model of-hub median problem and service facility configuration was constructed. A numeric example with the scale of 9 cities, 4 types of aircraft and 72 OD pairs in domestic airline industry in 2016 is used to verify the feasibility. The results indicated that the approach can decrease the hub network designing cost by 1.34% and the adaptability of hub network scheme to service facility configuration was significantly raised as compared to the traditional approach. In addition, two limitations of the maximum number of service facilities deploying on each link and the total service time of each facility type are both main factors that impact their adaptability.

-hub median; service facility configuration; hub network; integrated optimization model; OD pair

1672-4747（2020）04-0023-09

F560.5

A

10.3969/j.issn.1672-4747.2020.04.003

2020-03-12

国家自然科学基金项目（U1733127）；中国民航飞行学院民航运输规划智能决策研究所计划项目（JG2019-32）；大学生创新创业训练项目（S201910624050）

汪瑜（1983—），男，中国民航飞行学院副教授，工学博士，研究方向为民航运输系统优化，E-mail：wangyu2001.111@163.com

汪瑜，车通，张培文.-枢纽中位问题与服务设备配置的联合优化模型[J]. 交通运输工程与信息学报，2020, 18(4): 23-30, 60

（责任编辑：刘娉婷）