A dynamic virtual air hub location problem with balancing requirements via robust optimization: Mathematical modeling and solution methods

Nomenclature

1 Introduction

Hub location problems (HLPs) relate to the design of transportation networks with multiple components/nodes transferring cargo, passengers, and information between each pair. One usage of HLP is in air transportation system. There are many airports in the system, and the paths between origins and destination pairs should be determined so that passengers get to their destinations on time with lower costs.

Regarding airline transportation network, Yang [1] developed a stochastic model for the air freightage hub location problem so that flight paths altered according to requirements of seasonal changes. Considering the problem of multi-allocation hub location, Hamacher et al. [2] introduced a model to solve the polyhedral characteristics of the problem. Marin et al. [3] stated a model for un-capacitated HLP so that there was the possibility of one or two pauses in hubs. De Camargo et al. [4] provided the decomposition algorithm of Benders to efficiently solve large size problems. Ebery et al. [5] suggested an integer linear model and a heuristic perspective, branch, and bound algorithm to solve it. Marin [6] used a new integer linear programming to solve average size problems. In Contreras et al. [7] model, the activeun-capacitated hub location problem, all demands were completely routed via the network each time, and hub facilities could be opened or closed in the periods. Chou [8] investigated the hub ports in the networks of marine transportation through a fuzzy multi-criteria decision making model. The study applied fuzzy concept because of modal conditions for the existence and choosing of efficient hubs in the networks of marine transportation. Correia et al. [9] presented an extension of the classical single-allocation hub location problem, in which dimensioning decisions and balancing requirements were introduced. Moreover, they proposed two mathematical programming formulations for this problem. A dynamic virtual hub location problem in fuzzy setting with integer linear programming was presented by Taghipourian et al. [10].

However, in previous works, design factors of the problem are of deterministic nature. Nonetheless, the dynamic and complicate nature of manufacturing operations requires a high uncertainty in designing hub networks. This significantly affects the general efficiency of the system. Therefore, the applying uncertainty in determining the parameters seems inevitable. Generally, three approaches are often used to solve non-deterministic nature problems: (a) stochastic, (b) fuzzy, and (c) robust. Robust optimization has emerged as an approach to solve uncertainty problems. The main benefits are: (i) This model is computationally manageable and independent like uncertain characteristics; (ii) There is no need to know the uncertain parameters’ probability distributions; however, historical data and experts’ experiences can be used to gain the range of uncertainty in some cases [11]; (iii) This method calculates the possible solutions for all scenarios of uncertain parameters optimizing objective functions in a controlled and balanced condition [12].

Hence, this paper proposes a robust dynamic virtual hub location problem. In fact, a dynamic perspective is considered so that the decisions on locating the virtual hubs and determining path among any original and destination nodes are made in the entire planning horizon. To develop the presented mixed integer linear programming model and to handle the uncertain data, transportation costs, demand, fixed opening and closing costs, and maintenance costs are ensured to vary in uncertain conditions. Then, the tractable robust counterpart of the presented deterministic hub location model is applied to find out the robust solutions. Moreover, a meta-heuristic algorithm based on two simulated annealing and imperialist competitive algorithms are utilized in order to solve the proposed problem.

The rest of the paper is organized as follows. The problem’s assumptions and mathematical formulation are described in Section 2. The solution approach is given in Section 3. The proposed meta-heuristic algorithm is given in Section 4. Computational experiments are provided in Section 5. Section 6 discusses about the computational experiments. Finally, the paper is concluded in Section 7.

2 Mathematical formulation

When an original hub encounters with an unexpected status like inclement weather, congestion of passenger or commodity, etc., a virtual hub location problem is considered; thus, the original hubs miss service capacities. Regarding the original hubs’ function in the transportation system, interruption of the hubs leads to extensive widespread interruption in the network. A virtual hub is a pre-specified alternative spoke component to work as an original hub in crisis so that the original hub’s disruption of service is removed. Here, a mixed integer linear programming model of a dynamic virtual hub location problem with balancing requisites is proposed. Let G be a graph G = (N,  A), with nodes N and arcs A. In a virtual hub network with maximum two possible stops in the source or virtual hubs, seven main possibilities are considered for each path from origin to destination nodes:

