# A Combined Average-Case and Worst-Case Analysis for an Integrated Hub Location and Revenue Management Problem

Authors: Jia-Zhen Huo; Yan-Ting Hou; Feng Chu; Jun-Kai He
Journal: Discrete Dynamics in Nature and Society
 (2019)

---

## Abstract

This paper investigates joint decisions on airline network design and capacity allocation by integrating an uncapacitated single allocation p-hub median location problem into a revenue management problem. For the situation in which uncertain demand can be captured by a finite set of scenarios, we extend this integrated problem with average profit maximization to a combined average-case and worst-case analysis of this integration. We formulate this problem as a two-stage stochastic programming framework to maximize the profit, including the cost of installing the hubs and a weighted sum of average and worst case transportation cost and the revenue from tickets over all scenarios. This model can give flexible decisions by putting the emphasis on the importance of average and worst case profits. To solve this problem, a genetic algorithm is applied. Computational results demonstrate the outperformance of the proposed formulation.


---

## Body

## 1. Introduction

Since the airline deregulation act enacted in 1978, airlines introduce the concept of revenue management, restructure airline network and develop centralized airline control centers to establish and sustain a competitive edge in this market-driven environment [1]. Hence, hub location and revenue management play significant roles in boosting the development of the airline industry. New challenges remain in these two disciplines.Hub location problem by locating the hubs and connecting fewer links from the hubs to the non-hubs makes an airline network obtain more traffic flows and largely reduce the cost. In the area of revenue management, the flows can be performed as air tickets which can be effectively allocated to different segments of customers to obtain more revenue. Hence, these two disciplines are closely related. Until now, only two publications [2, 3] have considered about integrating the hub location into the revenue management to maximize the airline profit on the one hand. These studies consider the average profit, which is difficult to identify the underlying distribution probability. On the other hand, our research is also inspired by a weight-based combined consideration of the average-case and worst-case values in [4]. They provide a flexible decision for an emergency response network design problem by putting relative emphasis on average-case and worst-case cost. Consequently, our aim is to maximize the profit of integrating a hub location problem into a revenue management problem and to provide less conservative and restrictive solutions by a weight-based combination of average-case and worst-case profits.The main contribution of our research is developing a new mathematical model and proposing flexible decisions for an integrated problem of hub location and revenue management. In this paper, we present a weight-based two-stage stochastic programming framework formulation by combining average-case and worst-case profits. To reduce the computation time, a genetic algorithm (GA) has been applied. The results show that our formulation outperforms the other one only considering the average case. Accordingly, the effects of the weight value, the network configuration and the discount factor on the profit are discussed.The organization of this paper is as follows: Section2 presents a brief literature review. Section 3 describes an integrated problem of hub location and revenue management. Section 4 details the solution methodology. Section 5 discusses the results. Section 6 summarizes our conclusions.


## 2. Literature Review

Since [5] introduces the concept of revenue management, the research on revenue management has received tremendous attention in both academia and industry. The main problems in revenue management can be categorized: pricing, capacity control, overbooking, auctions and forecasting [6]. This paper focuses on capacity control problem by allocating the capacities on all itineraries of an airline network to different booking classes segmented by customer demand over a fixed period from departure to maximize the airline revenue. Early publications provide an effective analysis of revenue management on single flight leg without consideration of network effects ([5, 7]). Progress in this area has moved forward to network revenue management problem which is proposed by [8]. The main difference between these two problems is that dramatic expansion of the airline network makes the itineraries largely increase. The research about network topology in network revenue management can be classified by: on the one hand, for multiple legs without a specific network structure, some research ([9–14]) decomposes the multi-leg problem into many single leg problems and then makes a decision on allocating the capacities to every single leg. The research on the hub-and-spoke network also has received significant attention on the other hand. [15] considers the network revenue management in a hub-and-spoke network. In their assumptions, a single hub can serve N spokes. [16] studies the capacity allocation in a two-airline alliance under competitions in a hub-and-spoke network. [17] studies the airline revenue management with consideration of a competitor’s behavior under simultaneous price and capacity competition in a hub-and-spoke network. [18] explores the impact of structural properties on a hub-to-hub network revenue management problem. As seen from the above literature, the research of airline revenue is closely relevant to airline network structure. Until now, only two papers ([2, 3]) focus on integrated research of hub location and revenue management. Our paper continues to consider this integrated problem. For reviews on revenue management, we refer the readers to e.g., [19, 20].The hub is used to largely reduce the links between the origins and the destinations in an airline network [21]. Hub location problem is a discipline which focuses on locating the hubs from a set of nodes and routing the links from the hubs to the non-hubs. Since [22, 23] contribute the first mathematical formulation and the solution method to the hub location problem, this research has received constant attention. Four fundamental hub location problems are [24]: (1) p-hub median, (2) p-hub center, (3) uncapacitated or capacitated p-hub location, and (4) hub covering. Diverse network topologies also play a role in the development of these four problems, e.g. tree network, star-star network, cycle network and hub line network. This paper focuses on a star-star p-hub location problem. [25] studies a single allocation p-hub median problem in a star-star network structure. [26] minimizes the routing cost between the hubs and the non-hubs in a star-star network. [27] formulates two separated problems on a star-star network. One is p-hub center problem, which is to minimize the maximum length of the paths between different nodes. The other is p-hub median problem with bounded path length to minimize the cost. Then they analyze the performances of these two problems. [28] explores the hardness of a star p-hub center problem. For poor service quality incurred by minimizing the routing cost, [29] proposes Δβ-star single-allocation p-hub center problem. A min-max criterion is introduced by maximizing the service quality and minimizing the cost. These above research with a cost-based objective assume that every origin or destination node should be served. However, if some origin & destination (O&D) pairs are not profitable, the airline isn’t necessary to operate them. This assumption is relaxed by [30]. They measure the tradeoff between the profits of the commodities served on some O&D pairs and the cost of hub location and routing between the hubs and the non-hubs. Our paper also considers the hub location problem from the perspective of optimizing the profit. The overviews on the hub location problem ([21, 31]) provide a detailed treatment.This paper is based on a very recent work [3]. They integrate an uncapacitated single allocation p-hub median problem and a revenue management problem in a star-star network. A two-stage stochastic programming formulation is presented to maximize the profit. In the first stage, the hub location, the link between the hub and the non-hub and the protection level of tickets for different booking classes are determined. The booking limit of tickets can be obtained in the second stage. The demand is captured in a set of discrete scenarios under the average case. The average-case analysis is effective when a probability distribution is known. However, demand information is always hard to obtain which makes the results more sensitive and less accurate. To address this concern, robust optimization is proposed as an alternative method to handle data uncertainty. Instead of considering distributional information, robust optimization assumes a defined set of values that any uncertainty can be realized. The solution is obtained under the realization of most unfavorable uncertainty in this set. That is to say, robust optimization analyzes the worst-case value. But choosing an uncertain parameter set makes the result over-conservative. For more information regarding the average-case and worst-case analysis, the readers are referred to [32, 33]. To overcome these shortcomings, the research on the complementary effects of worst-case and average-case analysis is appeared ([34–38]). In addition, there is relatively sparse research regarding the average-case or worst-case analysis for a two-stage optimization problem. [39] explores the performance between the worst-case cost of two-stage robust optimization and the expected cost of two-stage stochastic programming. [40] discusses the performance between a two-stage scenario-based stochastic optimization model and a two-stage robust optimization formulation in response management for residential appliances under real-time price-based demand. The above research still explores the pros and the cons between these two methods rather than providing a more flexible solution. The recent advance in the research is proposed by [4]. This paper formulates a two-stage stochastic programming framework for an emergency response network design problem to minimize a weighted sum of average and worst case costs. This contribution can give the flexibility of network configuration by putting relative emphasis on the average-case and the worst-case costs. In our paper, this research is introduced into an integrated problem of hub location and revenue management.


## 3. Problem Description

