Abstract
This paper presents a bi-objective model for the design and optimization of a sustainable hierarchical multi-modal hub network. The proposed model focuses on sustainability by considering economic, environmental, and social aspects of the decisions in a hierarchical network. A case of Turkish network for freight transportation is used to validate the proposed model. To solve the small-sized problems, the augmented epsilon constraint method version 2 (AUGMECON2) is applied. It can be inferred from the Pareto-optimal set obtained by AUGMECON2 that the effect of increasing the number of hubs after a threshold is marginal. The current contribution proposes two multi-objective genetic algorithms (NSGA-II and NRGA), which incorporate LP solving and Dijkstra algorithm. The results show the superiority of NRGA compared to NSGA-II in terms of solution time. Also, we present an alternative, more efficient formulation to the problem. Based on the alternative formulation, in addition to AUGMECON2, we use two exact methods, including Torabi and Hassini (TH) method and augmented weighted Tchebycheff procedure (AWTP), to find Pareto-optimal solutions for small, medium, and large-sized problems (including the case study). The performance of the proposed solution methods is measured using some multi-objective indicators. The results show the superiority of AUGMECON2.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Hubs are facilities that reduce the number of connections in a network. Instead of a direct link between pairs of Origin/Destination (O/D) nodes, each node connects to a hub and, through it, with indirect and fewer connections, connects to other nodes.
Hub-and-spoke design problem, also called hub location problem (HLP), seeks to find a set of nodes named hub to minimize the defined cost in the problem in a way that there is at least one route between each pair of O/D nodes. Three main characteristics are attributed to the classic HLP. First, a complete architecture is assumed for a hub network, i.e., every two hubs are connected via a link. Second, economies of scale on transportation costs, between hubs and between O/D nodes and hubs, are made possible by the consolidation of flows. Third, direct connection between O/D pairs without the use of hub(s) is not allowed.
The telecommunication networks, airlines, and cargo delivery systems are some well-known instances for the applications of the HLP (Nasiri et al. 2018b; Wasner & Zäpfel 2004). This research mainly considers a freight transport company in Turkey that cares about sustainability. A typical freight transport system is composed of area and central offices. Area offices receive and deliver shipments from/to customers directly, and central offices receive and deliver shipments from/to area offices or send shipments to another central office. Although more than one area office can exist in a town, it may have no central office. Therefore, each area office should be allocated to a central office.
As a result of the above description about a freight transport system, freight transport networks are very similar to hub networks (Arbabi et al. 2021). In this way, area and central offices in freight transport networks correspond to demand nodes and hubs, respectively. Moreover, economies of scale are obtained due to the consolidation of shipments that are supposed to be transported between central offices. Consequently, the freight transport problem can be recognized as a HLP (Alumur et al. 2012b; Dukkanci and Kara 2017).
Road freight transport has been a rapidly growing contributor to carbon dioxide (CO2) emissions (European_Commission 2015; Ahmad et al. 2022) and requires effective policy towards achieving zero carbon (Kannan et al. 2022; Karthick and Uthayakumar 2022). Moreover, social responsibility is a major concern of the companies, and they take the social issues into account in their decision-making (Govindan 2022a; Zarbakhshnia et al. 2022). However, classic HLPs traditionally focus on minimizing the total transportation cost.
Consider a freight shipping (or parcel delivery) company that uses ground and air transportation modes in a hierarchical structure to transport the customer’s demand from an origin to a destination. The model presented in this paper can help the manager of this company to minimize the current investment costs. In addition, pursuing sustainable development, the company intends to create at least a certain number of jobs and to ensure its produced emissions will not exceed a predetermined level. Also, to improve the level of service, the maximum travel time in its network should be minimized (as an index of responsiveness). Note that opening the hubs creates fixed job opportunities such as managerial positions, which do not depend on the transportation flow in a particular hub. In addition, by opening the hubs, variable job opportunities are created that depend on the amount of incoming flow to the hub (such as workers operating on the incoming flows). In this study, it is assumed that only one shipping company is responsible for the freight. Also, for each shipment, from origin to destination, only one shipment contract is concluded. For this reason, the network under consideration is multi-modal.
If a freight company wants to increase its level of service and to improve its social and environmental sustainability aspects while paying attention to the minimization of economic costs of network design, the decisions resulting from separately solving each of these problems will not necessarily be the optimal decisions for the company. The objectives of these two problems are in conflict with each other, so the best decisions that can be made for each problem are not necessarily desirable or even feasible for the other problem. In this research, the hierarchical HLP and sustainable HLP are considered as an integrated problem. A freight company that only seeks to minimize transportation costs and fixed network design costs should design a network that selects facilities with lower fixed costs. In addition, the routes should be selected in such a way that reduces transportation costs. But if the company pays attention to sustainability aspects in addition to the economic costs, it should design the network so that the travel time is reduced for the most distant demands, routes are selected that reduce emissions, and hubs are selected that increase employment levels. Moreover, in order to increase the level of employment, more flows should enter the hubs. These are not necessarily choices that will minimize economic costs. Therefore, in the present study, the aim is to provide decisions to the company manager in which the above objectives are met simultaneously.
The remainder of this paper is organized as follows. Section 2 gives the literature review, and Sect. 3 presents a mathematical model for Sustainable Hierarchical Multi-modal Hub Network Design Problem (SHMHNDP). In Sect. 4, an alternative formulation for the problem is presented. In Sect. 5, multi-objective optimization methods are proposed to solve the problem. Section 6 presents the numerical experiments. Finally, conclusions and future research are discussed in Sect. 7.
2 Literature review
The concept of hub was first developed by Goldman, (1969), which was an extension of Hakimi (1964)’s switching centers’ location problem. The first formulation of HLP was developed as a quadratic model by O'kelly (1987). Moreover, the linear model of HLP was presented by (Campbell 1994, 1996). (Aykin 1994, 1995a, 1995b) and (Klincewicz 1991, 1992) proposed various extensions of HLP. The application of the hub location idea in telecommunication and air transportation was examined by Bryan and O'kelly (1999). A survey on hub location models, classification, solution methods, and applications were carried out by Farahani et al., (2013).
A common assumption in many HLPs is that only one transportation mode exists between demand nodes and hubs and between hubs. A limited number of studies relaxed this assumption and took multiple transportation modes into account (Alumur et al. 2012a, 2012b; Ambrosino and Sciomachen 2016; Karimi et al. 2018; Maiyar and Thakkar 2018).
In recent years, considering sustainability in any new design and innovation is converted into an important issue (Govindan 2022a, b; Sharma et al. 2022; Kannan 2021). In particular, several studies take sustainability into account in HLPs. Mohammadi et al. (2014) presented a hub covering location problem considering environmental objectives. The objectives include minimizing greenhouse gas emissions and noise pollution. Moreover, they investigated the importance of considering vehicle speed in a sustainable HLP. Zhalechian et al. (2017b) presented a mathematical model for a multi-modal HLP considering the following objectives: minimization of total transportation and investment costs, minimization of the maximum transportation time between nodes, and minimization of noise pollution costs. To optimize the social and environmental impacts and costs of a biofuel supply chain, (Roni et al. 2017) developed a mixed-integer linear mathematical model to minimize the hub location cost and the unmet demand penalty cost. In their study, environmental and social issues have been taken into account, and a case of the Midwest region of United States was examined. Xu et al. (2018) dealt with designing an intermodal transportation network, as a special case of HLP, associated with the port competition while considering environmental concerns of stakeholders. As can be seen from researches mentioned above, although considering sustainability in multi-modal networks is more practical, it is not yet widely studied.
Moreover, in the traditional HLP, only two layers exist in the network: one among hubs and the other between hubs and demand nodes. However, real-world networks are more complex and involve more than two levels. A hierarchical hub structure is, hence, a more practical network. Yaman (2009) proposed a model for the single assignment hierarchical hub location in a three-level network. In this model, regarding delivery time constraints, the objective was to minimize the costs of transportation and hub establishment. Lin (2010) proposed a model for the design of a hierarchical hub network for a dual express system with the aim of minimizing fixed costs and transportation costs. The novelty of this model was to consider time constraints for demand pairs.
Later on, Alumur et al. (2012b) developed a hierarchical multi-modal hub location model with time-definite deliveries in a star network. The objectives in this model were the minimization of transportation costs and fixed costs of the links. The novelty was to consider a defined time for departing vehicles from the hubs. Yaman and Elloumi (2012) introduced a star p-hub center problem with the aim of minimizing the maximum path in the network and a star p-hub median problem with the aim of minimizing routing costs in a star/star network with a central hub. Davari et al. (2013) studied an incomplete hub covering location problem with the aim of maximizing the credibility of satisfying each flow in the network in less than a predefined time. Karimi et al. (2014) studied a capacitated single allocation hierarchical hub median location problem with the aim of minimizing total routing costs. Rajabi and Avakh Darestani (2015), regarding dispersion criterion for central hubs in a three-level network, attempted to locate hierarchical hubs in order to minimize transportation costs. Dukkanci and Kara (2017) studied routing and scheduling issues in the hierarchical HLP. Zhong et al. (2018) proposed a hybrid method for using hierarchical hub locations with the aim of integrating urban and rural public transportation.
In the context of hub center location problems, which are related to the present study, we refer to the research by Campbell (1994) and Kara and Tansel (2000). In these studies, minimization of service or cost measures is considered. These measures include the maximum travel time or flow cost between all demand nodes or arcs in the network and the maximum travel time or flow cost associated with an access arc. Campbell et al. (2007) and Ernst et al. (2009) also played an important role in developing mathematical models for this problem. Table 1 shows the studies which considered sustainability aspects or hierarchical network for HLP.
Recent works on hierarchical multi-modal HLP include the following: Shang et al. (2020) proposed a memetic algorithm and a Monte Carlo simulation to solve a stochastic hierarchical multi-modal HLP in a ring-star-star network. In addition, Ma et al. (2020) proposed a mixed-integer programming model for hierarchical multi-modal HLP considering time restrictions for a China railway express network. Moreover, Korani et al. (2020) developed mathematical models and a Lagrangian relaxation solution method for a reliable hierarchical multi-modal HLP. Later on, Shang et al. (2021) proposed two heuristic solution methods based on variable neighborhood search and multi-objective genetic algorithm for a bi-objective hierarchical multi-modal HLP. The objectives of the problem were minimization of overall system-wide costs and the maximum delivery time.
To the best of our knowledge, sustainability aspects have not been considered in hierarchical hub location models. The main contribution of this study, which distinguished our efforts from related studies, is designing a hierarchical multi-modal hub network considering economic, environmental, and social aspects. Given that the present model is multi-objective, the modelling approaches to multi-objective HLPs and the proposed solution methods for these problems are listed in Table 2. According to Table 2, researchers have used various methods, including exact, heuristic, metaheuristic, and hybrid methods, to solve the multi-objective HLP. In this research, to solve the present problem, we use three exact solution methods (AUGMECON2, TH, and AWTP) and two metaheuristic solution methods (NSGA-II and NRGA).
3 Mathematical modelling
In this section, a mathematical formulation for SHMHNDP is proposed. In this model, two transportation modes are studied: truck and airplane. The customers are served by a set of trucks and airplanes from \(P\) opened ground or airport hubs. There is an airport as a central hub, and other airport hubs are directly connected to the central hub. The transportation at the links between airport hubs and the central hub is done by airplane, and transport at other links is performed using the trucks. An instance of the hierarchical network is shown in Fig. 1.
In Fig. 1, there is a central hub (circle), three airport hubs (triangles) that are directly connected to the central hub, seven ground hubs (squares), and the other demand nodes allocated to the hubs. The network studied in this research is the same network used by Alumur et al. (2012b), with the difference that in this network, if two ground hubs are assigned to an airport hub, the two hubs will be connected to each other. While in the network used by Alumur et al. (2012b), this is not necessarily the case (i.e., two ground hubs can be connected or not).
3.1 Assumptions
In the proposed formulation for SHMHNDP, the following assumptions are considered:
-
The number of hubs is predetermined.
-
The location of the central hub is specified.
-
Two transportation modes (airplane and truck) are considered.
-
There are direct links between the central hub and the other airport hubs.
-
Each demand node is allocated to exactly one hub (single allocation).
-
There is no direct link between the airport hubs.
-
The flow quantity from the origin to the destination is determined.
-
All of the parameters are considered to be deterministic.
-
The capacity of the hubs is assumed unlimited.
4 Notations
In this subsection, sets, parameters, and variables used in the mathematical modelling are presented. The order of presentation is as follows: sets used in hub network design (including demand nodes, candidate nodes for hubs, and central hub), parameters (except parameters related to the calculation of emissions), decision variables, variables used in the linearization of nonlinear terms of the model, and parameters used in the calculation of emissions.
Sets
\(N\) | Demand nodes |
\(H\subseteq N\) | Candidate nodes for hubs |
\(A\subseteq H\) | Candidate nodes for airport hubs |
\(o\in A\) | Central hub |
Parameters
\(P\) | The number of hubs (central and non-central) |
\({w}_{ij}\) | Demand flow from node \(i\in N\) to node \(j\in N\) |
\({t}_{ij}\) | Travel time by trucks between nodes |
\({t}_{ij}^{P}\) | Travel time by airplanes between nodes |
\(\alpha\) | Discount factor for travel time using trucks on inter-hub links |
\({c}_{ij}\) | Unit cost of routing from node \(i\in N\) to node \(j\in N\) if one of nodes is hub and another is non-hub |
\({c}_{jo}^{P}\) | Routing cost from node \(j\in A\backslash \left\{o\right\}\) to the central hub |
\({c}_{oj}^{P}\) | Routing cost from the central hub to node \(j\in A\backslash \left\{o\right\}\) |
\({c}_{jk}^{T}\) | Routing cost (for trucks) from node \(j\in H\) to node \(k\in H\) if both nodes are hubs |
\({FE}_{ij}\) | Fixed cost of establishing a link between node \(i\in N\) and node \(j\in H\) |
\({FE}_{jk}^{T}\) | Fixed cost of establishing a truck link between node \(j\in H\) and \(k\in H\backslash \left\{j\right\}\) |
\({FE}_{j}^{P}\) | Fixed cost of establishing a link between node \(j\in A\backslash \left\{o\right\}\) and the central hub |
\({FJG}_{j}\) | Fixed job opportunities created by the establishment of ground hub \(j\in H\) |
\({FJA}_{l}\) | Fixed job opportunities created by the establishment of airport hub \(l\in A\) |
\({UJG}_{j}\) | Unit job opportunities (related to flow) in ground hub \(j\in H\) |
\({UJA}_{l}\) | Unit job opportunities (related to flow) in airport hub \(l\in A\) |
\({OF}_{i}=\sum_{s\in N}{w}_{is}\) | Total flow originated from node \(i\in N\) |
\({DF}_{i}=\sum_{s\in N}{w}_{si}\) | Total flow delivered in node \(i\in N\) |
\(Emissions\) | The maximum allowable amount of emissions |
\(Jobs\) | The number of job opportunities to be created |
Decision variables
\({z}_{ij}\) | Binary variable for allocation of node \(i\in N\) to hub \(j\in H\) |
\({h}_{jl}\) | Binary variable for allocation of hub \(j\in H\) to airport hub \(l\in A\) |
\({r}_{jk}^{l}\) | Binary variable that is equal to 1 if \(j\in H\) and \(k\in H\backslash \left\{j\right\}\) are hubs and both are allocated to the same airport hub \(l\in A\) |
\({Y}_{jk}^{i}\) | Flow amount, initiated from node \(i\in N\) and passes node \(j\in H\) and \(k\in H\backslash \left\{j\right\}\) by trucks |
\({X}_{jo}^{i}\) | Flow amount, initiated from node \(i\in N\) and passes node \(j\in A\backslash \left\{o\right\}\) toward the central hub |
\({X}_{oj}^{i}\) | Flow amount, initiated from node \(i\in N\) and passes the central hub toward node \(j\in A\backslash \left\{o\right\}\) |
\(\phi\) | Variable that denotes the maximum travel time in the network |
Variables for the linearization
\({\tau }_{ijl}\) | Binary variable that is equal to 1 if node \(i\in N\) is allocated to hub \(j\in H\) and hub \(j\in H\) is allocated to hub \(l\in A\) |
Parameters used for modelling the emission of trucks
\(M\) | Truck mass (summation of carried and empty load) (\(\mathrm{kg}\)) |
\(g\) | Constant of gravity (9.81 \(\mathrm{m}/{\mathrm{s}}^{2}\)) |
\(a\) | Acceleration of truck (\(\mathrm{m}/{\mathrm{s}}^{2}\)) |
\({v}_{ij}\) | Velocity of truck in arc \((i,j)\) (\(\mathrm{m}/\mathrm{s}\)) |
\({\theta }_{ij}\) | Angle of road in arc \((i,j)\) (degree) |
\(\rho\) | Air density (\(\mathrm{kg}/{\mathrm{m}}^{3}\)) |
\(AR\) | Frontal surface area of the truck (\({\mathrm{m}}^{2}\)) |
\({C}_{d}\) | Factor of the drag resistance |
\({C}_{r}\) | Factor of the rolling resistance |
\(LW\) | Weight of load carried by each truck (\(\mathrm{kg}\)) |
\(EW\) | Weight of empty truck (\(\mathrm{kg}\)) |
\({d}_{ij}\) | Distance between nodes \(i\) and \(j\) (\(\mathrm{m}\)) |
\(\beta\) | Particular fixed value of the truck |
\({\gamma }_{ij}\) | Particular fixed value of arc \((i,j)\) |
The particular fixed value of arc \((i,j)\) and the particular fixed value of the truck are calculated as Eqs. (1) and (2), respectively:
Finally, the amount of emission produced by trucks can be calculated to be used as the left-hand side of constraint (25) of Sect. 3.3.
4.1 Mathematical model
Here, a mathematical formulation is suggested for SHMHNDP.
subject to:
In this formulation, the summation of transportation costs in the hierarchical network and fixed costs of the links constitute the first objective function in Eq. (3). The costs of transportation are calculated according to the flows. These flows include flows between demands and hubs, flows in track routes, and flows in air routes. The second objective function, Eq. (4), minimizes the maximum travel time in the network.
Constraint (5) ensures that every demand node is exactly allocated to one hub (single allocation). By constraint (6), if and only if a node is selected to be a hub, demand nodes can be assigned to it. Constraint (7) expresses single allocation in the first level (allocation to airport hubs). By constraint (8), ground hubs can be assigned to a node if and only if it is selected as an airport hub. Constraint (9) ensures that P hubs (in total) must be located. Due to constraint (10), node o must be the central hub. Constraints (11)–(14) specify how to choose truck routes. By constraint (15), ground hubs assigned to a common airport hub must be connected to each other. Constraints (16)–(20) are related to routing flows in a hierarchical network. Constraint (21) specifies routes that consist of two links and have a hub. In constraint (22), routes consist of an airport hub and two ground hubs, and ground hubs are allocated to the airport hub.
Constraint (23) includes the routes in which there are two ground hubs that are connected to each other. Constraint (24) is related to the routes in which there are a central hub, two airport hubs, and two ground hubs.
In constraints (21)–(24), the travel times for all routes are calculated. Variable ϕ must be greater than or equal to all calculated travel times. Constraint (25) states that the total amount of emissions produced by the trucks must not be greater than a specified value. Constraint (26) guarantees that at least a specified number of jobs must be created. Constraints (27)–(31) describe the type of decision variables.
In constraints (22) and (24), the nonlinear term \({z}_{ij}{h}_{jl}\) can be linearized as Eqs. (32) and (33):
The proposed SHMHNDP after linearization, in the worst case, when we have |N| =|H| =|A|= n, involves a total of 3n3 + n2-2n + 1 decision variables. Of these, 2n3 variables are binary variables, and n3 + n2-2n + 1 variables are continuous variables. Thus, the number of decision variables in the worst case is O(n3). Furthermore, the number of problem constraints equals n6-3n5 + 4n4 + 4n3-n + 4. Of these, there are n6 − 3n5 + 4n4 − 2n3 constraints related to the calculation of the maximum travel time (constraints (21)–(24)), and 6n3 − n + 4 constraints constitute other constraints. Thus, the number of constraints in the worst case is O(n6). It is observed that a high percentage of the problem constraints are related to the maximum travel time constraints. For example, if there are only ten demand nodes on the network, in the worst case, the problem would be 743,994 constraints. Of these, 738,000 constraints are related to the calculation of the maximum travel time on the network, and the number of other constraints is 5994.
5 Alternative formulation
In this section, we present an alternative formulation to reduce the number of constraints of the initial formulation and to solve more instances. First, we introduce some valid inequalities to improve the initial formulation. These inequalities are implied from constraints (21), (23), and (24).
Valid inequality 1. For each feasible solution of the problem, Eq. (34) is valid:
Proof
If \({z}_{ij}=1\) and \({z}_{sk}=1\), then the right-hand side of Eq. (34) is the same as the right-hand side of Eq. (22). Because in this case \({z}_{jj}=1\) and \({z}_{kk}=1\). If \({z}_{ij}=1\) and \({z}_{sk}=0\), two cases occur: if \({z}_{kk}=1\), the above relation provides a lower bound for \(\phi\). If \({z}_{kk}=0\), the above relation provides a lower bound for the travel time between node \(i\) and any hub allocated to node \(l\). The case \({z}_{ij}=0\) and \({z}_{sk}=1\) is the same as before. If \({z}_{ij}=0\) and \({z}_{sk}=0\), then two cases occur. If \({z}_{jj}=1\) and \({z}_{kk}=1\), the right-hand side indicates the travel time between the hubs \(j\) and \(l\). If \({z}_{jj}=1\) and \({z}_{kk}=0\), the right-hand side of the above relation provides a lower bound for the travel time between node \(j\) and any hub assigned to node \(l\). The case \({z}_{jj}=0\) and \({z}_{kk}=1\) is shown similarly, and the case \({z}_{jj}=0\) and \({z}_{kk}=0\) is easy.
Valid inequality 2. Constraint (21) can be replaced by Eq. (35):
Proof
If \({z}_{ij}=1\) and \({z}_{sj}=1\), the right-hand side of Eq. (35) is equal to the right-hand side of Eq. (21). But if \({z}_{ij}=1\) and \({z}_{sk}=1\) for \(j,k\in H,j\ne k\), the right-hand side of the above relation is less than or equal to the right-hand side of Eq. (23). The above relation has fewer constraints than Eq. (21).
Valid inequality 3. Constraint (23) can be replaced by Eq. (36):
Proof
Hub \(j\in H\) and hub \(k\in H\backslash \left\{j\right\}\) can only be allocated to one common airport hub \(l\in A\). Therefore, for index \(l\) of the common airport hub, the right-hand side of Eq. (36) and the right-hand side of Eq. (23) are the same.
Equation (36) has fewer constraints than Eq. (23).
In order to provide an alternative formulation, we define some variables. Variable \({\mu }_{j}\) represents the value of the longest travel time from the nodes assigned to node \(j\). We also consider variable \({\theta }_{j}\) as the value of the longest travel time from node \(j\) to nodes assigned to node \(j\). Variable \({\delta }^{l}\) represents the longest travel time from demand nodes to airport hubs, and variable \({\eta }^{l}\) represents the longest travel time from airport hubs to demand nodes. Variable \({\delta }^{o}\) represents the longest travel time from the demand nodes to the central hub, and variable \({\eta }^{o}\) represents the longest travel time from the central hub to the demand nodes. According to these definitions, the constraints related to the calculation of the maximum travel time can be replaced by Eqs. (37)–(47).
Thus, the alternative formulation simultaneously optimizes the first and second objective functions (Eqs. (3) and (4)) subject to Eqs. (5)–(20), (25)–(31), (35), and (37)–(47).
The alternative formulation of the SHMHNDP, in the worst case, when we have |N| =|H| =|A|= n, involves a total of 2n3 + n2 + 5 decision variables. Of these, n3 variables are binary variables, and n3 + n2 + 5 variables are continuous variables. Thus, the number of decision variables in the worst case is O(n3). Also, the number of problem constraints equals 4n3 + 6n2 + n + 2. Thus, the number of constraints in the worst case is O(n3). Note that in the initial formulation, the number of constraints related to the calculation of maximum travel time was n6-3n5 + 4n4-2n3, that is O(n6). While, in the alternative formulation, the number of constraints of calculating the maximum travel time equals 4n2 + 2n-2, that is O(n2). For example, if |N|= 10, then in the initial formulation, we have 738,000 constraints, and in the alternative formulation, we have 418 constraints related to the calculation of the maximum travel time.
6 Multi-objective optimization methods
Multi-objective optimization seeks to find one or more optimal solutions in problems with more than one objective. These objectives are often in conflict with each other, and thus finding an optimal solution for all objectives at the same time is usually impossible.
6.1 Domination and Pareto optimality
Domination is the basic concept considered in multi-objective optimization (all of the min type), which is defined as follows:
Consider a problem with \(\kappa\) objectives. The solution p dominates the solution \(q\) \((p\prec q\)) if the following conditions are met:
(1) In none of the objective functions, the value of \(p\) is worse than the value of \(q\):
(2) At least in one of the objective functions, the value of \(p\) is strictly better than the value of \(q\):
In this case, the solution \(p\) is non-dominated, and the solution \(q\) is dominated. In a set of solutions, a member is a non-dominated solution if no other member dominates it. In addition, the set of non-dominated solutions is called the Pareto set.
6.2 The Epsilon constraint method
The epsilon constraint method can find efficient solutions for multi-objective problems. In this method, we optimize one of the objective functions while the other objective functions are included in the problem constraints. An improved version of the original epsilon constraint method, named augmented epsilon constraint method (AUGMECON), was proposed by (Mavrotas 2009). Then, (Mavrotas and Florios 2013) presented a novel version of the epsilon constraint method, namely, augmented epsilon constraint method version 2 (AUGMECON2). In this method, the information of slack variables is used to reduce computational time by avoiding redundant iterations. More details about the AUGMECON2 method are described in Appendix A.
6.3 Multi-objective genetic algorithm
The classic HLP is NP-hard (Skorin-Kapov et al. 1996). The hierarchical HLP is also NP-hard, because the classic HLP is a special case of the hierarchical HLP (Yaman 2009). In addition, in our problem, there are many constraints related to the calculation of maximum travel time on the network, which can increase the complexity of the problem in terms of the solution space and solution time. Besides, as the size of the problem increases, the solution time increases exponentially, and general solvers cannot solve the problem in a reasonable time. Therefore, in this section, we present two metaheuristic algorithms to solve the problem in larger scales. Among the developed metaheuristic algorithms, the multi-objective genetic algorithm is popular because of its capability in providing Pareto solutions that are uniformly distributed in the search space and are more desirable for the decision-maker. This algorithm maintains the diversity among non-dominated solutions through the crowding mechanism and does not require other control tools. Further, this algorithm is elitist and retains the Pareto solutions found in previous generations. Two of the most powerful algorithms for solving multi-objective problems are Non-dominated Sorting Genetic Algorithm version 2 (NSGA-II) and Non-dominated Rank-based sorting Genetic Algorithm (NRGA), which were proposed by (Deb et al. 2002). The steps of these algorithms are as follows:
6.3.1 Solution representation
At this stage, the way of coding the solutions of the problem is determined. The string or vector of genes, which shows a coded solution, is called a chromosome. An example of the solution representation for the present model is shown in Fig. 2.
In this solution representation, each chromosome consists of two parts. The first part shows how to allocate demand nodes to the located hubs (both ground and airport hubs). The second part describes how to allocate ground hubs to airport hubs. In the second part, when separating airport hubs from ground hubs, the numbers related to airport hubs appear twice, and the numbers related to ground hubs appear only once. Note that the content of the last two genes in each chromosome is always equal to 0 (node 0 is the central hub and it is not allocated to any other hub). According to Fig. 2, because the numbers 2 and 0 appear twice in the second part, these two nodes are selected as airport hubs, and other hubs that appear only once include ground hubs (hubs 1, 8, and 3). The numbers that appear between the two airport hubs show how the ground hubs are assigned to the right-hand side airport hub. Therefore, ground hub 3 is assigned to the central hub, and ground hubs 1 and 8 are assigned to airport hub 2. Once the hubs are located, and the ground hubs are allocated to the airport hubs, it is possible to determine how the other demand points are allocated to the hubs. In the first part of the chromosome, the numbers between the two hubs indicate how the other demand nodes are allocated to the right-hand side hub. If no number is seen between the two hubs, it means that no node is assigned to the hub on the right-hand side. Therefore, in Fig. 2, the nodes are allocated to the located hubs as follows: nodes 4 and 5 to hub 3, node 7 to hub 1, node 6 to hub 2, and node 9 to hub 8. A schematic representation of the above solution is depicted in Fig. 3.
6.3.2 Creating an initial population
After identifying an appropriate mechanism to convert any solution to a chromosome, a set of chromosomes creates the initial population. In this study, the initial population is generated randomly, and the number of its members is considered to be (npop).
6.3.3 Fitness evaluation
In this step, the fitness of each individual is calculated. As we discussed in Sect. 3, the complexity of the problem is mainly related to the high number of constraints for calculating the maximum travel time on the network. Therefore, for specific values of binary variables that are determined from the chromosome, in calculating the value of the first objective function, we relax these constraints because they only include binary variables and maximum travel time variables that are not entered in calculating the first objective function value (continuous variables \({Y}_{jk}^{i}\), \({X}_{jo}^{i}\), and \({X}_{oj}^{i}\) do not exist in constraints of calculating the maximum travel time). In addition, to calculate the maximum travel time, we use a Dijkstra algorithm with polynomial time complexity. In this study, for calculating the value of the first objective, we use the following approach. At first, the values of binary variables are determined based on the individual. Then, these values of binary variables are entered in a commercially available mathematical programming solver (e.g., CPLEX) as parameters, and the first objective function subject to the constraints (16)–(20), (25), (26), (30), and (31) is solved. The reason for the omission of constraints (5)–(15) is that they are already considered in the solution representation. In addition, constraints (21)–(24) are only used for obtaining the second objective; they are not required for calculating the first objective. Because no integer variable exists in the resulting model, it is an LP instead of a MIP problem, and therefore, it can be solved in polynomial time. After solving the LP, if the problem is infeasible, a penalty is considered for the objective functions.
To calculate the second objective function value, the values of binary variables are determined based on the individual, and the corresponding graph structure related to that chromosome is specified. Then, the adjacency matrix of the graph and the travel times between the vertices of the graph (after applying parameter α) are given as inputs to the Dijkstra algorithm. The Dijkstra algorithm calculates the minimum travel time between each pair of vertices of the graph, and the maximum of the minimum travel times (for all pairs) is considered as the second objective function value.
6.3.4 Non-dominating sorting
In this step, each solution is ranked based on the times it is dominated by the other solutions. The solutions that are not dominated by any of the other solutions are located on the first front and assigned rank one. The solutions dominated by at least one of the first front solutions are placed on the second front and assigned rank two, and likewise, all the solutions are sorted out.
6.3.5 Calculation of the crowding distance
After fronting the solutions, the crowding distance criterion is used to evaluate the solutions at a front. In this step, the crowding distance for each solution in each front is calculated, and the closeness of the solution to the other solutions is determined. The solution has a greater crowding distance if it is located in a less crowded space. To determine the crowding distance of the solution i, the average distance of the solution to the two adjacent solutions (in a front) for each objective (m) is calculated, and the summation for all objectives is shown by di as Eq. (50).
6.3.6 Selection mechanism
The only difference between the two algorithms NSGA-II and NRGA used in this study is the implementation of this step outlined below:
-
The NSGA-II selection method: In the NSGA-II algorithm, the binary tournament selection method is used. In this method, the selection is based on the following two conditions:
-
Population rank: The population is selected at lower front ranks.
-
Crowding distance: Assuming that p and q are two members of the same front rank, a member is selected that has a greater crowding distance. In other words, the selection priority is based on the rank and crowding distance, respectively.
-
The NRGA selection method: The selection mechanism in the NRGA algorithm is based on a roulette wheel. In the roulette wheel, the selection mechanism is designed such that better possible members are selected. Each member of the population has two attributes: (a) rank of front, which is located on, and (b) member rank within the front based on the crowding distance. Thus, to select a solution, first, a non-dominated front should be selected. Then, a solution must be selected within that front. The probability of selecting the non-dominated front \(i\) is calculated as Eq. (51):
-
where \({rank}_{i}\) is the rank of the front i, and Nf is the number of fronts determined in the non-dominated sorting step.
The probability of selecting the solution j in the non-dominated front i is calculated as Eq. (52):
where \({N}_{i}\) represents the number of solutions on the front i, and \(ran{k}_{ji}\) denotes the rank of the solution j in the front i, based on the crowding distance.
By defining s1 = ∑Pi and s2 = ∑Pji, the roulette wheel will be defined on two real intervals: [0,s1] and [0,s2]. Based on the calculated probability values, each front occupies a value in the interval [0,s1], and each solution occupies a value in the interval [0,s2]. Then, two random numbers between zero and one are selected. The first random number is used to select the front in [0,s1], and the second random number is used to select one of the solutions in the selected front in the interval [0,s2].
-
Implementing crossover and mutation to produce new offspring
A crossover operator for information exchange between chromosomes in genotype space is used to create offspring chromosomes. The crossover operation can be done in different ways: single-point, two-point, multi-point, and uniform. In this study, the single-point crossover (like Fig. 4) is used. In our implementation, a random point is selected from the allocation part of chromosomes, and the contents of genes before and after that point are exchanged.
In the crossover operation, there may be some repetitive numbers, or some numbers may not appear in the permutation. Hence, repairing of offspring is needed. Thus, repetitive numbers should be removed, and numbers that are not in the permutation need to be added (Fig. 5).
The mutation operator prevents the algorithm from being trapped in local optimum points. In the mutation operation, offspring receives different characteristics from parents. In this study, in order to perform mutation, two points from the allocation part of a chromosome are selected randomly, and contents of genes are replaced (see Fig. 6).
6.3.7 Combining offspring and parent population
In this step, by merging the offspring and parent population, a new population is created. The new population is first sorted based on ranking, during which solutions with worse ranks are eliminated. The remaining population is also sorted according to the crowding distance. Then, the first (npop) individuals are transferred to the next generation of the algorithm.
6.3.8 Termination condition
The number of function evaluations (NFE) is used in this study as the termination condition of the algorithms.
6.3.9 Performance criteria
Because in multi-objective problems, a set of non-dominated solutions is selected as optimal solutions for setting parameters and comparing their efficiency, four comparison criteria (multi-objective indexes) are considered; they are summarized as follows:
-
Quality metric (QM)
The most important criterion for comparing the quality of the solution methods is QM, which is simply obtained in three steps. At first, the results obtained through algorithms are placed in a new archive. Then, all the solutions are again mutually compared to each other to update the archive. Finally, QM is calculated as the number of non-dominated solutions that belong to the results of each algorithm to the number of non-dominated solutions in the archive. The higher percentage indicates the higher quality of the algorithm.
-
Mean ideal distance (MID)
This criterion value is equal to the distance of the Pareto solutions of the algorithm from the ideal point. For a bi-objective problem, MID is calculated as Eq. (53):
In which \(n\) is the number of Pareto solutions, \({f}_{i,total}^{max}\) is the maximum value of objective functions in all algorithms, and \({f}_{i,total}^{min}\) is the minimum value of objective functions in all algorithms. In the above equation, the ideal solution is \(\left({f}_{1}^{Best},{f}_{2}^{Best}\right)\).
-
Spacing metric (SM)
This criterion measures the uniformity of set points in the solution space. Equation (54) presents how to calculate the criterion:
where \(n\) is the number of Pareto solutions, di is the Euclidean distance between solution \(i\) and solution \((i+1)\) in solution space, and \(\overline{d}\) is the mean of distances di.
-
Diversification metric (DM)
This criterion shows the extent of Pareto solutions of an algorithm. DM is calculated using Eqs. (55) and (56).
In which \(\kappa\) is the number of objective functions. Also, \({f}_{m}^{i}\) and \({f}_{m}^{j}\) are the values of the objective function \(m\) for the two Pareto solutions \(i\) and \(j\).
6.4 Torabi-Hassini method and augmented weighted Tchebycheff procedure
In the following, we will use two exact solution methods to solve the SHMHNDP. The methods include the Torabi and Hassini (TH) method and the Augmented Weighted Tchebycheff Procedure (AWTP). The TH method is an interactive method to solve multi-objective optimization problems. This method was introduced by Torabi and Hassini, (2008). The TH method can determine the satisfaction degree of objective functions with respect to decision-maker preferences. This method solves a single-objective parametric mathematical programming problem to get compromise solutions. The TH method details are presented in Appendix B. The AWTP is one of the developed methods for solving multi-objective optimization problems based on reference points. The AWTP was introduced by Steuer and Choo, (1983). This method can find efficient Pareto solutions. The AWTP details are described in Appendix C.
7 Numerical experiments
In this section, the results of the proposed solution methods are presented. Computations are carried out on a laptop with the following characteristics: processor Intel(R) Core (TM) i5-5200U CPU @ 2.20 GHz and 6 GB of RAM. The AUGMECON2, TH, and AWTP methods are coded in GAMS software version 24.1.2 and the CPLEX solver version 12.5.1.0 is applied to solve instances. NSGA-II and NRGA are implemented in MATLAB software version 2014a.
7.1 Test problems and case study
To validate the proposed model, six test problems are solved and the results are reported. Test problems #1 to #5 are generated based on the Turkish dataset (with 81 demand nodes) in Operations Research (OR) library (Beasley 1990), while test problem #6 (hereafter called the case study) is exactly the case study of the Turkish network for freight transportation mentioned by Alumur et al. (2012b). In addition, test problems #1-#6 consist of |N|= 10, 12, 15, 17, 50, 81 demand nodes, respectively. Candidate nodes for hubs consist of |H|= 5, 6, 7, 11, 17, 22 nodes, and candidate nodes for airport hubs consist of |A|= 4, 4, 5, 7, 15, 19 nodes, respectively. Also, the number of hubs that must be located are P = 3, 3, 4, 5, 6, 8, respectively. Demand flows, travel times using ground transportation, transportation costs (distances between the nodes), and fixed costs of establishing the links between the nodes are available in OR library. Other parameters of the model that we needed for test problems are not available in OR library. So, the values of some of these parameters are generated based on the work of Alumur et al. (2012b). The demand points and the candidate nodes for hubs are shown in Fig. 7, and Ankara is selected as the central hub. All of the candidate nodes for hubs are candidates for airports except nodes 3, 68, and 81. Travel time between the central hub and other airport hubs are calculated based on the average speed of airplane (700 km/h). It should be noted that data on the distance is updated due to the construction of new highways within Turkey, and we use the updated data given in OR library via a link. The value of parameters related to emissions and jobs and other characteristics of the generated test problems are presented as online supplementary in Appendixes D and E.
7.2 Parameter setting
Parameters like crossover probability and mutation probability can significantly affect the performance of NSGA-II and NRGA (Gupta et al. 2019). In order to set the parameters of the proposed methods, the Taguchi design of experiment is applied. The way it works is that first, different levels are considered for the parameters that need to be set. Then, the experiments suggested by the Taguchi method should be performed. These experiments involve solving the problem by both algorithms considering different levels for the parameters (according to the proposed levels of the Taguchi method). After solving the problem, the values of multi-objective indicators must be calculated. In order to calculate a response for each experiment, the indicators need to be normalized according to their nature, and a specific weight must be considered for each indicator. After determining the responses, the best levels for the parameters are calculated using the S/N ratio.
Hence, the input parameters of the proposed algorithms and their levels are determined according to Table 3. To determine the most efficient levels of each parameter in the Taguchi method, by using the Minitab software, the orthogonal array L9 is used and nine experiments are set.
By solving the problem, with respect to the Pareto solutions obtained by NSGA-II and NRGA, the four defined criteria are calculated for NSGA-II and NRGA (Table 4). Note that each experiment is repeated six times, and the average of indexes is calculated.
Subsequently, in order to create an output of each experiment, all criteria will be converted to a response by using the following method:
(1) At first, the positive or negative nature of each criterion must be specified. Here, the QM and DM are positive in nature, and thus, higher values are better for them. Instead, the MID and SM are negative in nature. Figure 8 shows the criteria and different situations (the designed experiments).
In Fig. 8, \({O}_{i}\) and \({X}_{j}\) represent situation \(i\) and criterion \(j\), respectively. Also, \({r}_{ij}\) is the value of situation \(i\) in criterion \(j\). The number of experiments is \(\eta\).
(2) The obtained values of the parameters are normalized using the linear normalization technique (Çelen 2014) as Eqs. (57) and (58).
In this technique, criteria with negative nature become positive.
(3) In this step, a Total Weighted Normalized Indicator (TWNI) of the four criteria (Nasiri et al. 2018a) is calculated according to their importance and considered as response. In this problem, the following weights based on the importance of each criterion are intended.
(4) where (wQM,wMID,wSM,wDM) = (102,10,1,1). The results of normalization and calculation of the responses are collected in Table 5.
After obtaining the values for four multi-objective criteria, the response values of each experiment for NSGA-II and NRGA are calculated (column “response” in Table 5). Next, the S/N ratio is used to obtain the suitable level of each input parameter, which is shown in Table 6. The results of Taguchi experiments are reported in Appendix F.
7.3 The performance of multi-objective optimization methods
7.3.1 Results of AUGMECON2 for the alternative formulation
The alternative formulation has fewer constraints than the initial formulation, and it is computationally more efficient. The test problems #4, #5, and #6 (case study), which could not be solved with the initial formulation, can be solved with this formulation. The results of solving test problems #1-#6, including the payoff table and Pareto-optimal solutions obtained by AUGMECON2 method, are presented in Tables 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, and 18. The solution times for test problems #1-#6 are 0.72, 1.52, 2.14, 11.13, 69.08, and 538.94 s, respectively. The Pareto-optimal solution #4 for test problem #6 (case study) is shown in Fig. 9.
7.3.2 Results of NSGA-II and NRGA
The Pareto solutions obtained by AUGMECON2, NSGA-II, and NRGA for test problems #1-#3, and the Pareto solutions obtained by NSGA-II and NRGA for test problems #4-#6 are shown in Fig. 10. According to Fig. 10a, the number of Pareto solutions obtained from AUGMECON2 and NSGA-II is greater than the number of Pareto solutions obtained from NRGA. A Pareto solution has been found by all three algorithms. Also, AUGMECON2 covers a larger area of the solution space. According to Fig. 10b, AUGMECON2 has found more solutions than the other two algorithms. According to Fig. 10c, the number of Pareto solutions generated by AUGMECON2 is greater than NSGA-II and NRGA. Also, the Pareto solutions generated by AUGMECON2 dominate all the Pareto solutions of NRGA and NSGA-II.
In order to compare the Pareto solutions obtained from AUGMECON2, NSGA-II, and NRGA (depicted in Fig. 10), multi-objective indexes for these solution methods are reported in Table 19. According to Table 19, AUGMECON2 outperforms NSGA-II and NRGA in terms of QM.
7.3.3 A comparison between NSGA-II and NRGA
In the following, the performance of the two metaheuristic algorithms (NSGA-II and NRGA) are compared. The purpose of this section is to investigate which of the metaheuristic algorithms performs better in terms of multi-objective indicators (including QM, MID, SM, and DM). For this purpose, it is necessary to prepare different instances of the problem with different sizes and use these instances to make statistical inferences on the performance of these algorithms. After identifying instances, each of these instances must be solved by both algorithms, and the values of multi-objective indicators for each instance are calculated. Then, by statistical tests, the performance of these two algorithms is compared.
To compare the efficiency of the developed metaheuristic algorithms, twenty-two instances with different sizes (small, medium, and large) are generated. We use three datasets for generating instances with different sizes: CAB (O'kelly, 1987), for generating instances with 18 to 25 nodes, IAD (Karimi and Bashiri 2011), for generating instances with 26–37 nodes, and TR (Tan and Kara 2007), for generating instances with 40 to 81 nodes. The reason for using different datasets is to make a more comprehensive comparison of the mean of multi-objective indexes in the two metaheuristic algorithms. The number of demand nodes, candidate nodes for hubs, candidate nodes for airport hubs, central hub, and the number of hubs that must be located are presented in Table 20. Note that sets N, H, and A consist of the first |N|, |H|, and |A| nodes from that dataset. Other details of generating instances are provided in Appendix G. The obtained indexes are presented in Tables 21, 22, and 23. It should be noted that the results are the average of the six times of running the proposed metaheuristics.
In order to compare the performance of the two metaheuristics statistically, we use a T-test. In this way, before using the T-test, a “Two-sample F-test” is used to investigate the equality of variances. If the variances are equal, a “Two-sample T-test assuming equal variances” is applied, and if the variances are not equal, a “Two-sample T-test assuming unequal variances” is applied. In all tests, the null hypothesis is that the variances or averages are equal, and the alternative hypothesis is that they are different. Results of statistical tests and a graphical representation of indexes are shown in Fig. 11.
As shown in Fig. 11, there is no significant difference between the performance of the two proposed metaheuristics in the four indexes. A comparison of the solution times in the proposed metaheuristics with increasing the size of the problem is demonstrated in Fig. 12.
According to Fig. 12, it can be concluded that by increasing the size of the problem, solution times in NSGA-II and NRGA increase but an increase in solution times is reasonable (the test instance with 81 nodes is solved in about four hours). Also, NRGA is faster than NSGA-II except for two instances (instances #1 and #2). However, in small problem instances (with 15 nodes or fewer), AUGMECON2 outperforms NSGA-II and NRGA in terms of the quality of solutions.
7.3.4 Results of TH method
Tables 24, 25, 26, 27, 28, and 29 show the Pareto solutions obtained by the TH method for test problems #1-#6. According to Tables 24, 25, 26, 27, 28, and 29, for a certain value for \(\psi\), with increasing the importance coefficient of an objective function, the satisfaction degree of that objective function does not decrease. Also, for a certain value for importance coefficient, with increasing \(\psi\), the satisfaction degree of the second objective function does not decrease, while the satisfaction degree of the first objective function decreases except in one case. In Table 29, for \({\pi }_{1}=0.2\) and \({\pi }_{2}=0.8\), by increasing \(\psi\) from 0.2 to 0.4, the satisfaction degree of the first objective function increases and the satisfaction degree of the second objective function decreases. It can be concluded that the higher value of the parameter \(\psi\) means more attention to the acquisition of a higher lower bound for the satisfaction degree of the objective functions and thus more balanced solutions are obtained. Conversely, lower values of \(\psi\) mean more attention to the objective function with a higher importance coefficient, and, as a result, unbalanced solutions are obtained.
7.3.5 Results of AWTP method
Tables 30, 31, 32, 33, 34, and 35 show the Pareto solutions obtained by the AWTP method for test problems #1-#6. According to Tables 30, 31, 32, 33, 34, and 35, with increasing the weights of the objective functions, the value of that objective either improves or remains unchanged except in one case (Table 33). In Table 33, by increasing the weight of the first objective function from 0.4 to 0.5, the first objective function value worsens. Also, by decreasing the weight of the second objective function from 0.6 to 0.5, the second objective function value improves.
7.3.6 A comparison between the proposed solution methods
The results of solving test problems #1-#6 by AUGMECON2, TH, and AWTP methods are shown in Fig. 13. According to Fig. 13, the number of solutions obtained by the AWTP is more than the other two methods.
The results of multi-objective indicators for the proposed solution methods on test problems #1-#6 are shown in Table 36. The results of the TWNI based on the normalized indexes are reported in the last column of Table 36. On test problems #1-#6, the average values of the TWNI for AUGMECON2, NSGA-II, NRGA, TH, and AWTP are 77.75, 7.92, 1.54, 65.62, and 44.73, respectively. Therefore, in terms of TWNI, the AUGMECON2 has the best performance among the proposed algorithms. The worst performance is related to the NRGA.
7.3.7 A comparison between the proposed formulations
In this subsection, the performance of the proposed formulations (initial and alternative) in terms of solution time are compared. To do this, we optimize the test problems #1, #2, and #3 using the proposed exact solution methods (AUGMECON2, AWTP, and TH) for the initial and alternative formulations. Note that in the TH method, the compensation coefficient is considered equal to 0.5 and the importance coefficients of the objectives are considered from 0.1 to 0.9 (with a moving step of 0.1). The reported solution time is the sum of the solution time of finding the PIS and NIS values and solving the single-objective problems of the TH method. Also, in the AWTP, the weights of the objective functions are considered from 0.1 to 0.9 (with a moving step of 0.1). The results are reported in Table 37. According to Table 37, the alternative formulation in all three solution methods improves the solution time of the initial formulation. The lowest and highest percentages of improvement are 59.79 and 95.62%, respectively, and the average percentage of improvement is 79.02%.
7.4 Sensitivity analysis
The most important parameters of the model that affect costs and maximum travel time are the number of hubs, the allowable amount of emissions, the number of jobs that must be created, and discount factor for travel time. Thus, we make a sensitivity analysis on these parameters to show their effects on the model. For investigating the effect of the number of hubs on the costs and level of service in the hierarchical network, we solve the proposed bi-objective model of Sect. 3.3 or Sect. 4 using the AUGMECON2 method for different values of parameter P (number of hubs) and get the Pareto frontier. Table 38 demonstrates the conflict between objectives using the Pareto solutions of test problem #3 with four hubs.
In Fig. 14, the graphical representation of the optimal solutions obtained by considering only the first objective, only the second objective, and Pareto-optimal solution #4 (Table 38) for test problem #3 with four hubs are shown. According to Fig. 14, if we optimize just the first objective, nodes 1, 7, and 16 are selected as airports, and other demand nodes are allocated to the central hub and airports in a way that transportation costs and fixed costs of links are minimized. If we optimize just the second objective, airports 7 and 16 and ground hub 5 are selected in order to minimize maximum travel time in the network. In this case, hubs have a central location, and we pay attention to the far demand points like 8 and 4. In bi-objective optimization, both criteria (minimizing costs and minimizing the maximum travel time) are considered, and the obtained solution is a combination of locations and allocations in two previous cases.
The results of sensitivity analysis of parameter P are shown in Fig. 15.
According to Fig. 15, by increasing the number of hubs, the costs of the hierarchical network and also the maximum travel time in the network (which is interpreted to the level of service) decrease. In addition, as demonstrated in Fig. 15, one can say that by increasing the number of hubs, the Pareto frontier is improved. However, the amount of improvement can be negligible when the number of hubs increases from five hubs. As the number of hubs increases from two hubs to four hubs, the number of Pareto solutions increases, which allows the decision-maker to reduce transportation costs as much as possible. Also, by increasing the number of hubs from two hubs to four hubs, the minimum value for the second objective function decreases, which means that a higher level of service is achieved to customers. But by increasing the number of hubs from four hubs to six hubs, the minimum value for the second objective function does not change, and therefore, the highest level of customer service does not increase.
To analyze the sensitivity of objective values concerning parameters for \(Emissions\) and \(Jobs\), we consider different values and solve the bi-objective model to get the Pareto-optimal solutions for test problems. Since each of these two parameters appears only in one constraint, the effect of changing their values can be seen in a limited number of points (only two or three values are reported for each test problem). The results of sensitivity analysis are reported in Tables 39, 40, and 41. In Table 39, the average objective function values of all obtained Pareto solutions are reported in columns 3 and 4. It can be observed that increasing the allowable level of emissions increases the costs of the hierarchical network and decreases the maximum travel time in the hierarchical network, which means an improvement in the level of service. This phenomenon can be described considering that by altering the feasible region, new Pareto solutions with a significantly greater value of the first objective can be obtained. Therefore, the average of the first objective values of the new Pareto solutions may worsen despite the expansion of the feasible region.
In Table 40, in all cases, by increasing the value of parameter \(Jobs\), the maximum travel time in the network increases, and the level of service decreases. Also, system costs decrease except in test problem #2.
In Table 41, in a specified level of allowable emissions, by increasing the parameter Jobs, in case Emissions = 7 × 1015, the maximum travel time and system costs remain constant. In the other cases, system costs decrease and the maximum travel time increases. Also, in case Jobs = 10,300, by increasing the allowable level of emissions, system costs increase, and the maximum travel time decreases.
Next, to examine the changes in the second objective function value relative to the discount factor for travel time, we optimize the second objective function for different values of the parameter α. The results are shown in Fig. 16. According to Fig. 16, as the value of α increases, a non-decreasing trend is observed in the curve. In two cases, as the value of α increases, there is no change in the second objective function value (from α = 0.4 to α = 0.5 and from α = 0.8 to α = 0.9). Between the values of α = 0.6 and α = 0.8, the objective value increases with a greater slope. It can be concluded that for increasing the level of service, the value of the parameter α should be reduced.
8 Conclusions and future research
In this paper, a mathematical model for the design and optimization of a sustainable hierarchical hub network was presented. The model considers two objective functions, the first of which seeks to minimize transportation costs and the costs of establishing links in the network. The second objective is dedicated to minimizing the maximum travel time in the network. Sustainability aspects (emissions and employment) and responsiveness (level of service) were considered in the model. This model can be applied in a freight or passenger transport network with two transport modes (air and ground), in which there are different levels of service (hierarchical), and customers are varied in choosing their desired services. Moreover, concerning the problem objectives, the maximum travel time is minimized in the second objective function, and as a result, the level of service increases.
For solving the model, the AUGMECON2 method was used. Tthe solution time of AUGMECON2 was increased exponentially by increasing the size of the problem. Therefore, two multi-objective genetic algorithms (NSGA-II and NRGA) were applied to solve more instances of the problem. Several criteria and statistical tests were applied to compare the efficiency of the two proposed metaheuristics. Experimental results demonstrated that NRGA can find solutions with the same quality as the NSGA-II in less solution time. Also, an alternative formulation for the problem was proposed, which was computationally more efficient than the initial formulation. With the help of this formulation, medium and large-sized problems that could not be solved with the initial formulation were solved by three exact multi-objective solution methods, including AUGMECON2, TH, and AWTP, and Pareto-optimal solutions were reported. In addition, the performance of the proposed solution methods was measured by some multi-objective indicators. The results showed the superiority of AUGMECON2 over the proposed solution methods.
For extending the model, other assumptions that exist in real world can be included in the model. In this model, capacity constraints for ground and airport hubs have not been considered. This is a limitation of the current model and can be considered in future research. Also, in the present study, air pollution has not been considered for the airplanes, which may be a fruitful search area. Furthermore, a similar model can be proposed for other variants of HLP such as the p-hub center location problem, hub covering location problem, and continuous HLP. In addition, other solution methods for reducing solution time in large scales of the problem can be developed by researchers.
References
Ahmad S, Utomo DS, Dadhich P, Greening P (2022) Packaging design, fill rate and road freight decarbonisation: a literature review and a future research agenda. Clean Logist Supply Chain 4:100066
Alumur SA, Kara BY, Karasan OE (2012a) Multimodal hub location and hub network design. Omega 40(6):927–939
Alumur SA, Yaman H, Kara BY (2012b) Hierarchical multimodal hub location problem with time-definite deliveries. Transp Res Part E Logist Transp Rev 48(6):1107–1120
Ambrosino D, Sciomachen A (2016) A capacitated hub location problem in freight logistics multimodal networks. Optim Lett 10(5):875–901
Arbabi H, Nasiri MM, Bozorgi-Amiri A (2021) A hub-and-spoke architecture for a parcel delivery system using the cross-docking distribution strategy. Eng Optim 53(9):1593–1612
Aykin T (1994) Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem. Eur J Oper Res 79(3):501–523
Aykin T (1995a) The hub location and routing problem. Eur J Oper Res 83(1):200–219
Aykin T (1995b) Networking policies for hub-and-spoke systems with application to the air transportation system. Transp Sci 29(3):201–221
Beasley JE (1990) OR-library: hub location. In: Vol. 2019
Bryan DL, O’kelly ME (1999) Hub-and-spoke networks in air transportation: an analytical review. J Reg Sci 39(2):275–295
Campbell JF (1994) Integer programming formulations of discrete hub location problems. Eur J Oper Res 72(2):387–405
Campbell JF (1996) Hub location and the p-hub median problem. Oper Res 44(6):923–935
Campbell AM, Lowe TJ, Zhang L (2007) The p-hub center allocation problem. Eur J Oper Res 176(2):819–835
Çelen A (2014) Comparative analysis of normalization procedures in TOPSIS method: with an application to Turkish deposit banking market. Informatica 25(2):185–208
da Graça Costa M, Captivo ME, Clímaco J (2008) Capacitated single allocation hub location problem: a bi-criteria approach. Comput Oper Res 35(11):3671–3695
Davari S, Zarandi MF, Turksen I (2013) The incomplete hub-covering location problem considering imprecise location of demands. Sci Iran 20(3):983–991
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Dukkanci O, Kara BY (2017) Routing and scheduling decisions in the hierarchical hub location problem. Comput Oper Res 85:45–57
Ernst AT, Hamacher H, Jiang H, Krishnamoorthy M, Woeginger G (2009) Uncapacitated single and multiple allocation p-hub center problems. Comput Oper Res 36(7):2230–2241
European_Commission. (2015) EU energy and transport in figures 2015. In: Publications Office of the European Union Luxembourg.
Farahani RZ, Hekmatfar M, Arabani AB, Nikbakhsh E (2013) Hub location problems: a review of models, classification, solution techniques, and applications. Comput Ind Eng 64(4):1096–1109
Ghezavati V, Hosseinifar P (2018) Application of efficient metaheuristics to solve a new bi-objective optimization model for hub facility location problem considering value at risk criterion. Soft Comput 22(1):195–212
Ghodratnama A, Tavakkoli-Moghaddam R, Azaron A (2015a) Robust and fuzzy goal programming optimization approaches for a novel multi-objective hub location-allocation problem: a supply chain overview. Appl Soft Comput 37:255–276
Ghodratnama A, Tavakkoli-Moghaddam R, Kalami-Heris SM, Nagy G (2015b) Solving a novel multi-objective uncapacitated hub location problem by five meta-heuristics. J Intell Fuzzy Syst 28:2457–2469
Goldman A (1969) Optimal locations for centers in a network. Transp Sci 3(4):352–360
Govindan K (2022a) How artificial intelligence drives sustainable frugal innovation: A multitheoretical perspective. IEEE Trans Eng Manag 2022:1–18
Govindan K (2022) Theory Building Through Corporate Social Responsibility 4.0 for Achieving SDGs: A Practical Step Toward Integration of Digitalization With Practice-Based View and Social Good Theory. IEEE Trans Eng Manag 2022:1–18
Gupta VK, Ting QU, Tiwari MK (2019) Multi-period price optimization problem for omnichannel retailers accounting for customer heterogeneity. Int J Prod Econ 212:155–167
Hakimi SL (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper Res 12(3):450–459
Kannan D (2021) Sustainable procurement drivers for extended multi-tier context: A multi-theoretical perspective in the Danish supply chain. Transp Res Part E Logist Transp Rev 146:102092
Kannan D, Solanki R, Kaul A, Jha PC (2022) Barrier analysis for carbon regulatory environmental policies implementation in manufacturing supply chains to achieve zero carbon. J Clean Prod 358:131910
Kara BY, Tansel BC (2000) On the single-assignment p-hub center problem. Eur J Oper Res 125(3):648–655
Karimi H, Bashiri M (2011) Hub covering location problems with different coverage types. Sci Iran 18(6):1571–1578
Karimi M, Eydi A, Korani E (2014) Modeling of the capacitated single allocation hub location problem with a hierarchical approch. Int J Eng 27(4):573–586
Karimi B, Bashiri M, Nikzad E (2018) Multi-commodity multimodal splittable logistics hub location problem with stochastic demands. Int J Eng 31(11):1935–1942
Karthick B, Uthayakumar R (2022) Impact of carbon emission reduction on supply chain model with manufacturing decisions and dynamic lead time under uncertain demand. Clean Logist Supply Chain 4:100037
Klincewicz JG (1991) Heuristics for the p-hub location problem. Eur J Oper Res 53(1):25–37
Klincewicz JG (1992) Avoiding local optima in thep-hub location problem using tabu search and GRASP. Ann Oper Res 40(1):283–302
Köksalan M, Soylu B (2010) Bicriteria p-hub location problems and evolutionary algorithms. INFORMS J Comput 22(4):528–542
Korani E, Eydi A, Nakhai Kamalabadi I (2020) Reliable hierarchical multimodal hub location problem: models and Lagrangian relaxation algorithm. Sci Iran 27(3):1525–1543
Lin C-C (2010) The integrated secondary route network design model in the hierarchical hub-and-spoke network for dual express services. Int J Prod Econ 123(1):20–30
Ma Y, Shi X, Qiu Y (2020) Hierarchical multimodal hub location with time restriction for China Railway (CR) Express network. IEEE Access 8:61395–61404
Maiyar LM, Thakkar JJ (2018). Modelling and analysis of intermodal food grain transportation under hub disruption towards sustainability. Int J Prod Econ
Mavrotas G (2009) Effective implementation of the ε-constraint method in multi-objective mathematical programming problems. Appl Math Comput 213(2):455–465
Mavrotas G, Florios K (2013) An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems. Appl Math Comput 219(18):9652–9669
Mohammadi M, Jolai F, Tavakkoli-Moghaddam R (2013) Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm. Appl Math Model 37(24):10053–10073
Mohammadi M, Torabi SA, Tavakkoli-Moghaddam R (2014) Sustainable hub location under mixed uncertainty. Transp Res Part E Logist Transp Rev 62:89–115
Musavi M, Bozorgi-Amiri A (2017) A multi-objective sustainable hub location-scheduling problem for perishable food supply chain. Comput Ind Eng 113:766–778
Nasiri MM, Abdollahi M, Rahbari A, Salmanzadeh N, Meydani SS (2018a) Minimizing the energy consumption and the total weighted tardiness for the flexible flowshop using NSGA-II and NRGA. J Ind Syst Eng 11:150–162
Nasiri MM, Shahmoradi-Moghadam H, Torabi SA (2018b) A hub covering flow network design resilient to major disruptions and supply/demand uncertainties. Int J Bus Contin Risk Manag 8(4):319–334
Niakan F, Vahdani B, Mohammadi M (2015) A multi-objective optimization model for hub network design under uncertainty: an inexact rough-interval fuzzy approach. Eng Optim 47(12):1670–1688
Niknamfar AH, Niaki STA (2016) Fair profit contract for a carrier collaboration framework in a green hub network under soft time-windows: dual lexicographic max–min approach. Transp Res Part E Logist Transp Rev 91:129–151
O’kelly, M.E. (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 32(3):393–404
Rajabi Z, Avakh Darestani S (2015) Optimizing a hierarchical hub covering problem with mandatory dispersion of central hubs. Int J Appl Oper Res 5(1):17–28
Roni MS, Eksioglu SD, Cafferty KG, Jacobson JJ (2017) A multi-objective, hub-and-spoke model to design and manage biofuel supply chains. Ann Oper Res 249(1–2):351–380
Sedehzadeh S, Tavakkoli-Moghaddam R, Mohammadi M, Jolai F (2014) Solving a new priority m/m/c queue model for a multimode hub covering location problem by multi-objective parallel simulated annealing. Econ Comput Econ Cybern Stud Res, 48(4).
Shang X, Yang K, Wang W, Wang W, Zhang H, Celic S (2020) Stochastic hierarchical multimodal hub location problem for cargo delivery systems: formulation and algorithm. IEEE Access 8:55076–55090
Shang X, Yang K, Jia B, Gao Z, Ji H (2021) Heuristic algorithms for the bi-objective hierarchical multimodal hub location problem in cargo delivery systems. Appl Math Model 91:412–437
Sharma R, Kannan D, Darbari JD, Jha PC (2022) Analysis of collaborative sustainable practices in multi-tier food supply chain using integrated TISM-Fuzzy MICMAC model: a supply chain practice view. J Clean Prod 354:131271
Skorin-Kapov D, Skorin-Kapov J, O’Kelly M (1996) Tight linear programming relaxations of uncapacitated p-hub median problems. Eur J Oper Res 94(3):582–593
Steuer RE, Choo EU (1983) An interactive weighted Tchebycheff procedure for multiple objective programming. Math Program 26(3):326–344
Tan PZ, Kara BY (2007) A hub covering model for cargo delivery systems. Netw Int J 49(1):28–39
Torabi SA, Hassini E (2008) An interactive possibilistic programming approach for multiple objective supply chain master planning. Fuzzy Sets Syst 159(2):193–214
Wasner M, Zäpfel G (2004) An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. Int J Prod Econ 90(3):403–419
Xu X, Zhang Q, Wang W, Peng Y, Song X, Jiang Y (2018) Modelling port competition for intermodal network design with environmental concerns. J Clean Prod 202:720–735
Yaman H (2009) The hierarchical hub median problem with single assignment. Transp Res Part B Methodol 43(6):643–658
Yaman H, Elloumi S (2012) Star p-hub center problem and star p-hub median problem with bounded path lengths. Comput Oper Res 39(11):2725–2732
Zarbakhshnia N, Govindan K, Kannan D, Goh M (2022) Outsourcing logistics operations in circular economy towards to sustainable development goals. Bus Strategy Environ
Zhalechian M, Tavakkoli-Moghaddam R, Rahimi Y (2017a) A self-adaptive evolutionary algorithm for a fuzzy multi-objective hub location problem: an integration of responsiveness and social responsibility. Eng Appl Artif Intell 62:1–16
Zhalechian M, Tavakkoli-Moghaddam R, Rahimi Y, Jolai F (2017b) An interactive possibilistic programming approach for a multi-objective hub location problem: economic and environmental design. Appl Soft Comput 52:699–713
Zhong W, Juan Z, Zong F, Su H (2018) Hierarchical hub location model and hybrid algorithm for integration of urban and rural public transport. Int J Distrib Sens Netw 14(4):1550147718773263
Acknowledgements
The authors are grateful for the comments provided by the anonymous reviewers on an earlier version of this study. These comments greatly helped improve the study.
Funding
Open access funding provided by Royal Danish Library. There is no funding for this research work.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A
The AUGMECON2 method.
For explaining the AUGMECON2 method, suppose a problem that has \(p\) objective functions. The general form of multi-objective optimization using AUGMECON2 is as follows:
In Eq. (60), \({e}_{2},...,{e}_{p}\) are the RHS values for the specific iteration based on grid points of objective functions \(2,...,p\). epsilon is a constant value between 10–6 and 10–3. \({r}_{2},...,{r}_{p}\) are the ranges of objective functions \(2,...,p\). The range of each objective function is the difference between the best and worst value of that objective function in the payoff table. \(F\) is the feasible region of the problem, and \({S}_{2},...,{S}_{p}\) are slack variables for the respective constraints. Then, the range of objective function \(k\) is divided into \({g}_{k}\) equal intervals using \(({g}_{k}-1)\) intermediate grid points. Thus, in total, \(({g}_{k}+1)\) grid points can be used to vary the RHS of constraint \(k\) (i.e. \({e}_{k}\)). The total number of runs is \(\left({g}_{2}+1\right)\times ... \times ({g}_{p}+1)\). The discretization step is calculated as Eq. (61).
Then, the RHS of the corresponding constraint in iteration \(t\) for objective function \(k\) is as Eq. (62).
In which, \({\mathrm{fmin}}_{k}\) is the minimum value of objective function \(k\) in the payoff table.
The slack variable of the innermost objective function is checked at each iteration (in our case, objective function 2). Then, the bypass coefficient is calculated as Eq. (63).
In which function \(\mathrm{int}()\) returns the integer part of a real number. If \({S}_{2}>ste{p}_{2}\), the same solution is obtained in the next iteration with a smaller slack variable whose value is \(({S}_{2}-ste{p}_{2})\). Thus, the next iteration is redundant, and we can bypass it. The bypass coefficient indicates how many consecutive iterations can be bypassed. The flowchart of the AUGMECON2 method is shown in Fig.
17.
Appendix B
The TH method.
To use the TH method, we need to determine Positive Ideal Solution (PIS), i.e., \(\left({Obj}_{1}^{\mathrm{PIS}},{x}_{1}^{\mathrm{PIS}}\right), \left({Obj}_{2}^{\mathrm{PIS}},{x}_{2}^{\mathrm{PIS}}\right)\), and Negative Ideal Solution (NIS) for each objective function. To obtain the PIS, each objective function must be optimized separately under the problem constraints. Also, NIS for each objective function can be estimated using Eq. (64).
The satisfaction degrees for the first and second objective function are calculated as Eqs. (65) and (66), respectively.
Then, using the aggregation function of the TH method, the bi-objective problem is converted into a single-objective parametric problem as Eqs. (67)–(69).
In this formulation, parameter \(\psi \in [\mathrm{0,1}]\) is the coefficient of compensation, and parameter \({\pi }_{f}\in [\mathrm{0,1}]\) denotes the importance of objective function \(f\). Also, \(F\) is feasible region. Note that \(\sum_{f=1}^{2}{\pi }_{f}=1, {\pi }_{f}>0\). Equation (67) looks for a compromise value between the minimum and weighted sum operators. By setting the parameters \(\psi\) and \({\pi }_{f}\) at different levels, the TH method finds efficient Pareto solutions.
Appendix C
The AWTP method.
To illustrate this method, consider the general form of a multi-objective optimization problem with \(q\) decision variables and \(\kappa\) objective function as follows:
In Eq. (70), \(x\) is a solution to the problem and \(X\) represents the set of feasible solutions. The objective function vector \(F(x)\) maps a decision vector \(x=({x}_{1}, {x}_{2},\dots , {x}_{q})\) in the decision space (\(X\)) to an objective vector \(z=({z}_{1}, {z}_{2},\dots , {z}_{\kappa })\) in the objective space (\(Z\)). In the AWTP, the following single-objective problem should be solved to get Pareto-optimal solutions.
In Eq. (71), \({\lambda }_{t}\) represents the weight of objective function \(t\), which is determined by the decision-maker. Parameter \({r}_{t}^{*}\) represents the best possible value for the objective function \(t\). Also, \(\nu\) is a parameter that is usually considered between 0.01 and 0.001. In this study, it is set at 0.005. This method can find efficient Pareto solutions to the problem. Note that in this study to scale objective functions, each objective function is divided into its range (difference between the best and worst values of the objective function).
Appendix D
Characteristics of the case study problem.
See Tables
42,
43, and
44.
Appendix E
Test problems dataset.
See Tables
45 and
46.
Appendix F
S/N ratios for the proposed metaheuristic algorithms’ parameter setting.
See Figs.
18 and
19.
Appendix G
Test instances on three datasets.
See Table
47.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Nasiri, M.M., Khaleghi, A., Govindan, K. et al. Sustainable hierarchical multi-modal hub network design problem: bi-objective formulations and solution algorithms. Oper Res Int J 23, 35 (2023). https://doi.org/10.1007/s12351-023-00767-9
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s12351-023-00767-9