node – node (direct path)

Distance costs between origin and destination nodes are calculated as follows: c ikhj = d ik + δ d kh + d lj c ikvj = d ik + ɛ d kv + d vj c ivkj = d iv + ɛ d vk + d kj c ivyj = d iv + γ d vy + d yj c ij = d ij

Model: Min z = ∑ i ∈ N ∑ j ≠ i ∈ N ∑ t ∈ T D it s ijt c ij + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ k ∈ H ∑ h ∈ H ∑ l ∈ L ∑ r ∈ L D it s i ( k , l ) ( h , r ) jt c ikhj + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ k ∈ H ∑ v ∈ VH ∑ l ∈ L ∑ g ∈ L D it s i ( k , l ) ( v , g ) jt c ikvj + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ k ∈ H ∑ v ∈ VH ∑ l ∈ L ∑ g ∈ L D it s i ( v , g ) ( k , l ) jt c ivkj + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ v ∈ VH ∑ y ∈ VH ∑ l ∈ L ∑ g ∈ L D it s i ( v , g ) ( y , p ) jt c ivyj + ∑ t ∈ T ∑ v ∈ VH ∑ g ∈ L ZH vtg z vtg + ∑ t ∈ T ∑ v ∈ VH ∑ g ∈ L ZHO vtg zo vtg + ∑ t ∈ T ∑ v ∈ VH ∑ g ∈ L ZHC vtg zc vtg S . t . :(1) x ikl ≤ z kl ∀ i ∈ N , k ∈ H , l ∈ L(2) ∑ i ∈ N x ikl ≥ z kl ∀ k ∈ H , l ∈ L(3) ∑ l ∈ L ∑ k ∈ H x ikl ≤ 1 ∀ i ∈ N(4) x ivgt ≤ z vtg ∀ i ∈ N , v ∈ VH , t ∈ T , g ∈ L(5) ∑ i ∈ N x ivgt ≥ z vtg ∀ v ∈ VH , t ∈ T , g ∈ L(6) ∑ g ∈ L ∑ v ∈ VH x ivgt ≤ 1 ∀ i ∈ N , t ∈ T(7) s ijt + s i ( k , l ) ( h , r ) jt + s i ( k , l ) ( v , g ) jt + s i ( v , g ) ( k , l ) jt + s i ( v , g ) ( y , p ) jt = 1 ∀ i , j ∈ N ; k , h ∈ H ; v , y ∈ VH ; l , r , g , p ∈ L ; t ∈ T(8) s i ( k , l ) ( h , r ) jt ≤ x ikl ∀ i , j ∈ N ; k , h ∈ H ; l , r ∈ L ; t ∈ T(9) s i ( k , l ) ( h , r ) jt ≤ x jhr ∀ i , j ∈ N ; k , h ∈ H ; l , r ∈ L ; t ∈ T(10) s i ( k , l ) ( v , g ) jt ≤ x ikl ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T(11) s i ( k , l ) ( v , g ) jt ≤ x jvgt ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T(12) s i ( v , g ) ( k , l ) jt ≤ x ivgt ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T(13) s i ( v , g ) ( k , l ) jt ≤ x jkl ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T(14) s i ( v , g ) ( y , p ) jt ≤ x ivgt ∀ i , j ∈ N ; v , y ∈ VH ; g , p ∈ L ; t ∈ T(15) s i ( v , g ) ( y , p ) jt ≤ x jvpt ∀ i , j ∈ N ; v , y ∈ VH ; g , p ∈ L ; t ∈ T(16) ∑ j ≠ i ∈ N s ijt ≤ w ∀ i ∈ N , t ∈ T(17) | z vtg - z v , t - 1 , g | = sw vtg ∀ v ∈ VH ; t ∈ T ; g ∈ L(18) ∑ t ∈ T sw vtg ≤ 1 ∀ v ∈ VH ; g ∈ L(19) B ≤ ∑ i ∈ N ∑ g ∈ L x ivgt + M ( 1 - ∑ g ∈ L zo vtg ) ∀ v ∈ VH ; t ∈ T(20) B ′ ≥ ∑ i ∈ N ∑ g ∈ L x ivgt - M ( 1 - ∑ g ∈ L zo vtg ) ∀ v ∈ VH ; t ∈ T(21) Q ≤ ∑ i ∈ N ∑ l ∈ L x ikl + M ( 1 - ∑ l ∈ L zo vtg ) ∀ v ∈ VH(22) Q ′ ≥ ∑ i ∈ N ∑ l ∈ L x ikl - M ( 1 - ∑ l ∈ L zo kl ) ∀ k ∈ H(23) ( 1 - zint vg ) sw vtg = zo vtg ∀ v ∈ VH ; g ∈ L ; t = 1(24) ( 1 - z v , t - 1 , g ) sw vtg = zo vtg ∀ v ∈ VH ; g ∈ L ; t ≥ 2(25) zint vg sw vtg = zc vtg ∀ v ∈ VH ; g ∈ L ; t = 1(26) z v , t - 1 , g sw vtg = zc vtg ∀ v ∈ VH ; g ∈ L ; t ≥ 2(27) B ′ - B ≤ φ(28) Q ′ - Q ≤ φ ′(29) x ikl , x ivgt , zint vg , z vtg , z kl , zo kl , zo vtg , zc vtg , sw vtg , s i ( k , l ) ( h , r ) jt , s i ( k , l ) ( v , g ) jt , s i ( v , g ) ( y , p ) jt , s ijt ∈ { 0 , 1 } ∀ i , j ∈ N ; k , h ∈ H ; v , y ∈ VH ; l , r , g , p ∈ L ; t ∈ T , B ′ , B , Q ′ , Q ≥ 0 andinteger(30)