We consider an integrated problem of an uncapacitated single allocationp hub median location problem and a network revenue management problem. In this star-star network, a central hub 0 is predefined. The hubs must be connected to the central hub 0. The number of hub j is P and these hubs are chosen from a set of nodes I. The non-hub i refers to the node that hasn’t been chosen as a hub. Consequently, two stars are formed: (1) the links between the hubs and the non-hubs, and (2) the other links between the hubs and the central hub. Here, the O&D pairs in this network can traverse at least one hub and at most two hubs (not including the central hub). That is to say, all these O&D pairs can be made of these two basic links: (1) Type1 is the link between non-hub i and hub j; (2) Type2 is used for connecting hub j to central hub 0. Figure 1 illustrates the underlying star-star network structure in this paper.Figure 1
Airline star-star network.We have the following assumptions for our problem:(i)
The location of the central hub 0 is predefined.(ii)
No direct link is allowed between the two hubs.(iii)
Each non-hub can be allocated to only one hub and direct link between the two non-hubs is not allowed.(iv)
Only the aircraft type with capacityQ1 can be available on Type1 link. Type2 link allows the aircraft type with capacity Q2.(v)
The capacities onType1 and Type2 links are considered. The capacity is relevant to the number of flights passing over this link.(vi)
The ticket price at each fare classk is given.(vii)
The booking limit of tickets for the fare classk is related to uncertain demand and the protection level of tickets. Once the protection level is set, upgrading to a higher fare class or changing to a later or earlier flight shouldn’t be allowed. Demand for different types of fares should be independent. The arrival order of demand is not considered.(viii)
Cancellations and no-shows are not considered.(ix)
Cost discount factorα reflects the economies of scale on unit cost on Type2 link.


### 3.1. Notations

The definitions of parameters and decision variables are summarized as follows:Indices i, m: indices for nodes. j: index for hubs. s: index for scenarios. k: index for fare classes.Parameters I: set of nodes in the network. P: the number of hubs located in the network. S: set of scenarios captured by uncertain demand. K: set of fare classes. w 1: weight of the average-case value over all scenarios S, where ω1∈[0,1],  ω1+ω2=1. w 2: weight of the worst-case value over all scenarios S, where ω2∈[0,1],  ω1+ω2=1. f i j: distance from non-hub i to hub j, for i∈I and j∈I. f j 0: distance from hub j to central hub 0, for j∈I. C 1 k: transfer cost (per unit distance in a flight) on Type1 link at fare class k, where k∈K. C 2 k: transfer cost (per unit distance in a flight) on Type2 link at fare class k, where k∈K. In addition, C2k=αC1k, α is a discount factor to describe the effect of economies of scale, α∈[0,1]. d i m k s: demand on O&D pair between origin node i and destination node m at fare class k under scenario s, where s∈S, i∈I, m∈I and k∈K. p i m k s: the probability of scenario s under the average case on O&D pair between origin i and destination m at fare class k, where s∈S, i∈I, m∈I and k∈K. r i m k: ticket price on O&D pair between origin i and destination m at fare class k, where i∈I, m∈I and k∈K. N o i j: capacity on Type1 link. That is, the number of flights can pass over Type1 link, where i∈I and j∈I. N o j 0: capacity on Type2 link. That is, the number of flights can pass over Type2 link, where j∈I. Q 1: the transport capacity of a specific aircraft on Type1 link is Q1. Q 2: an aircraft’s capacity on Type2 link is limited to a certain amount Q2 referring to passengers volume. F j: fixed cost for installing a hub j, for j∈I. F ′: fixed cost for installing a central hub 0. M: a very large integer.Variables y i m k s: booking limit of tickets at each fare class k on O&D pair between origin i and destination m under scenario s. z i m k: protection level of tickets at each fare class k on O&D pair between origin i and destination m. x j j: binary decision variable. xjj equals to 1 if node j is a hub node and 0 otherwise. x i j: binary decision variable. If non-hub i is routed to hub j, xij equals to 1. Otherwise, xij=0.


### 3.2. A Weight-Based Two-Stage Model