Objective function (1) expresses transportation prices between origin and destination nodes and shows opening, maintenance, and virtual hubs’ closing costs. Constraints (2) – (7) ensure that the model relates to one allocation problem. Constraints (2) ensure that if a hub is open, a demand node may not be given to the hub. Constraints (3) claim that if node k is a hub with capacity l, then at least one node should be given to it. Constraints (4) show that a demand node of the network may be allocated to just one hub and its capacity. Constraints (5) ensure that a demand node may not be allocated to a virtual hub unless it is assumed open. Constraints (6) assert that if node v is a virtual hub with capacity g, then a node has to be assigned for it. Constraints (7) contend that a demand node in the system may be allocated to only one virtual hub and its capacity. Constraints (8) show that one route and the capacity between every pair of origin and destination nodes can be chosen in all periods. Constraints (9) and (10) ensure that the path between origin node i and destination node j is transported through the primary hubs at nodes k with capacity l and h with capacity r in period t if node i is given to original hub at node k with capacity l, and node j is assigned to original hub at node h with capacity r in the t-th period. Constraints (11)– (16) are similar to (9) and (10) for all feasible paths between any source and destination nodes in the network which are transshipped through source or virtual hubs. Constraints (17) guarantee that the number of direct paths between any origin and destination nodes does not overpass a distinct value. Constraints (18) and (19) ensure that maximum one switch (demand node to virtual hub or vice versa) is feasible for the virtual hubs in the horizon periods. Constraints (20), (21) and (28) make an equilibrium in nodes’ allocation to the hubs where the variety between lower and upper count of allocations has to be less than a predetermined amount. Constraints (22), (23) and (29) balance the assignment of nodes to the virtual hubs where the variation between lower and higher number of allocations should be less than a distinct value. Constraints (24)–(27) denote the opening and closing virtual hubs’ condition in any period regarding former period configuration and switching allowance. Constraints (30) are the restrictions on the decision variables.

For the robust optimization model application, the transportation costs, demand, fixed opening and closing costs, and maintenance costs are all accounted as uncertain variables. Here, this study gives an explanation of RO principles. Pay attention to the following linear program (LP) [13–15]:

min cx s . t . Ax ≥ b(31)

Where x ∈ R n is the vector of decision variables, b ∈ R m is the right-hand parameter vector, c ∈ R n is the vector of objective function factors, and A ∈ R m × n, with element a _ij , is the constraint coefficient matrix.

In a common equation like (LP), c, A, and b are deterministic according to which the problem is solved, and an optimal solution is gained. Some data variables are taken as uncertain in the RO model; however, they lie in a set that shows restrictions on uncertainty. Subsequently the foregoing uncertainty set describes the limits on uncertainty in which a solution is going to be immunized against it. It means that the solution x relates to any uncertainty in the set [16–18]. In the RO approach, linear programming (LP) is changed into a robust counterpart by being replaced with every constraint that has uncertain factors with a constraint that represents the introduction of the uncertainty set. In the presented model, each uncertain parameter varies in a definite closed-bounded box [13–15, 19].

The robust problem— box uncertainty: In order to simplify the expressions representing the demand and distance costs, in this sub-section, henceforth, this study employs the notations A itj , B ikht , C ikvjt , D ivkjt and F ivyjt to represent the multiply (D _it c _ij ) , (D _it c _ikhj ) , (D _it c _ikvj ) , (D _it c _ivkj ) and (D _it c _ivyj ). According to the above description, the robust counterpart of the proposed model with uncertain parameters given by box sets is equivalent to the following: min W S . t . : ∑ i ∈ N ∑ j ≠ i ∈ N ∑ t ∈ T ( A itj ¯ s ijt + η itj A ) + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ k ∈ H ∑ h ∈ H ∑ l ∈ L ∑ r ∈ L ( B ikht ¯ s i ( k , l ) ( h , r ) jt + η ikht B ) + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ k ∈ H ∑ v ∈ VH ∑ l ∈ L ∑ g ∈ L ( C ikvjt ¯ s i ( k , l ) ( v , g ) jt + η ikvjt C ) + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ k ∈ H ∑ v ∈ VH ∑ l ∈ L ∑ g ∈ L ( D ivkjt ¯ s i ( v , g ) ( k , l ) jt + η ivkjt D ) + ∑ t ∈ T ∑ i ∈ N ∑ j ≠ i ∈ N ∑ v ∈ VH ∑ y ∈ VH ∑ l ∈ L ∑ g ∈ L ( F ivyjt ¯ s i ( v , g ) ( y , p ) jt + η ivyjt F ) + ∑ t ∈ T ∑ v ∈ VH ∑ g ∈ L ( ZH vtg ¯ z vtg + η vtg ZH ) + ∑ t ∈ T ∑ v ∈ VH ∑ g ∈ L ( ZHO vtg ¯ zo vtg + η vtg ZHO ) + ∑ t ∈ T ∑ v ∈ VH ∑ g ∈ L ( ZHC vtg ¯ zc vtg + η vtg ZHC ) ≤ W ρ A G itj A s ijt ≤ η itj A ∀ i , j ∈ N , t ∈ T ρ A G itj A s ijt ≥ - η itj A ∀ i , j ∈ N , t ∈ T ρ B G ikht B s i ( k , l ) ( h , r ) jt ≤ η ikht B ∀ i , j ∈ N , t ∈ T , l , r ∈ L , k , h ∈ H ρ B G ikht B s i ( k , l ) ( h , r ) jt ≥ - η ikht B ∀ i , j ∈ N , t ∈ T , l , r ∈ L , k , h ∈ H ρ C G ikvjt C s i ( k , l ) ( v , g ) jt ≤ η ikvjt C ∀ i , j ∈ N , t ∈ T , k ∈ H , v ∈ VH , l , g ∈ L ρ C G ikvjt C s i ( k , l ) ( v , g ) jt ≥ - η ikvjt C ∀ i , j ∈ N , t ∈ T , k ∈ H , v ∈ VH , l , g ∈ L ρ D G ivkjt D s i ( v , g ) ( k , l ) jt ≤ η ivkjt D ∀ i , j ∈ N , t ∈ T , k ∈ H , v ∈ VH , l , g ∈ L ρ D G ivkjt D s i ( v , g ) ( k , l ) jt ≥ - η ivkjt D ∀ i , j ∈ N , t ∈ T , k ∈ H , v ∈ VH , l , g ∈ L ρ F G ivyjt F s i ( v , g ) ( y , p ) jt ≤ η ivyjt F ∀ i , j ∈ N , t ∈ T , v , y ∈ VH ; g , p ∈ L ρ F G ivyjt F s i ( v , g ) ( y , p ) jt ≥ - η ivyjt F ∀ i , j ∈ N , t ∈ T , v , y ∈ VH ; g , p ∈ L ρ ZH G vtg ZH z vtg ≤ η vtg ZH t ∈ T , v ∈ VH ; g ∈ L ρ ZH G vtg ZH z vtg ≥ - η vtg ZH t ∈ T , v ∈ VH ; g ∈ L ρ ZHO G vtg ZHO zo vtg ≤ η vtg ZHO t ∈ T , v ∈ VH ; g ∈ L ρ ZHO G vtg ZHO zo vtg ≥ - η vtg ZHO t ∈ T , v ∈ VH ; g ∈ L ρ ZHC G vtg ZHC zc vtg ≤ η vtg ZHC t ∈ T , v ∈ VH ; g ∈ L ρ ZHC G vtg ZHC zc vtg ≥ - η vtg ZHC t ∈ T , v ∈ VH ; g ∈ L x ivgt ≤ z vtg ∀ i ∈ N , v ∈ VH , t ∈ T , g ∈ L ∑ i ∈ N x ivgt ≥ z vtg ∀ v ∈ VH , t ∈ T , g ∈ L ∑ g ∈ L ∑ v ∈ VH x ivgt ≤ 1 ∀ i ∈ N , t ∈ T x ikl ≤ z kl ∀ i ∈ N , k ∈ H , l ∈ L ∑ i ∈ N x ikl ≥ z kl ∀ k ∈ H , l ∈ L ∑ l ∈ L ∑ k ∈ H x ikl ≤ 1 ∀ i ∈ N s ijt + s i ( k , l ) ( h , r ) jt + s i ( k , l ) ( v , g ) jt + s i ( v , g ) ( k , l ) jt + s i ( v , g ) ( y , p ) jt = 1 ∀ i , j ∈ N ; k , h ∈ H ; v , y ∈ VH ; l , r , g , p ∈ L ; t ∈ T s i ( k , l ) ( h , r ) jt ≤ x ikl ∀ i , j ∈ N ; k , h ∈ H ; l , r ∈ L ; t ∈ T s i ( k , l ) ( h , r ) jt ≤ x jhl ∀ i , j ∈ N ; k , h ∈ H ; l , r ∈ L ; t ∈ T s i ( k , l ) ( v , g ) jt ≤ x ikl ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T s i ( k , l ) ( v , g ) jt ≤ x jvgt ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T s i ( v , g ) ( k , l ) jt ≤ x ivgt ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ T s i ( v , g ) ( k , l ) jt ≤ x jkl ∀ i , j ∈ N ; k ∈ H ; v ∈ VH ; l , g ∈ L ; t ∈ Ts i ( v , g ) ( y , p ) jt ≤ x ivgt ∀ i , j ∈ N ; v , y ∈ VH ; g , p ∈ L ; t ∈ T s i ( v , g ) ( y , p ) jt ≤ x jgt ∀ i , j ∈ N ; v , y ∈ VH ; g , p ∈ L ; t ∈ T ∑ j ≠ i ∈ N s ijt ≤ w ∀ i ∈ N , t ∈ T | z vtg - z v , t - 1 , g | = sw vtg ∀ v ∈ VH ; t ∈ T ; g ∈ L ∑ t ∈ T sw vtg ≤ 1 ∀ v ∈ VH ; g ∈ L B ≤ ∑ i ∈ N ∑ g ∈ L x ivgt + M ( 1 - ∑ g ∈ L zo vtg ) ∀ v ∈ VH ; t ∈ T B ′ ≥ ∑ i ∈ N ∑ g ∈ L x ivgt - M ( 1 - ∑ g ∈ L zo vtg ) ∀ v ∈ VH ; t ∈ T Q ≤ ∑ i ∈ N ∑ l ∈ L x ikl + M ( 1 - ∑ l ∈ L zo vtg ) ∀ v ∈ VH Q ′ ≥ ∑ i ∈ N ∑ l ∈ L x ikl - M ( 1 - ∑ l ∈ L zo kl ) ∀ k ∈ H ( 1 - zint vg ) sw vtg = zo vtg ∀ v ∈ VH ; g ∈ L ; t = 1 ( 1 - z v , t - 1 , g ) sw vtg = zo vtg ∀ v ∈ VH ; g ∈ L ; t ≥ 2 zint vg sw vtg = zc vtg ∀ v ∈ VH ; g ∈ L ; t = 1 z v , t - 1 , g sw vtg = zc vtg ∀ v ∈ VH ; g ∈ L ; t ≥ 2 B ′ - B ≤ φ Q ′ - Q ≤ φ ′ x ikl , x ivgt , zint vg , z vtg , z kl , zo kl , zo vtg , zc vtg , sw vtg , s i ( k , l ) ( h , r ) jt , s i ( k , l ) ( v , g ) jt , s i ( v , g ) ( y , p ) jt , s ijt ∈ { 0 , 1 } ∀ i , j ∈ N ; k , h ∈ H ; v , y ∈ VH ; l , r , g , p ∈ L ; t ∈ T η itj A , η ikht B , η ikvjt C , η ivkjt D , η ivyjt F , η vtg ZH , η vtg ZHO , η vtg ZHC ≥ 0 ∀ i , j ∈ N ; k , h ∈ H ; v , y ∈ VH ; l , r , g , p ∈ L ; t ∈ T