This paper proposes a two-stage formulation for the integrated problem of hub location and revenue management. The first stage decision is the location of the hub, routing the links and the protection level of airline tickets for different fare classes. In the second stage, the booking limit of tickets is employed in response to the arrivals of customers orders. Uncertain demand is captured byS scenarios. In the average case, the probability under every scenario s is pimks. ω1 and ω2 represent the weights of the average-case value and the worst-case value, respectively, where ω1,ω2∈[0,1] and ω1+ω2=1.A model with combining the average-case and worst-case values via a pair of weights based on two-stage stochastic programming is presented. This model is as follows:(1)maxω1∑i∈I∑m∈I∑k∈K∑s∈Spimksyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC1kpimksfijyimksQ1+pmiksfjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC2kpimksfj0yimksQ2+pmiksf0jymiksQ2xij1-xmj+ω2mins∈S⁡∑i∈I∑m∈I∑k∈Kyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈KC1kfijyimksQ1+fjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈KC2kfj0yimksQ2+f0jymiksQ2xij1-xmj-∑j∈IFjxjj-F′(2)Subjectto∑j∈Ixij≤1∀i∈I(3)∑j∈Ixjj=P(4)xij≤xjj∀i,j∈I(5)yimks≤dimks∀i,m∈I,∀k∈K,∀s∈S(6)yimks≤Zimk∀i,m∈I,∀k∈K,∀s∈S(7)∑m∈I∑k∈KZimkQ1+∑m∈I∑k∈KZmikQ1≤∑j∈INoijxij+Mxii∀i∈I(8)∑i∈I∑m∈I/i∑k∈KZimkQ2xij1-xmj+∑i∈I∑m∈I/i∑k∈KZmikQ2xij1-xmj≤Noj0xjj∀j∈I(9)xij,xjj∈0,1∀i,j∈I(10)yimks,Zimk∈Z+∀i,m∈I,∀k∈K,∀s∈SThe objective function (1) is to maximize a weighted sum of average and worst case profits. The first term represents the average of: (a) the revenue from tickets sales for different fare classes on O&D pair between origin i and destination m, (b) the transportation cost on Type1 link, and (c) the transportation cost on Type2 link, with a weight ω1. The second term represents the minimum profit over all S scenarios with an associated weight ω2. The profits include the revenue on O&D pairs, and the transportation costs on Type1 and Type2 links. The last two terms represent the installation cost of the hubs and the central hub. Here the profit can be determined by putting relative emphasis on the values of weights ω1 and ω2. Constraint (2) indicates that each non-hub must be allocated to one hub. Constraint (3) defines the number of the hubs in this star-star network. Constraint (4) assures that node i can be allocated to hub j only when j is selected as a hub. That is to say, all flows are sent and received via the hubs to avoid direct connections among non-hubs. Constraint (5) and Constraint (6) specify that the booking limit of the tickets for each fare class k is not over the demand and the protection level. Constraint (7) and Constraint (8) limit the flow on Type1 link and Type2 link, respectively. In our problem, the flow can be interpreted as the number of the flights. Zimk/Q1 and Zmik/Q1 indicate the number of the flights on Type1 link used by O&D pairs im and mi. The number of the flights can be described as Zimk/Q2 and Zmik/Q2 on Type2 link. Constraint (7) indicates that the protection level of the flights on Type1 link used by O&D pair im and mi can’t overpass its fixed capacity Noij. A large-valued integer M on the right-hand side of Constraint (7) is used for ensuring this inequality meaningful even when xij=0 and xii=1. Constraint (8) describes the capacity restriction of Type2 link. The protection level of the flights on Type2 link used by O&D pair im and mi should be less than fixed capacity Noj0. In our network, xij(1-xmj)=1 if Type2 link is used by O&D pair im and xij(1-xmj)=0 otherwise. For xij(1-xmj)=1, xij=1 and xmj=0 is the only case satisfying this equation. In this case, this O&D pair comprises Type1 link and Type2 link when the origin node i and the destination node m haven’t routed to the same hub j. Constraint (9) and Constraint (10) identify that xij and xjj are binary variables and yimks and Zimk are integers.We can further simplify objective (1) by introducing an auxiliary variable Ψ(Ψ≥0). Then new model will be(11)maxω1∑i∈I∑m∈I∑k∈K∑s∈Spimksyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC1kpimksfijyimksQ1+pmiksfjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC2kpimksfj0yimksQ2+pmiksf0jymiksQ2xij1-xmj+ω2Ψ-∑j∈IFjxjj-F′(12)Subjectto2)-(10Ψ≤∑i∈I∑m∈I∑k∈Kyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈KC1kfijyimksQ1+fjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈KC2kfj0yimksQ2+f0jymiksQ2xij1-xmj∀s∈S(13)Ψ≥0


## 3.1. Notations

The definitions of parameters and decision variables are summarized as follows:Indices i, m: indices for nodes. j: index for hubs. s: index for scenarios. k: index for fare classes.Parameters I: set of nodes in the network. P: the number of hubs located in the network. S: set of scenarios captured by uncertain demand. K: set of fare classes. w 1: weight of the average-case value over all scenarios S, where ω1∈[0,1],  ω1+ω2=1. w 2: weight of the worst-case value over all scenarios S, where ω2∈[0,1],  ω1+ω2=1. f i j: distance from non-hub i to hub j, for i∈I and j∈I. f j 0: distance from hub j to central hub 0, for j∈I. C 1 k: transfer cost (per unit distance in a flight) on Type1 link at fare class k, where k∈K. C 2 k: transfer cost (per unit distance in a flight) on Type2 link at fare class k, where k∈K. In addition, C2k=αC1k, α is a discount factor to describe the effect of economies of scale, α∈[0,1]. d i m k s: demand on O&D pair between origin node i and destination node m at fare class k under scenario s, where s∈S, i∈I, m∈I and k∈K. p i m k s: the probability of scenario s under the average case on O&D pair between origin i and destination m at fare class k, where s∈S, i∈I, m∈I and k∈K. r i m k: ticket price on O&D pair between origin i and destination m at fare class k, where i∈I, m∈I and k∈K. N o i j: capacity on Type1 link. That is, the number of flights can pass over Type1 link, where i∈I and j∈I. N o j 0: capacity on Type2 link. That is, the number of flights can pass over Type2 link, where j∈I. Q 1: the transport capacity of a specific aircraft on Type1 link is Q1. Q 2: an aircraft’s capacity on Type2 link is limited to a certain amount Q2 referring to passengers volume. F j: fixed cost for installing a hub j, for j∈I. F ′: fixed cost for installing a central hub 0. M: a very large integer.Variables y i m k s: booking limit of tickets at each fare class k on O&D pair between origin i and destination m under scenario s. z i m k: protection level of tickets at each fare class k on O&D pair between origin i and destination m. x j j: binary decision variable. xjj equals to 1 if node j is a hub node and 0 otherwise. x i j: binary decision variable. If non-hub i is routed to hub j, xij equals to 1. Otherwise, xij=0.


## 3.2. A Weight-Based Two-Stage Model

This paper proposes a two-stage formulation for the integrated problem of hub location and revenue management. The first stage decision is the location of the hub, routing the links and the protection level of airline tickets for different fare classes. In the second stage, the booking limit of tickets is employed in response to the arrivals of customers orders. Uncertain demand is captured byS scenarios. In the average case, the probability under every scenario s is pimks. ω1 and ω2 represent the weights of the average-case value and the worst-case value, respectively, where ω1,ω2∈[0,1] and ω1+ω2=1.A model with combining the average-case and worst-case values via a pair of weights based on two-stage stochastic programming is presented. This model is as follows:(1)maxω1∑i∈I∑m∈I∑k∈K∑s∈Spimksyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC1kpimksfijyimksQ1+pmiksfjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC2kpimksfj0yimksQ2+pmiksf0jymiksQ2xij1-xmj+ω2mins∈S⁡∑i∈I∑m∈I∑k∈Kyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈KC1kfijyimksQ1+fjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈KC2kfj0yimksQ2+f0jymiksQ2xij1-xmj-∑j∈IFjxjj-F′(2)Subjectto∑j∈Ixij≤1∀i∈I(3)∑j∈Ixjj=P(4)xij≤xjj∀i,j∈I(5)yimks≤dimks∀i,m∈I,∀k∈K,∀s∈S(6)yimks≤Zimk∀i,m∈I,∀k∈K,∀s∈S(7)∑m∈I∑k∈KZimkQ1+∑m∈I∑k∈KZmikQ1≤∑j∈INoijxij+Mxii∀i∈I(8)∑i∈I∑m∈I/i∑k∈KZimkQ2xij1-xmj+∑i∈I∑m∈I/i∑k∈KZmikQ2xij1-xmj≤Noj0xjj∀j∈I(9)xij,xjj∈0,1∀i,j∈I(10)yimks,Zimk∈Z+∀i,m∈I,∀k∈K,∀s∈SThe objective function (1) is to maximize a weighted sum of average and worst case profits. The first term represents the average of: (a) the revenue from tickets sales for different fare classes on O&D pair between origin i and destination m, (b) the transportation cost on Type1 link, and (c) the transportation cost on Type2 link, with a weight ω1. The second term represents the minimum profit over all S scenarios with an associated weight ω2. The profits include the revenue on O&D pairs, and the transportation costs on Type1 and Type2 links. The last two terms represent the installation cost of the hubs and the central hub. Here the profit can be determined by putting relative emphasis on the values of weights ω1 and ω2. Constraint (2) indicates that each non-hub must be allocated to one hub. Constraint (3) defines the number of the hubs in this star-star network. Constraint (4) assures that node i can be allocated to hub j only when j is selected as a hub. That is to say, all flows are sent and received via the hubs to avoid direct connections among non-hubs. Constraint (5) and Constraint (6) specify that the booking limit of the tickets for each fare class k is not over the demand and the protection level. Constraint (7) and Constraint (8) limit the flow on Type1 link and Type2 link, respectively. In our problem, the flow can be interpreted as the number of the flights. Zimk/Q1 and Zmik/Q1 indicate the number of the flights on Type1 link used by O&D pairs im and mi. The number of the flights can be described as Zimk/Q2 and Zmik/Q2 on Type2 link. Constraint (7) indicates that the protection level of the flights on Type1 link used by O&D pair im and mi can’t overpass its fixed capacity Noij. A large-valued integer M on the right-hand side of Constraint (7) is used for ensuring this inequality meaningful even when xij=0 and xii=1. Constraint (8) describes the capacity restriction of Type2 link. The protection level of the flights on Type2 link used by O&D pair im and mi should be less than fixed capacity Noj0. In our network, xij(1-xmj)=1 if Type2 link is used by O&D pair im and xij(1-xmj)=0 otherwise. For xij(1-xmj)=1, xij=1 and xmj=0 is the only case satisfying this equation. In this case, this O&D pair comprises Type1 link and Type2 link when the origin node i and the destination node m haven’t routed to the same hub j. Constraint (9) and Constraint (10) identify that xij and xjj are binary variables and yimks and Zimk are integers.We can further simplify objective (1) by introducing an auxiliary variable Ψ(Ψ≥0). Then new model will be(11)maxω1∑i∈I∑m∈I∑k∈K∑s∈Spimksyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC1kpimksfijyimksQ1+pmiksfjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈K∑s∈SC2kpimksfj0yimksQ2+pmiksf0jymiksQ2xij1-xmj+ω2Ψ-∑j∈IFjxjj-F′(12)Subjectto2)-(10Ψ≤∑i∈I∑m∈I∑k∈Kyimksrimk-∑i∈I∑mϵI/i∑j∈I∑k∈KC1kfijyimksQ1+fjiymiksQ1xij-∑i∈I∑mϵI/i∑j∈I∑k∈KC2kfj0yimksQ2+f0jymiksQ2xij1-xmj∀s∈S(13)Ψ≥0


## 4. Genetic Algorithms

When the network size increases, the computational time will largely increase until finding the best solution. In this paper, we introduce a GA, which is proposed by [3]. GA introduced by [41] is based on natural biological evolution and has been successfully applied to various combinatorial optimization problems in hub location problem ([42–52]). After generating a feasible solution of xij and xjj based on proposed model in Section 3.2 by GA, the other descisions are obtained by using CPLEX. This algorithm avoids introducing more variables and constraints induced by the linearization process and effectively reduces the computation time.The main components of implementing the GA are given as follows:(A) Initial Population Generation.The genetic code of each individual in our problem is a N-dimension matrix generated by a uniform distribution over [0,1], where N is the number of the nodes. We name this matrix as Matrix A. P highest entries from the diagonal of Matrix A need to be turned into 1 and the other entries on this diagonal can be rewritten as 0. The entries equalling 1 indicate the locations of the hubs, namely xjj=1 and the other entries 0 indicates otherwise, xjj=0. Next, we replace the entries on the overlaps between the columns where the entries of this diagonal equal to 1 and the rows where the entries of this diagonal equal to 0. Comparing the overlaps in the same row, the highest entry needs to be rewritten as 1 which means xij=1. Beyond that, other entries in addition to the ones xij=1, xjj=1 and xjj=0 need to be rewritten as 0 which mean xij=0. In addition, if the overlaps in the same row have the same values, we choose the first highest one as xij=1. According to the above principles, we obtain a 0-1 matrix as Matrix B. Here Matrix B represents the network structure. The size of initial population stays the same from generation to generation.(B) Fitness Value.The fitness value of each individual is obtained by calculating the reciprocal of the profit obtained from the model in Section 3.2.(C) Selection Operation.In order to reproduce the offspring, a selection process aims to choose the parents who will mate. The parents can be chosen from the generation by random selection.(D) Crossover Operator.The offspring can be generated by applying a crossover operator to the selected parents. The crossover procedure is as follows:(14)Pnew1=bPf+1-bPm(15)Pnew2=1-bPf+bPmwhere Pnew1 and Pnew2 are the offsprings. Pf and Pm represent the two parents. b is a random N-dimensional matrix chosen uniformly over the interval [0,1], where N is the number of the nodes. The same b is used in every combination.(E) Mutation Operator.Premature convergence to suboptimal solutions may occur because some genetic codes are lost or unexplored from the above steps. To avoid this problem, mutation process is needed. Mutation can perform sporadic and random changes in offsprings’ genetic codes with a mutation probability. There are three mutation operators: Elimination, Transposition and Conversion. Only one of these three operators can be selected randomly in each iteration. The details of all the operators are as follows:(a)Elimination. The hubs need to be relocated by subtracting the highest entry on the same diagonal of Matrix A from 1.(b)Transposition. The assignment between the non-hubs and the hubs can be recaptured by transposing Matrix A.(c)Conversion. The network structure can be redesigned. A l-dimension matrix (l<N) is removed from the bottom-right corner of Matrix A. This random integer l is generated from the multiplication of the nodes N and a random number drawn from a uniform distribution [0,0.5]. A new l-dimension matrix uniformly distributed between 0 and 1 can refill the empty space of Matrix A.After the above mentioned, new individual can be produced. The valuesxij and xjj of each individual can be inputted into the simplified model in Section 3.2 as the parameters. We use CPLEX to obtain other values yimks and zimk. This process is iteratively repeated until a suitable stopping criterion can be met.(F) Stopping Criterion.This hybrid algorithm can be terminated when any of the following conditions is satisfied:(i)
The best solution hasn’t been changed after 10 iterations;(ii)
The running time is over 8 hours.


## 5. Computational Study

In this section, we perform extensive computational experiments to analyze the performance of the proposed mathematical model. The parameter settings are provided in Section5.1 and the solutions are analyzed in Section 5.2.


### 5.1. Test Bed

We use the data set from [3]. The values of (N,P) are set at (5,2), (10,3), (10,5), (15,3), (15,5), (15,7), (20,3), (20,5), (20,7), (25,3), (25,5) and (25,7). The cost of installing hub Fj or a central hub F′ is drawn from U(1200000,2400000). Two fare classes (K=2) provide a business class k=1 and an economic class k=2. For Type1 link, the transportation cost C11 per unit distance per flight on the class k=1 is drawn from U(7,14) and the transportation cost C12 per unit distance per flight for k=2 is γC11, where γ~U(0.5,1). We consider C21 = αC11 and C22=αC12, where α∈{0.2,0.4,0.6}. Since [3] does not provide any information regarding the distance, we set fij=1 and fj0=1. The capacity Noij on Type1 link is drawn from a discrete uniform distribution DU(1,3). For Type2 link, the capacity Noj0 is drawn from DU(3,6). The capacity Q1 of the aircraft used on Type1 link and Q2 on Type2 link are 100 and 200, respectively. The ticket price at k=2 is drawn from a continuous distribution U(600,3600). And the price at k=1 is 1.5 higher than the one at k=2. We set M=100000.We setS=10 and the probability of all the scenarios is the same, namely 1/S. The demand for each fare class is drawn from the interval between low demand and high demand [3.75,6.25]. 80% of the demand come from the economic class and 20% are from the business class. We also test six weight vectors (ω1,ω2), such that (0,1), (0.2,0.8), (0.4,0.6), (0.6,0.4), (0.8,0.2) and (1,0). Note that the weight combination (1,0) represents that the objective of our problem is to maximize the average profit over all scenarios. The weight (0,1) stands for maximizing the worst-case profit. The mixed weight combinations (0.2,0.8), (0.4,0.6), (0.6,0.4) and (0.8,0.2) mean maximizing a weighted sum of average and worst case profits over all scenarios. In addition, the probability of crossover is 0.8 and the probability of mutation is 0.15. The maximum number of generation is 50 and the population size is 20. We extend the number of scenarios to 10. When the number of scenarios is three times more than the number used in [3], our problem becomes more challenging if the population size is still set 50 as in [3]. Therefore, we reduce the population size to 20 so that this process can continue in limited iterative.


### 5.2. Results

This hybrid algorithm was implemented in Matlab R2017b using Yalmip R20171121 and IBM ILOG Cplex Optimization Studio 12.8.0. All runs were done on a MacBook Pro with an Intel Core i7 CPU 3GHz processor at 8GB of RAM under macOS High Sierra 10.13.3 operating system. To demonstrate good performance of our mathematical formulation, we conducted 216 computational experiments considering 6 weight vectors with varying 12 network sizes as well as 3 discount factors.The organization of this section is as follows: First, we report computational results under different parameter valuesN and P, weight vector (ω1,ω2) and discount factor α in Tables 1 and 2. Especially, the results under (0,1) and (1,0) are shown in Table 1 and the results under the mixed weight combinations are presented in Table 2. Second, Figure 2 is used for comparing the performance of our proposed model and the model in [3]. The impact of α on the profits can also be illustrated in Figure 2. Finally, we present the results of the worst-case values in Table 3 and investigate the correlation between the worst-case value and the profit in Table 4.Table 1
Profits under(0,1) and (1,0).
α N P (ω1, ω2) D e v ( 0,1 ) ( 1,0 ) 0.2 5 2 5442266.67 5423379.87 18886.80 10 3 4918937.71 4887976.87 30960.84 10 5 8293400.06 8262616.21 30783.85 15 3 4160728.26 4137520.58 23207.68 15 5 7562556.80 7534413.37 28143.43 15 7 11755282.60 11720169.74 35112.86 20 3 2360179.15 2300020.24 60158.91 20 5 5759796.83 5512755.65 247041.18 20 7 8522527.33 8486613.75 35913.58 25 3 892883.30 879578.93 13304.37 25 5 4080747.68 4063431.36 17316.32 25 7 8384020.92 8053287.16 330733.76  0.4 5 2 5442267.26 5423380.53 18886.73 10 3 4918942.44 4890648.04 28294.40 10 5 8293404.64 8262621.05 30783.59 15 3 4160738.83 4137529.01 23209.82 15 5 7562570.08 7534424.29 28145.79 15 7 11850706.76 11720184.41 130522.35 20 3 2486257.40 2400330.06 85927.34 20 5 5550614.23 5512778.82 37835.41 20 7 8522586.77 8486633.64 35953.13 25 3 892917.49 879603.28 13314.21 25 5 4080550.59 4063463.12 17087.47 25 7 8089252.79 8053316.86 35935.93  0.6 5 2 5442267.86 5442301.65 -33.79 10 3 4922407.92 4904121.97 18285.95 10 5 8294319.76 8275448.45 18871.31 15 3 4202882.06 4217080.62 -14198.56 15 5 7585948.98 7603389.82 -17440.84 15 7 11764264.73 11613095.26 151169.47 20 3 2540668.89 2489654.33 51014.56 20 5 5946942.46 6018106.15 -71163.69 20 7 9494836.41 8683483.27 811353.14 25 3 1039461.55 1263250.70 -223789.15 25 5 4208509.22 4489668.85 -281159.63 25 7 8208922.00 8439144.76 -230222.76Table 2
Profits under mixed weight combinations.
α N P (ω1, ω2) (0.2,0.8) (0.4,0.6) (0.6,0.4) (0.8,0.2) 0.2 5 2 5438489.31 5434711.95 5430934.59 5427157.23 10 3 4913467.23 4907997.64 4900371.10 4894182.34 10 5 8287303.68 8281207.29 8275110.91 8269014.53 15 3 4158103.96 4154727.13 4150791.16 4145561.69 15 5 7558990.36 7554668.13 7550225.45 7544160.12 15 7 11750609.00 11745627.15 11739865.46 11731346.52 20 3 2329636.54 2358141.43 2356525.42 2311386.40 20 5 5756168.69 5541820.03 5534669.13 5525588.27 20 7 8518495.08 8512989.30 8506425.30 8498186.76 25 3 892821.19 892421.61 891341.44 888308.81 25 5 4080580.66 4080098.79 4077652.35 4073697.67 25 7 8087887.20 8383805.11 8382705.01 8070721.25  0.4 5 2 5438489.92 5434712.57 5430935.22 5427157.88 10 3 4913472.45 4908002.46 4900375.65 4897055.01 10 5 8287308.31 8281211.98 8275115.64 8269019.31 15 3 4158123.59 4154780.97 4150767.12 4145572.12 15 5 7559010.28 7554681.63 7550236.36 7544173.58 15 7 11848845.27 11745641.74 11739880.18 11731361.18 20 3 2485358.09 2483758.63 2481010.23 2412575.20 20 5 5547325.79 5541841.01 5534690.21 5525611.37 20 7 8518582.62 8513134.96 8506445.13 8498206.57 25 3 892825.69 892446.01 891519.07 888333.16 25 5 4080612.63 4080130.36 4077683.94 4073694.68 25 7 8087920.51 8085342.31 8080574.24 8070745.42  0.6 5 2 5438605.23 5434908.81 5431212.39 5427515.97 10 3 4917136.78 4920304.97 4917254.78 4913525.68 10 5 8291540.99 8288510.64 8284498.40 8280123.99 15 3 4207659.77 4211795.89 4215598.76 4217939.77 15 5 7591518.47 7596498.75 7600645.46 7603957.17 15 7 11770077.05 11780236.43 11775541.08 11782141.51 20 3 2448689.50 2462337.45 2475390.84 2614576.61 20 5 5964606.93 5638808.22 5658492.99 5676115.37 20 7 8620303.58 8639383.51 8656293.84 8671485.14 25 3 1086566.93 1133431.06 1179989.42 1224327.94 25 5 4267896.78 6606733.17 5333392.58 4439826.92 25 7 8260241.17 8310382.27 8358821.16 8403406.83Table 3
Results ofΨ under all weight combinations.
α N P Ψ ( w 1 , w 2 ) ( 0,1 ) ( 0.2,0.8 ) ( 0.4,0.6 ) ( 0.6,0.4 ) ( 0.8,0.2 ) ( 1,0 ) 0.2 5 2 224589.93 224589.93 224589.93 224589.93 224589.93 0 10 3 1027541.72 1027542.16 1027541.72 1027542.06 1027542.06 0 10 5 1027540.54 1027541.86 1027541.86 1027541.86 1027541.86 0 15 3 2205498.61 2204915.80 2204727.56 2202259.72 2195477.81 0 15 5 2273547.74 2273392.94 2272551.04 2272551.04 2261676.91 0 15 7 2311447.10 2311137.58 2311095.56 2306936.05 2294650.48 0 20 3 3588267.13 3938882.22 3587185.19 3584464.32 3925765.50 0 20 5 3939207.08 3938719.34 4055035.41 4051068.03 4042096.26 0 20 7 3731104.38 3730388.83 3729155.46 3724789.92 3715758.04 0 25 3 5431526.32 5431334.97 5430280.84 5428905.69 5413902.00 0 25 5 5804793.44 5804580.58 5802449.29 5800139.55 5788545.96 0 25 7 5263624.74 5502366.53 5262415.20 5256008.24 5469477.79 0  0.4 5 2 224589.34 224589.34 224589.34 224589.34 224589.34 0 10 3 1027536.99 1027536.99 1027536.99 1027537.68 1026879.10 0 10 5 1027537.28 1027537.28 1027537.28 1027537.28 1027537.28 0 15 3 2205488.04 2204717.21 2204669.98 2201115.95 2195467.39 0 15 5 2273534.46 2272920.82 2272537.49 2272540.05 2261663.43 0 15 7 2216022.94 2215966.32 2311081.02 2306921.27 2294635.80 0 20 3 3699820.06 3699182.19 3698340.30 3695085.61 3774691.16 0 20 5 4059318.54 4058552.83 4055014.52 4051047.01 4042073.30 0 20 7 3731044.95 3730490.30 3729225.35 3724770.15 3715738.48 0 25 3 5431492.12 5431330.48 5430256.40 5428029.34 5413877.78 0 25 5 5804990.52 5804548.54 5802417.79 5800108.08 5788548.96 0 25 7 5503524.93 5502643.11 5500729.01 5492950.94 5469453.84 0  0.6 5 2 224554.95 224554.95 224554.95 224554.95 224554.95 0 10 3 1024071.51 1026667.22 1020713.87 1018697.17 1017440.43 0 10 5 1026622.16 1026622.16 1025421.48 1023320.27 1023320.27 0 15 3 2163344.81 2163058.34 2162344.63 2160215.98 2152309.47 0 15 5 2250155.56 2249725.99 2248005.32 2247607.11 2239913.46 0 15 7 2302464.96 2302116.69 2298189.51 2302116.69 2285669.98 0 20 3 3645408.58 3513526.93 3512307.10 3510255.47 3629509.85 0 20 5 3925221.98 3924681.23 4011560.44 4007231.48 3998353.17 0 20 7 3902333.95 3652923.24 3649362.17 3645532.56 3638103.70 0 25 3 5284948.07 5284697.67 5284412.47 5280823.21 5270077.06 0 25 5 5677031.89 5676600.82 5353469.83 5549252.16 5661697.15 0 25 7 5383855.72 5383293.86 5380626.84 5373180.31 5351349.29 0Table 4
Worst-case value ratios.
α N P ( w 1 , w 2 ) (0,1) (0.2,0.8) (0.4,0.6) (0.6,0.4) (0.8,0.2) 0.2 5 2 0.04 0.04 0.04 0.04 0.04 10 3 0.21 0.21 0.21 0.21 0.21 10 5 0.12 0.12 0.12 0.12 0.12 15 3 0.53 0.53 0.53 0.53 0.53 15 5 0.30 0.30 0.30 0.30 0.30 15 7 0.20 0.20 0.20 0.20 0.20 20 3 1.52 1.69 1.52 1.52 1.70 20 5 0.68 0.68 0.73 0.73 0.73 20 7 0.44 0.44 0.44 0.44 0.44 25 3 6.08 6.08 6.08 6.09 6.09 25 5 1.42 1.42 1.42 1.42 1.42 25 7 0.63 0.68 0.63 0.63 0.68  0.4 5 2 0.04 0.04 0.04 0.04 0.04 10 3 0.21 0.21 0.21 0.21 0.21 10 5 0.12 0.12 0.12 0.12 0.12 15 3 0.53 0.53 0.53 0.53 0.53 15 5 0.30 0.30 0.30 0.30 0.30 15 7 0.19 0.19 0.20 0.20 0.20 20 3 1.49 1.49 1.49 1.49 1.56 20 5 0.73 0.73 0.73 0.73 0.73 20 7 0.44 0.44 0.44 0.44 0.44 25 3 6.08 6.08 6.08 6.09 6.09 25 5 1.42 1.42 1.42 1.42 1.42 25 7 0.68 0.68 0.68 0.68 0.68  0.6 5 2 0.04 0.04 0.04 0.04 0.04 10 3 0.21 0.21 0.21 0.21 0.21 10 5 0.12 0.12 0.12 0.12 0.12 15 3 0.51 0.51 0.51 0.51 0.51 15 5 0.30 0.30 0.30 0.30 0.29 15 7 0.20 0.20 0.20 0.20 0.19 20 3 1.43 1.43 1.43 1.42 1.39 20 5 0.66 0.66 0.71 0.71 0.70 20 7 0.41 0.42 0.42 0.42 0.42 25 3 5.08 4.86 4.66 4.48 4.30 25 5 1.35 1.33 0.81 1.04 1.28 25 7 0.66 0.65 0.65 0.64 0.64Figure 2
Profits comparison under different parameter values.We initially observe the profits under weight combinations(0,1) and (1,0). The results obtained from solving the simplified model (11)-(13) and (2)-(10) are summarized in Table 1. The first three columns report the values of discount factor α, the number of the nodes N and the number of the hubs P. The columns, under the heading of (ω1,ω2), give the profits under the weight combinations (0,1) and (1,0). The last column shows the deviation between these two values under (0,1) and (1,0). This deviation has been computed as “profit under (0,1) - profit under (1,0)”.Observe from Table1 that the profit differs a lot depending on different node number N existed in the network. The highest profit is achieved at N=15 and the lowest profit is obtained at N=25. The values in the column labeled ‘Dev’ indicate that the profit under (0,1) is higher than the one under (1,0) for a given node number N in almost all cases. As can be seen, the deviation between profit (0,1) and (1,0) is insensitive to an increase in N. We next observe the effect of hub number P on the results presented in Table 1. The highest profit is produced when P=7, whereas the lowest profit is obtained at P=3. When P increases, the deviation also increases in the majority of cases. For a given N, the profit increases as P increases in all cases. Besides, for a given P, an increase in node number N yields to a decrease in profit. The largest deviation always can be obtained at N=20. We also test all instances with three different levels of discount. When the level of discount is increased from α=0.2 to α=0.6, higher profit can be resulted in for most cases. In particular, the profit stands out significantly when α=0.6, whereas only a few instances don’t justify this point. The profit under (0,1) is higher than the one under (1,0) along with an increasing discount.Table2 provides the solutions by solving our model optimally under mixed weight vectors. The discount factor, node number, and hub number are shown in the first three columns labeled as α, N and P. The next four columns represent the profits under different weight vectors, (0.2,0.8), (0.4,0.6), (0.6,0.4) and (0.8,0.2). To demonstrate the results with different levels of discount, Table 2 is split horizontally into three parts for α=0.2, α=0.4 and α=0.6.Regarding the factor of node numberN, the highest profit can be provided within the instances with N=15 and the lowest profit always can be reported at N=25. We observe that the profit is not proportional to the network size. When the network becomes larger over a perfect structure (e.g. it’s N=15 in our paper), the profit can’t be higher. In other words, not all the demand can be satisfied and some of the O&D pairs are unprofitable in a larger network with over 15 nodes. We also analyze the impact of hub number P on profits. The minimum profit is at P=3 and the maximum profit is at P=7. This is reasonable because the effect of the hub can not only largely reduce the links but also can bring economic benefits as a transportation and business center. Hence, more hubs can attract more business opportunities. Besides, the profit tends to be lower when the proportion of hub P and node N is less than 20%. The proportion of over 35% can result in higher profit. As can be seen, the profit changes significantly with discount factor α. It is clear that profits increase along with increasing α, for a given N, P and (ω1, ω1). For a given N, P and α, the profit reduces along with increasing ω1 and decreasing ω2 in almost all cases. For example, the maximum profit is at (0.2, 0.8) and the minimum is at (0.8, 0.2).Figure2 provides an insight into the change in profits under different parameter values. Each subgraph presented in Figure 2 refers to one specific network. For each network, we depict different profits under different discount factor α. The x-axis lists the values of weight vectors (ω1, ω2) and the y-axis shows the profit. To justify the priority of the proposed model, we analyze the computational results compared to [3]. The solutions in [3] correspond to the profits under weights (1, 0) in our experiments. As mentioned before, the profits under weight vector (0, 1) result in the best profit in most cases. In other words, the values in (0, 1) provide an upper bound for almost all the cases. The lowest profits are achieved when the weight combination is (1, 0) for each network size in the majority of cases. Besides, the profits under all weights (0.2, 0.8), (0.4, 0.6), (0.6, 0.4) and (0.8, 0.2) are higher than the ones under (1, 0) in most cases. We believe that these results provide a good indication of the added benefit of a combined average-case and worst-case analysis for the integrated problem. We also conclude from Figure 2 that when the discount factor α is higher, the decision maker can significantly obtain more profit. Hence, the discount factor is an important indicator in designing and operating a hub network.The value ofΨ is listed in Table 3. In addition to the columns in Table 2, the columns labeled ‘Ψ(ω1,ω2)’ report the values of Ψ under six weight vectors. As noted in the problem definition, Ψ indicates the worst-case value over all the scenarios. We would like to note that the value of Ψ in column (1, 0) is 0 in any case because the experiment under (1, 0) aims to maximize the average profit. In other words, Ψ is absent from objective function (11). For a given N, P and α, Ψ reduces along with increasing ω1 and decreasing ω2. The highest worst-case values are obtained with the weight vector (0, 1) in the majority of the cases, whereas the lowest worst-case values are achieved with the weight vector (0.8, 0.2) in most cases. Similar conclusions from Table 3 can also be drawn as from Tables 1 and 2.We want to explore the effect of the worst-case value on the profit in Table4. The ratio is computed as “Worst-case value Ψ / Profit”. It is clear that the worst-case value is usually lower than the profit in the majority of cases. However, the ratio over 1 indicates that the worst-case value is higher than the profit as increasing network size for a given α. In addition, the value of the ratio is insensitive to α, for the given N, P and (ω1, ω2). Under different weight combinations, the ratio is usually the same for the same network size.


## 5.1. Test Bed

We use the data set from [3]. The values of (N,P) are set at (5,2), (10,3), (10,5), (15,3), (15,5), (15,7), (20,3), (20,5), (20,7), (25,3), (25,5) and (25,7). The cost of installing hub Fj or a central hub F′ is drawn from U(1200000,2400000). Two fare classes (K=2) provide a business class k=1 and an economic class k=2. For Type1 link, the transportation cost C11 per unit distance per flight on the class k=1 is drawn from U(7,14) and the transportation cost C12 per unit distance per flight for k=2 is γC11, where γ~U(0.5,1). We consider C21 = αC11 and C22=αC12, where α∈{0.2,0.4,0.6}. Since [3] does not provide any information regarding the distance, we set fij=1 and fj0=1. The capacity Noij on Type1 link is drawn from a discrete uniform distribution DU(1,3). For Type2 link, the capacity Noj0 is drawn from DU(3,6). The capacity Q1 of the aircraft used on Type1 link and Q2 on Type2 link are 100 and 200, respectively. The ticket price at k=2 is drawn from a continuous distribution U(600,3600). And the price at k=1 is 1.5 higher than the one at k=2. We set M=100000.We setS=10 and the probability of all the scenarios is the same, namely 1/S. The demand for each fare class is drawn from the interval between low demand and high demand [3.75,6.25]. 80% of the demand come from the economic class and 20% are from the business class. We also test six weight vectors (ω1,ω2), such that (0,1), (0.2,0.8), (0.4,0.6), (0.6,0.4), (0.8,0.2) and (1,0). Note that the weight combination (1,0) represents that the objective of our problem is to maximize the average profit over all scenarios. The weight (0,1) stands for maximizing the worst-case profit. The mixed weight combinations (0.2,0.8), (0.4,0.6), (0.6,0.4) and (0.8,0.2) mean maximizing a weighted sum of average and worst case profits over all scenarios. In addition, the probability of crossover is 0.8 and the probability of mutation is 0.15. The maximum number of generation is 50 and the population size is 20. We extend the number of scenarios to 10. When the number of scenarios is three times more than the number used in [3], our problem becomes more challenging if the population size is still set 50 as in [3]. Therefore, we reduce the population size to 20 so that this process can continue in limited iterative.


## 5.2. Results

This hybrid algorithm was implemented in Matlab R2017b using Yalmip R20171121 and IBM ILOG Cplex Optimization Studio 12.8.0. All runs were done on a MacBook Pro with an Intel Core i7 CPU 3GHz processor at 8GB of RAM under macOS High Sierra 10.13.3 operating system. To demonstrate good performance of our mathematical formulation, we conducted 216 computational experiments considering 6 weight vectors with varying 12 network sizes as well as 3 discount factors.The organization of this section is as follows: First, we report computational results under different parameter valuesN and P, weight vector (ω1,ω2) and discount factor α in Tables 1 and 2. Especially, the results under (0,1) and (1,0) are shown in Table 1 and the results under the mixed weight combinations are presented in Table 2. Second, Figure 2 is used for comparing the performance of our proposed model and the model in [3]. The impact of α on the profits can also be illustrated in Figure 2. Finally, we present the results of the worst-case values in Table 3 and investigate the correlation between the worst-case value and the profit in Table 4.Table 1
Profits under(0,1) and (1,0).
α N P (ω1, ω2) D e v ( 0,1 ) ( 1,0 ) 0.2 5 2 5442266.67 5423379.87 18886.80 10 3 4918937.71 4887976.87 30960.84 10 5 8293400.06 8262616.21 30783.85 15 3 4160728.26 4137520.58 23207.68 15 5 7562556.80 7534413.37 28143.43 15 7 11755282.60 11720169.74 35112.86 20 3 2360179.15 2300020.24 60158.91 20 5 5759796.83 5512755.65 247041.18 20 7 8522527.33 8486613.75 35913.58 25 3 892883.30 879578.93 13304.37 25 5 4080747.68 4063431.36 17316.32 25 7 8384020.92 8053287.16 330733.76  0.4 5 2 5442267.26 5423380.53 18886.73 10 3 4918942.44 4890648.04 28294.40 10 5 8293404.64 8262621.05 30783.59 15 3 4160738.83 4137529.01 23209.82 15 5 7562570.08 7534424.29 28145.79 15 7 11850706.76 11720184.41 130522.35 20 3 2486257.40 2400330.06 85927.34 20 5 5550614.23 5512778.82 37835.41 20 7 8522586.77 8486633.64 35953.13 25 3 892917.49 879603.28 13314.21 25 5 4080550.59 4063463.12 17087.47 25 7 8089252.79 8053316.86 35935.93  0.6 5 2 5442267.86 5442301.65 -33.79 10 3 4922407.92 4904121.97 18285.95 10 5 8294319.76 8275448.45 18871.31 15 3 4202882.06 4217080.62 -14198.56 15 5 7585948.98 7603389.82 -17440.84 15 7 11764264.73 11613095.26 151169.47 20 3 2540668.89 2489654.33 51014.56 20 5 5946942.46 6018106.15 -71163.69 20 7 9494836.41 8683483.27 811353.14 25 3 1039461.55 1263250.70 -223789.15 25 5 4208509.22 4489668.85 -281159.63 25 7 8208922.00 8439144.76 -230222.76Table 2
Profits under mixed weight combinations.
α N P (ω1, ω2) (0.2,0.8) (0.4,0.6) (0.6,0.4) (0.8,0.2) 0.2 5 2 5438489.31 5434711.95 5430934.59 5427157.23 10 3 4913467.23 4907997.64 4900371.10 4894182.34 10 5 8287303.68 8281207.29 8275110.91 8269014.53 15 3 4158103.96 4154727.13 4150791.16 4145561.69 15 5 7558990.36 7554668.13 7550225.45 7544160.12 15 7 11750609.00 11745627.15 11739865.46 11731346.52 20 3 2329636.54 2358141.43 2356525.42 2311386.40 20 5 5756168.69 5541820.03 5534669.13 5525588.27 20 7 8518495.08 8512989.30 8506425.30 8498186.76 25 3 892821.19 892421.61 891341.44 888308.81 25 5 4080580.66 4080098.79 4077652.35 4073697.67 25 7 8087887.20 8383805.11 8382705.01 8070721.25  0.4 5 2 5438489.92 5434712.57 5430935.22 5427157.88 10 3 4913472.45 4908002.46 4900375.65 4897055.01 10 5 8287308.31 8281211.98 8275115.64 8269019.31 15 3 4158123.59 4154780.97 4150767.12 4145572.12 15 5 7559010.28 7554681.63 7550236.36 7544173.58 15 7 11848845.27 11745641.74 11739880.18 11731361.18 20 3 2485358.09 2483758.63 2481010.23 2412575.20 20 5 5547325.79 5541841.01 5534690.21 5525611.37 20 7 8518582.62 8513134.96 8506445.13 8498206.57 25 3 892825.69 892446.01 891519.07 888333.16 25 5 4080612.63 4080130.36 4077683.94 4073694.68 25 7 8087920.51 8085342.31 8080574.24 8070745.42  0.6 5 2 5438605.23 5434908.81 5431212.39 5427515.97 10 3 4917136.78 4920304.97 4917254.78 4913525.68 10 5 8291540.99 8288510.64 8284498.40 8280123.99 15 3 4207659.77 4211795.89 4215598.76 4217939.77 15 5 7591518.47 7596498.75 7600645.46 7603957.17 15 7 11770077.05 11780236.43 11775541.08 11782141.51 20 3 2448689.50 2462337.45 2475390.84 2614576.61 20 5 5964606.93 5638808.22 5658492.99 5676115.37 20 7 8620303.58 8639383.51 8656293.84 8671485.14 25 3 1086566.93 1133431.06 1179989.42 1224327.94 25 5 4267896.78 6606733.17 5333392.58 4439826.92 25 7 8260241.17 8310382.27 8358821.16 8403406.83Table 3
Results ofΨ under all weight combinations.
α N P Ψ ( w 1 , w 2 ) ( 0,1 ) ( 0.2,0.8 ) ( 0.4,0.6 ) ( 0.6,0.4 ) ( 0.8,0.2 ) ( 1,0 ) 0.2 5 2 224589.93 224589.93 224589.93 224589.93 224589.93 0 10 3 1027541.72 1027542.16 1027541.72 1027542.06 1027542.06 0 10 5 1027540.54 1027541.86 1027541.86 1027541.86 1027541.86 0 15 3 2205498.61 2204915.80 2204727.56 2202259.72 2195477.81 0 15 5 2273547.74 2273392.94 2272551.04 2272551.04 2261676.91 0 15 7 2311447.10 2311137.58 2311095.56 2306936.05 2294650.48 0 20 3 3588267.13 3938882.22 3587185.19 3584464.32 3925765.50 0 20 5 3939207.08 3938719.34 4055035.41 4051068.03 4042096.26 0 20 7 3731104.38 3730388.83 3729155.46 3724789.92 3715758.04 0 25 3 5431526.32 5431334.97 5430280.84 5428905.69 5413902.00 0 25 5 5804793.44 5804580.58 5802449.29 5800139.55 5788545.96 0 25 7 5263624.74 5502366.53 5262415.20 5256008.24 5469477.79 0  0.4 5 2 224589.34 224589.34 224589.34 224589.34 224589.34 0 10 3 1027536.99 1027536.99 1027536.99 1027537.68 1026879.10 0 10 5 1027537.28 1027537.28 1027537.28 1027537.28 1027537.28 0 15 3 2205488.04 2204717.21 2204669.98 2201115.95 2195467.39 0 15 5 2273534.46 2272920.82 2272537.49 2272540.05 2261663.43 0 15 7 2216022.94 2215966.32 2311081.02 2306921.27 2294635.80 0 20 3 3699820.06 3699182.19 3698340.30 3695085.61 3774691.16 0 20 5 4059318.54 4058552.83 4055014.52 4051047.01 4042073.30 0 20 7 3731044.95 3730490.30 3729225.35 3724770.15 3715738.48 0 25 3 5431492.12 5431330.48 5430256.40 5428029.34 5413877.78 0 25 5 5804990.52 5804548.54 5802417.79 5800108.08 5788548.96 0 25 7 5503524.93 5502643.11 5500729.01 5492950.94 5469453.84 0  0.6 5 2 224554.95 224554.95 224554.95 224554.95 224554.95 0 10 3 1024071.51 1026667.22 1020713.87 1018697.17 1017440.43 0 10 5 1026622.16 1026622.16 1025421.48 1023320.27 1023320.27 0 15 3 2163344.81 2163058.34 2162344.63 2160215.98 2152309.47 0 15 5 2250155.56 2249725.99 2248005.32 2247607.11 2239913.46 0 15 7 2302464.96 2302116.69 2298189.51 2302116.69 2285669.98 0 20 3 3645408.58 3513526.93 3512307.10 3510255.47 3629509.85 0 20 5 3925221.98 3924681.23 4011560.44 4007231.48 3998353.17 0 20 7 3902333.95 3652923.24 3649362.17 3645532.56 3638103.70 0 25 3 5284948.07 5284697.67 5284412.47 5280823.21 5270077.06 0 25 5 5677031.89 5676600.82 5353469.83 5549252.16 5661697.15 0 25 7 5383855.72 5383293.86 5380626.84 5373180.31 5351349.29 0Table 4
Worst-case value ratios.
α N P ( w 1 , w 2 ) (0,1) (0.2,0.8) (0.4,0.6) (0.6,0.4) (0.8,0.2) 0.2 5 2 0.04 0.04 0.04 0.04 0.04 10 3 0.21 0.21 0.21 0.21 0.21 10 5 0.12 0.12 0.12 0.12 0.12 15 3 0.53 0.53 0.53 0.53 0.53 15 5 0.30 0.30 0.30 0.30 0.30 15 7 0.20 0.20 0.20 0.20 0.20 20 3 1.52 1.69 1.52 1.52 1.70 20 5 0.68 0.68 0.73 0.73 0.73 20 7 0.44 0.44 0.44 0.44 0.44 25 3 6.08 6.08 6.08 6.09 6.09 25 5 1.42 1.42 1.42 1.42 1.42 25 7 0.63 0.68 0.63 0.63 0.68  0.4 5 2 0.04 0.04 0.04 0.04 0.04 10 3 0.21 0.21 0.21 0.21 0.21 10 5 0.12 0.12 0.12 0.12 0.12 15 3 0.53 0.53 0.53 0.53 0.53 15 5 0.30 0.30 0.30 0.30 0.30 15 7 0.19 0.19 0.20 0.20 0.20 20 3 1.49 1.49 1.49 1.49 1.56 20 5 0.73 0.73 0.73 0.73 0.73 20 7 0.44 0.44 0.44 0.44 0.44 25 3 6.08 6.08 6.08 6.09 6.09 25 5 1.42 1.42 1.42 1.42 1.42 25 7 0.68 0.68 0.68 0.68 0.68  0.6 5 2 0.04 0.04 0.04 0.04 0.04 10 3 0.21 0.21 0.21 0.21 0.21 10 5 0.12 0.12 0.12 0.12 0.12 15 3 0.51 0.51 0.51 0.51 0.51 15 5 0.30 0.30 0.30 0.30 0.29 15 7 0.20 0.20 0.20 0.20 0.19 20 3 1.43 1.43 1.43 1.42 1.39 20 5 0.66 0.66 0.71 0.71 0.70 20 7 0.41 0.42 0.42 0.42 0.42 25 3 5.08 4.86 4.66 4.48 4.30 25 5 1.35 1.33 0.81 1.04 1.28 25 7 0.66 0.65 0.65 0.64 0.64Figure 2
Profits comparison under different parameter values.We initially observe the profits under weight combinations(0,1) and (1,0). The results obtained from solving the simplified model (11)-(13) and (2)-(10) are summarized in Table 1. The first three columns report the values of discount factor α, the number of the nodes N and the number of the hubs P. The columns, under the heading of (ω1,ω2), give the profits under the weight combinations (0,1) and (1,0). The last column shows the deviation between these two values under (0,1) and (1,0). This deviation has been computed as “profit under (0,1) - profit under (1,0)”.Observe from Table1 that the profit differs a lot depending on different node number N existed in the network. The highest profit is achieved at N=15 and the lowest profit is obtained at N=25. The values in the column labeled ‘Dev’ indicate that the profit under (0,1) is higher than the one under (1,0) for a given node number N in almost all cases. As can be seen, the deviation between profit (0,1) and (1,0) is insensitive to an increase in N. We next observe the effect of hub number P on the results presented in Table 1. The highest profit is produced when P=7, whereas the lowest profit is obtained at P=3. When P increases, the deviation also increases in the majority of cases. For a given N, the profit increases as P increases in all cases. Besides, for a given P, an increase in node number N yields to a decrease in profit. The largest deviation always can be obtained at N=20. We also test all instances with three different levels of discount. When the level of discount is increased from α=0.2 to α=0.6, higher profit can be resulted in for most cases. In particular, the profit stands out significantly when α=0.6, whereas only a few instances don’t justify this point. The profit under (0,1) is higher than the one under (1,0) along with an increasing discount.Table2 provides the solutions by solving our model optimally under mixed weight vectors. The discount factor, node number, and hub number are shown in the first three columns labeled as α, N and P. The next four columns represent the profits under different weight vectors, (0.2,0.8), (0.4,0.6), (0.6,0.4) and (0.8,0.2). To demonstrate the results with different levels of discount, Table 2 is split horizontally into three parts for α=0.2, α=0.4 and α=0.6.Regarding the factor of node numberN, the highest profit can be provided within the instances with N=15 and the lowest profit always can be reported at N=25. We observe that the profit is not proportional to the network size. When the network becomes larger over a perfect structure (e.g. it’s N=15 in our paper), the profit can’t be higher. In other words, not all the demand can be satisfied and some of the O&D pairs are unprofitable in a larger network with over 15 nodes. We also analyze the impact of hub number P on profits. The minimum profit is at P=3 and the maximum profit is at P=7. This is reasonable because the effect of the hub can not only largely reduce the links but also can bring economic benefits as a transportation and business center. Hence, more hubs can attract more business opportunities. Besides, the profit tends to be lower when the proportion of hub P and node N is less than 20%. The proportion of over 35% can result in higher profit. As can be seen, the profit changes significantly with discount factor α. It is clear that profits increase along with increasing α, for a given N, P and (ω1, ω1). For a given N, P and α, the profit reduces along with increasing ω1 and decreasing ω2 in almost all cases. For example, the maximum profit is at (0.2, 0.8) and the minimum is at (0.8, 0.2).Figure2 provides an insight into the change in profits under different parameter values. Each subgraph presented in Figure 2 refers to one specific network. For each network, we depict different profits under different discount factor α. The x-axis lists the values of weight vectors (ω1, ω2) and the y-axis shows the profit. To justify the priority of the proposed model, we analyze the computational results compared to [3]. The solutions in [3] correspond to the profits under weights (1, 0) in our experiments. As mentioned before, the profits under weight vector (0, 1) result in the best profit in most cases. In other words, the values in (0, 1) provide an upper bound for almost all the cases. The lowest profits are achieved when the weight combination is (1, 0) for each network size in the majority of cases. Besides, the profits under all weights (0.2, 0.8), (0.4, 0.6), (0.6, 0.4) and (0.8, 0.2) are higher than the ones under (1, 0) in most cases. We believe that these results provide a good indication of the added benefit of a combined average-case and worst-case analysis for the integrated problem. We also conclude from Figure 2 that when the discount factor α is higher, the decision maker can significantly obtain more profit. Hence, the discount factor is an important indicator in designing and operating a hub network.The value ofΨ is listed in Table 3. In addition to the columns in Table 2, the columns labeled ‘Ψ(ω1,ω2)’ report the values of Ψ under six weight vectors. As noted in the problem definition, Ψ indicates the worst-case value over all the scenarios. We would like to note that the value of Ψ in column (1, 0) is 0 in any case because the experiment under (1, 0) aims to maximize the average profit. In other words, Ψ is absent from objective function (11). For a given N, P and α, Ψ reduces along with increasing ω1 and decreasing ω2. The highest worst-case values are obtained with the weight vector (0, 1) in the majority of the cases, whereas the lowest worst-case values are achieved with the weight vector (0.8, 0.2) in most cases. Similar conclusions from Table 3 can also be drawn as from Tables 1 and 2.We want to explore the effect of the worst-case value on the profit in Table4. The ratio is computed as “Worst-case value Ψ / Profit”. It is clear that the worst-case value is usually lower than the profit in the majority of cases. However, the ratio over 1 indicates that the worst-case value is higher than the profit as increasing network size for a given α. In addition, the value of the ratio is insensitive to α, for the given N, P and (ω1, ω2). Under different weight combinations, the ratio is usually the same for the same network size.


## 6. Conclusions

This paper focused on the integrated problem of an uncapacitated single allocationp-hub median location problem and a revenue management problem. We optimized the decisions about hub locations, routing links and the protection levels of airline tickets for multiple fare classes in the first stage and the booking limits of tickets in the second stage. We formulated a two-stage stochastic programming framework and considered a weighted sum of average and worst case profits. The proposed model could give the flexibilities of the decisions on network configuration and tickets sales by putting the emphasis on the importance of the average and worst case values over all scenarios.In addition, a GA was applied to solve our problem. We performed 216 computational experiments, including 6 weight vectors with varying 12 network sizes as well as 3 discount factors under 10 scenarios. We analyzed the profits under different weight vectors, the performance compared to the consideration in [3] and the effect of the worst-case on profits. The results demonstrated that the proposed formulation outperformed the model in [3]. The largest profits were obtained at weight combination (0, 1), whereas the lowest profits were achieved at the weight combination (1, 0). The profit decreased along with increasing ω1 and decreasing ω2. Moreover, the discount factor was also an important indicator in designing and operating a hub network.Future studies could be enriched to considering capacitated hubs in this integrated problem. For shortening the computation time, more efficient meta-heuristic algorithms could be developed. Using the robust controller to deal with the uncertainty could be a better solution, e.g. [53].



---

*Source: 8651728-2019-03-12.xml*