5 Computational experiments

To demonstrate the validity of the formulation hub model and the usefulness of the solution method presented, various numerical experiments are carried out and the results are presented. Accordingly, three test problems with different sizes are taken into account, and for every size, the experiments are done under three levels of various uncertainties (i.e., ρ = 0.1, 0.3, 0.5). At first, the robust and deterministic models are solved through nominal data. Nominal data are randomly produced through the random distributions given in Table 2.

The uncertainty levels for all parameters in each test problem are the same ( i . e . , ρ A = ρ B = ρ C = ρ D = ρ F = ρ ZH = ρ ZHO = ρ ZHC ) and for deterministic models (ρ = 0). The computational results for deterministic and robust models 1 and 2 are shown in Table 3. Moreover, all the mathematical models are coded in the optimization software (i.e., GAMS).

Regarding the results given in Table 3, this study is expecting to have worse findings from the robust models than the results obtained from the deterministic model. It is because that this study for the robust optimization considers the worst case until the least loss and risks are practically encountered. In addition, as it is assumed with the level of uncertainty increase, the value of objective function deteriorated. As a matter of fact, this indicates that by enhancing the value of existing uncertainty of the network, the model solution is satisfying these statuses and corresponding itself to the present condition. Thus, this study suggests that everything may increase the uncertainty of system since decision making is sensitive and problematic. The optimization methods adapt themselves to conditions and produce solutions with lower unsuccessful implementation possibilities compared to deterministic models, but they need more installation expenditures.

Regarding the results given in Table 4, the solutions of the optimal network design is given in without balancing requirements. These solutions are unbalanced in terms of the assignment of spokes to hubs. Suppose now that a balancing requirement is enforced such that the difference between the maximum and minimum number of nodes assigned to some hub should be at most equal to one node. Hence, in this case, the optimal network designs differences. Now, it can be seen that the network is balanced. Therefore, it could have multiple benefits for decision making in the hands of transportation experts or decision makers. Furthermore, the capacity levels of the operating hubs also change. In addition, the results for the purpose of this condition are greater than the previous case. Figs. 3 and 4 demonstrate the structure of the air hub network for the without and with balancing requirements situations, respectively. As it can be indicated feasibility, flexibility and stability of the proposed model.

In addition, this study randomly generates 25 test problems, along with that problem presented by Taghipourian et al. [10] are used, to compare the performance of the presented SAICA with five existent meta-heuristic algorithms (i.e., genetic algorithm, simulated annealing, ant colony, imperialist competitive algorithm and tabu search) in large-sized problems. In order to compare the algorithms, this study considers objective function and CPU time as the measures of efficiency and effectiveness and examines the algorithms in 25 problems separately [29]. Algorithms are coded in C++ and three independent runs are carried out for each algorithm; in each run, the best objective function and related CPU time are recorded. Algorithms run on a PC with a Pentium 4.3 GHz processor with 4 GB of RAM. The results of running algorithms are presented in Table 5 for 10 test problems.

6 Discussion

This study has proposed a robust dynamic virtual hub location problem. In fact, a dynamic perspective has been considered so that the decisions on locating the virtual hubs and determination of path among any original and destination nodes have been made in the entire planning horizon. To develop the given mathematical models to handle the uncertain data, transportation costs, demand, fixed opening and closing costs, and maintenance costs are ensured to vary in uncertain situations. Then, the tractable robust counterpart of the presented deterministic model has been applied to find out the robust solutions. Moreover, a hybrid meta-heuristic algorithm based on simulated annealing and imperialist competitive algorithms has been utilized in order to solve the proposed problem. Since in some applications of the HLP the use of multiple allocations of non-hub nodes to the hubs can be justified, relaxing the single allocation limitation could decrease the transportation time on some routes. It is done while the total cost is increased owing to more transporters and paths being used. In addition, as speed has an important role when the flows must arrive at their destination at a certain time, considering specific due dates for flows and minimizing the weighted deviation from these due dates at each destination node is suggested as a future research direction. Moreover, in fact the use of meta-heuristic algorithms can achieve an appropriate solution in a reasonable time. In addition, the convergence of these methods for closing to optimal solution is much more than other methods. Therefore, this can be an expression of the productivity of these methods in air transportation systems.

7 Conclusion

This study has defined a dynamic virtual hub location problem and has proposed a new robust integer linear planning model to represent a solution. In fact, a dynamic perspective was considered so that the decisions on locating the virtual hubs and determination of path among any original and destination nodes were made in the entire planning horizon. To develop the given optimization models to deal with the uncertain information, transportation costs, demand, fixed opening and closing costs, and maintenance costs are ensured to vary in an uncertain closed box condition. Then, the related semi-definite formulation was given based on uncertain variables. At last, the tractable robust counterpart of the presented deterministic model was applied to find out the robust solutions. Moreover, a meta-heuristic algorithm based on two simulated annealing and imperialist competitive algorithms were utilized in order to solve the proposed problem. Finally, numerical examinations were administered to completely represent the efficiency and utility of the proposed model and solution approaches.