Hierarchical hub location model and hybrid algorithm for integration of urban and rural public transport

Abstract

Integration of urban and rural infrastructure is critical to integrating urban and rural public transport. A public transport hub is an important element of infrastructure, and it is the key facilities that serve as transferring points between cities and towns. The location of hub is related to the convenience of travel for urban and rural residents and the closeness of economic interactions between urban and rural areas. In this article, considering the background of the integration of urban and rural public transport, from the perspective of public transport hubs in urban and central town, a multi-level hub-and-spoke network is designed, and the location of integration of urban and rural public transport hub is determined. Based on the connection associated with central towns and the capacity constraints of hubs and to achieve the minimum total cost, this article proposes a mixed-integer programming model that employs a genetic and tabu search hybrid optimization algorithm to validate and analyze, which used the urban and rural public transport data from a specified area of Shandong province in China. The results indicate that the model can simultaneously determine locations for hubs in cities and central towns while minimizing total cost. The hub capacity constraint significantly influences the location of two-level hubs. The hub capacity constraint in the model can reduce the transportation cost for an entire network and optimize the transportation network. This study on urban and rural public transport hub location in a hub-and-spoke network not only reduces the transportation cost of the network but also completes and supplements the location theory of integration of urban and rural public transport.

Keywords

Hub-and-spoke network integration of urban and rural public transport hub location hierarchical capacitated genetic algorithm tabu search algorithm

Introduction

The integration of urban and rural passenger transport is critical to integration of urban and rural areas. The main mode is the integration of urban and rural public transport. Its major task is to satisfy urban and rural residents’ ever-increasing travel demand, particularly to enable the residents of cities, villages, and towns to conveniently travel to and from destinations at low cost. However, the residents of villages and towns are scattered and travel less frequently than their urban counterparts. Satisfying residents’ travel demands by directly connecting all villages and towns with a city would increase costs and waste resources. A hub-and-spoke network employs indirect links between nodes, which concentrates travelers at a central node and then convey them to their respective destinations.¹ This approach reduces costs while improving efficiency of the network by taking advantage of economies of scale. A hub-and-spoke network includes two types of nodes: hub nodes and non-hub nodes. A hub location determines the distribution of hubs and the assignment of non-hub nodes.

Numerous studies of hub location in a hub-and-spoke network have been conducted. O’Kelly² presented the first mathematical formulation to solve the single allocation p-hub median problem. He investigated an American Airlines passenger network and established the first quadratic integer programming for single allocation p-hub median problem. Researchers have primarily investigated four models and algorithms: p-hub median problem, hub location problem with fixed costs, p-hub center problem, and hub covering problem.³ They discussed allocation and capacity constraints. However, the majority of studies addressed the problem of capacity constraints in single-layer networks; few studies explored capacity constraints in multi-level networks.

An urban and rural public transport network contains two types of hubs: urban public transport hubs and hubs in central towns.⁴ Hubs in central towns primarily serve passengers in general towns and administrative villages, whereas urban public transport hubs serve passengers in cities and central towns. Thus, urban public transport hubs, hubs in central towns, and demand nodes constitute a three-level urban and rural public transport network. The hub location in the network is a multi-level location problem. Existing researches on the integration of urban and rural public transport have primarily focused on urban public transport hubs and hubs in central towns, respectively, using different methods. For example, the hub location models for city environments considering different optimization goal were proposed in these studies.^5–8 Wang⁵ built a hub covering location model for hubs in central towns. This layout failed to consider urban and rural public transport terminal as a whole and was unable to guarantee optimal transportation cost.

Existing researches on multi-level hub location primarily focus on facility hierarchical locations, such as production-distribution systems;⁹ express delivery services systems;¹⁰ hospitals, schools, and other public service facilities;^11,12 solid waste management systems;¹³ and city emergency facilities.¹⁴ The majority of studies take the standpoint of management features and do not consider the use of a hub-and-spoke network structure. Only a few papers on hub location in a hierarchical hub-and-spoke network have considered transportation. One study was based on an application in cargo delivery. A previous survey of a major cargo company in Turkey by Elmastas¹⁵ discovered that the company used a three-level transport network, where two central hubs are directly connected, the remaining hubs are connected to one of these two central hubs, and each remaining demand node is connected to a hub or a central hub. Based on the network, Elmastas established a hierarchical hub location model that considers time constraints and compared it with an actual situation. The results show that the constructed model has fewer hubs with the lowest total transportation cost. Based on this research, Yaman¹⁶ developed a complete-star-star network and proposed a hierarchical single allocation hub location without capacity constraints. Alumur et al.¹⁷ considered the hierarchical hub location problem in multimodal transportation. Davari and Zarandi¹⁸ considered the uncertainty demand and introduced fuzzy variables into the model based on the model proposed by Yaman. Karimi et al.¹⁹ considered hub capacity and time constraints and presented the capacitated single allocation hierarchical hub median location model. Dükkanci et al.²⁰ defined a ring-star-star hierarchical network and combined location with route and schedule to construct a hub covering model. Zheng et al.²¹ studied the location of regional and international hub ports in liner shipping by proposing a hierarchical hub location problem. Li et al.²² proposed a hierarchical hub location model for a hub-and-spoke network that was primarily aimed at urban comprehensive passenger hub in China. These studies, however, considered the network structure from perspective of carriage of goods, which is not completely aligned with the characteristics of urban and rural public transport. Moreover, level II hubs are not allowed to connect in the literatures, and few studies have considered the capacity limitations for hubs and paths. In reality, central towns can be connected in an urban and rural public transport network, and factors such as capital, land, traffic distribution, and capacity limitations for hubs and paths require consideration. This article’s emphasis on capacity constraints will align well with real-world situation.

To remedy the previously mentioned deficiencies, this article seeks to improve three aspects of existing research:

The article will consider urban and rural public transport terminals as a whole, build a multi-level hub-and-spoke network, and simultaneously locate urban public transport hubs and hubs in central town.

According to the characteristics of urban and rural public transport, passengers travel from demand nodes to a hub in a central town and then travel to urban public transport hubs. This article will build a star-complete-complete network structure. However, considering real-world situation, if two hubs in central towns connect to the same urban public transport hub, then the connection between them will be allowed, as indicated in Figure 1.

Reflecting real-world situations, this article will simultaneously consider urban public transport hubs and hubs in central towns with capacity constraints while establishing a capacitated hierarchical location model.

Figure1.

Urban and rural public transport hub network with three level I hubs, six level II hubs.

Applying the background of the integration of urban and rural public transport, considering a hub-and-spoke network that considers connections of central towns and hub capacity constraints, this article proposes a hierarchical location model that employs a genetic and tabu search hybrid optimization algorithm to validate using real data. The remainder of this article is organized as follows. In section “Description of hub location for the integration of urban and rural public transport,” the problem is described. The model is constructed in section “Construction of hub location model,” and a solution approach is designed in section “Solution method.” Section “Computational result and analysis” presents the computational results and parameters analysis. The conclusions are discussed in section “Conclusion.”

Description of hub location for the integration of urban and rural public transport

The integration of urban and rural public transport does not cover the complete range of urban and rural areas but rather is confined to a certain administrative area, which is defined in this article as a specific area of a city and its neighboring townships.⁷ In this region, urban and rural public transport primarily aims to satisfy the growing travel demand generated by urban and rural residents, especially to satisfy the residents who moving into and out of city. Figure 1 displays a network of urban and rural public transport. Urban public transport hubs are known as the level I hub, which is located in the city or on the rural–urban continuum. Hubs in central towns are known as the level II hub. Level I hubs may be connected, and connections can be formed between level II hubs that connect to the same level I hub. Other demand nodes, however, are not allowed to connect.

The urban area and town are divided into numerous traffic districts, each of which can be considered as a demand node or destination that constitutes a set of urban and rural network nodes. The problem to be solved is to determine the number and location of level I hubs and level II hubs and assign demand nodes to the hub and assign level II hubs to level I hubs while minimizing total cost.

The following assumptions for the model are formed:

Each demand node only connects to one hub.

Direct connections between non-hub nodes are not allowed.

The unit transportation cost between level I hubs, level II hubs, level II hubs and level I hubs is lower than the unit transportation cost between two demand nodes. Moreover, the unit transportation cost between two level II hubs, level II hubs, and level I hubs is equal, as expressed by the discount factor $α_{2}$ , whereas the unit transportation cost between two level I hubs is represented by the discount factor $α_{1}$ , $0 < α_{1}, α_{2} \leq 1$ , which has been analyzed in literatures^23,24 in detail.

An alternative node can only place one hub.

Construction of hub location model

In this section, the article proposes a mixed-integer programming model that aims to minimize the sum of transportation costs and hub construction costs. The transportation costs include the assignment costs of non-hub nodes and transportation costs among the hubs. The hub construction cost is considered because the number of hubs is determined by the model. To calculate the traffic on the path, the article refers to the idea of multi-commodity flow proposed by Ernst and Krishnamoorthy²⁴ and Ebery²⁵ and employs three index variables to represent the traffic. The article assumes that the path cost of the network satisfies the triangular inequality.

Parameters and variables

To illustrate the problem, parameters and variables are defined as follows.

$I$ is the set of demand nodes; $P \subseteq I$ is the set of possible locations for level I hub; $Q \subseteq I$ , $Q \cap P = \emptyset$ is the set of possible locations for level II hub; $H$ is the set of possible locations for level I hub and level II hub, and $Q \cup P = H$ .

$w_{ij}$ is the amount of traffic from node $i \in I$ to node $j \in I$ . $f_{kl}^{i}$ is the amount of traffic from level I hub. $k \in P$ to level I hub $l \in P \ {k}$ which originates at $i \in I$ . $g_{mk}^{i}$ is the amount of traffic from level II hub $m \in Q$ to level I hub. $k \in P$ which originates or terminates at $i \in I$ . $h_{mn}^{i}$ is the amount of traffic from level II hub $m \in Q$ to level II hub. $n \in Q \ {m}$ which are assigned to the same level I hub, and the level II hub originates or terminates at $i \in I$ . $c_{ij}$ is the unit transportation cost from node $i \in I$ to node $j \in I \ {i}$ , $c_{ij} = c_{ji}$ .

$x_{im}$ is equal to 1 if the node $i \in I$ is assigned to the hub $m \in H$ and 0 otherwise; if node $m \in H$ is a hub, then $x_{mm}$ is equal to 1. $y_{mk}$ is equal to 1 if the hub $m \in H$ is assigned to level I hub $k \in P$ and 0 otherwise; if node $k \in P$ is a hub, then $y_{kk}$ is equal to 1. $z_{mn}^{k}$ is equal to 1 if there is a connection between $m \in H$ and $n \in H \ {m}$ when they are assigned to the same level I hub $k \in P$ and 0 otherwise.

$F_{1}$ is construction cost of level I hub, $F_{2}$ is construction cost of level II hub, $M_{1}$ is maximum capacity of level I hub, and $M_{2}$ is maximum capacity of level II hub.

Mathematical formulation

According to the above description of the problem, the related hypothesis and the definition of parameters and variables, based on literatures,^16,22 and considering the hub capacity constraints, the following mathematical model is established

\begin{matrix} \min \sum_{i \in I} \sum_{s \in I} (w_{is} + w_{si}) \sum_{m \in H} c_{im} x_{im} \\ + \sum_{i \in I} \sum_{k \in P} \sum_{l \in P \ {k}} α_{1} c_{kl} f_{kl}^{i} + \sum_{i \in I} \sum_{m \in H} \sum_{n \in H \ {m}} α_{2} c_{mn} h_{mn}^{i} \\ + \sum_{k \in P} F_{1} y_{kk} + \sum_{x \in Q} F_{2} x_{mm} \end{matrix}

(1)

s . t .

\sum_{j \in H} x_{ij} = 1 \forall i \in I

(2)

x_{kk} = y_{kk} \forall k \in P

(3)

x_{im} \leq x_{mm} \forall i \in I, m \in H

(4)

\sum_{k \in P} y_{mk} = x_{mm} \forall m \in H

(5)

y_{mk} \leq y_{kk} \forall m \in H, k \in P

(6)

\begin{matrix} z_{mn}^{k} \geq y_{mk} + y_{nk} - 1 \forall m \in H, \\ n \in H \ {m}, k \in P, k \neq m, k \neq n \end{matrix}

(7)

\begin{matrix} z_{mn}^{k} \leq y_{mk} - y_{nk} + 1 \forall m \in H, n \in H \ {m}, \\ k \in P, k \neq m, k \neq n \end{matrix}

(8)

\begin{matrix} z_{mn}^{k} = z_{nm}^{k} \forall m \in H, n \in H \ {m}, \\ k \in P, k \neq m, k \neq n \end{matrix}

(9)

z_{mk}^{k} \geq y_{mk} \forall m \in H, k \in P \ {m}

(10)

z_{mk}^{k} \leq x_{kk} \forall m \in H, k \in P \ {m}

(11)

z_{mk}^{k} \leq x_{mm} \forall m \in H, k \in P \ {m}

(12)

\sum_{n \in H \ {m}} h_{mn}^{i} - \sum_{n \in H \ {m}} h_{nm}^{i} = \sum_{s \in I} w_{is} (x_{im} - x_{sm}) \forall i \in I, m \in Q

(13)

\begin{matrix} \sum_{l \in H \ {j}} g_{jl}^{i} + \sum_{k \in P \ {j}} f_{jk}^{i} - \sum_{k \in P \ {j}} f_{kj}^{i} - \sum_{l \in H \ {j}} g_{lj}^{i} \\ = \sum_{s \in I} w_{is} (x_{ij} - x_{sj}) \forall i \in I, j \in P \end{matrix}

(14)

h_{jl}^{i} \leq z_{jl}^{k} \sum_{s \in I} w_{is} \forall i \in I, j \in H, l \in H \ {j}, k \in P

(15)

\sum_{i \in I} \sum_{j \in I} w_{ij} x_{im} \leq M_{2} x_{mm} \forall m \in Q

(16)

\sum_{i \in I} \sum_{m \in Q} h_{mn}^{i} + \sum_{i \in I} \sum_{j \in I} w_{ij} x_{in} \leq M_{1} y_{nn} \forall n \in P

(17)

h_{mn}^{i} \geq 0 \forall i \in I, m \in H, n \in H \ {m}

(18)

g_{mk}^{i} \geq 0 \forall i \in I, m \in H, k \in P

(19)

f_{kl}^{i} \geq 0 \forall i \in I, k \in P, l \in P \ {k}

(20)

x_{im}, y_{mk}, z_{mn}^{k} \in {0, 1} \forall i \in I, m \in H, k \in P, n \in H \ {m}

(21)

The objective function (1) indicates the minimum total costs that conclude transportation costs and hub construction costs. The first term is the assignment costs, the second is the transportation costs among the level I hubs, the third is the transportation costs among the level II hubs and costs between the level II hubs and level I hubs, the fourth and the fifth are construction costs of level I hubs and level II hubs, respectively. Constraint (2) ensures that the demand nodes are assigned only to one hub; and constraint (3) ensures that the level II hubs cannot be selected from the set of level I hubs. Constraint (4) ensures that the nodes must be assigned to the hub. Constraints (5) and (6) ensure that a level II hub is assigned only to one level I hub, which must serve as the hub. According to constraints (7)–(9), if the level II hub m and n are assigned to the same level I hub k, a connection exists between m and n. If m and n are not assigned to the same level I hub k, a connection between m and n does not exist. Constraints (10)–(12) indicate that m and n are selected as hubs. If the level II hub m is assigned to level I hub n, then the connection between m and n is the connection between the level II hubs. Constraint (13) represents the flow balance among level II hubs. Constraint (14) represents the flow balance among level I hubs. According to constraint (15) if a connection does not exist between the hub j and the hub l, the amount of traffic between j and l is 0. Constraints (16) and (17) are the capacity constraints of the level II hub and the level I hub, respectively. Constraints (18)–(20) are non-negativity restrictions on the amount of traffic, and constraint (21) is a 0–1 integer constraint. The model is 0–1 mixed-integer programming model, which has proved to be an NP hard problem in the literature.¹⁶

Solution method

Scholars have proposed many exact and intelligent optimization algorithms about hub location in a hub-and-spoke network³ and have demonstrated the effectiveness and superiority of intelligent optimization algorithms for solving the hub location problem. The genetic algorithm is an intelligent optimization algorithm that mimics natural selection, genetic biology, and evolution, and it is extensively employed for addressing location and allocation. For example, Lin et al.²⁶ employed genetic algorithm to solve the p-hub median problem with capacity constraints. Topcuoglu et al.²⁷ adopted genetic algorithm to determine the number of hubs, location, and the allocation of non-hub nodes. Kratica et al.²⁸ applied genetic algorithm to solve the uncapacitated hub median location problem. However, the genetic algorithm can easily fall into the local optimal solution, the simple genetic algorithm cannot successfully solve many complex problems, and allocation is not necessarily the optimal solution.²⁹ Therefore, scholars often combine other algorithms with genetic algorithms and employ combinatorial optimization algorithm to solve the hub location problem in the hub-and-spoke network. For instance, Cunha and Silva³⁰ embedded simulated annealing algorithm into genetic algorithm to solve the single allocation hub location problem. Abdinnour-Helm²⁹ combined genetic algorithm and tabu search algorithm to solve the single allocation hub location problem. Skorin-Kapov et al.³¹ proved that the tabu search algorithm can achieve optimal results, and it is better than simulated annealing algorithm for solving the problem. For the mixed-integer programming model established in the article, when the number of level II hubs is 0, the multi-level hub location problem becomes a classic single-layer median hub location problem. Abdinnour-Helm²⁹ has proved the effectiveness and superiority of the method; thus, this article applies the genetic and tabu search hybrid optimization algorithm to solve the model. The solution includes two stages: determining location by genetic algorithm to obtain an initial solution and solving the optimal assignment problem using the tabu search algorithm.

Solution representation

In genetic algorithm, a solution includes two arrays: HubArray and AssignArray. HubArray is expressed in 0s and 1s, where 0 indicates a non-hub node and 1 indicates a hub. AssignArray is expressed in real numbers; the value of the corresponding position in the array represents the serial number of a non-hub node that is assigned to a level II hub or a level I hub. The level I hub is the node that is located to itself. The length of the two arrays equals the number of nodes in the network k. The solution representation of Figure 1 is shown in Figure 2.

Figure 2.

The representation of solution.

Steps of genetic and tabu search hybrid optimization algorithm

Initial parameters including population of solution $N$ , selection probability $P_{c}$ , and mutation probabilities $P_{m 1}$ and $P_{m 2}$ are given (Table 1).

Generate initial population. A set of initial solution is generated based on the given fixed probability $p = 0.15$ that each node becomes a hub.

Calculate the fitness function. Calculate the fitness function value of each individual considering the objective function as a fitness function.

Select two parent solutions for reproduction. Use the binary tournament selection method due to its fewer iterations and greater speed.³⁰ Randomly choose two individuals from the population each time and save the individual with the smaller fitness value in the next generation. Because each binary tournament selection produces one parent, the article holds two binary tournament selections to perform the following operation.

Produce offspring by recombination. This step includes two parts: crossover operation and mutation operation.

Apply one point crossover operator and randomly select one crossover point for HubArray and AssignArray. The selected crossover point is the same. Then, offspring are generated by exchanging genes behind the crossover point in the parents. After exchanging, if two offspring are both hubs and non-hubs, they are dropped and a crossover point is generated once more. For the AssignArray, if a node is assigned to one node that is not a hub after exchanging, then the node is randomly reassigned to a selected hub.

Mutation is performed as follows: For HubArray, randomly select a hub node and a non-hub node and exchange the gene value for the corresponding positions: 0–1 and 1–0. For AssignArray, choose a non-hub node and reassign it to another randomly selected hub.

Apply a tabu search algorithm to each generated individual to improve the initial assignment process.

Replace an individual in the initial population using the new offspring solution obtained through this process, then evaluate the new population. Use an elitist generation replacement and replace the individual with the greatest fitness value by offspring solution.

Repeat steps 4–7 until a pre-defined number of iterations is attained.

Table 1.

Parameters for genetic and tabu search hybrid algorithm.

Parameter	Meaning
$N$	Population of solution
$P_{c}$	Selection probability
$P_{m 1}$ , $P_{m 2}$	Mutation probabilities
$\sqrt{n}$	tabu_size
$P_{s}$	Shift probability

Tabu search optimization component

The article improves the allocation of non-hub node to hub with tabu search algorithm, which finds the optimal allocation within a neighborhood. The allocation does not change the location of hubs. Find the optimal allocation by movement, which includes two types: shift moves and exchange moves. Shift moves switch the assignment of a non-hub from one hub to another hub. Exchange moves involve a pair of non-hubs, which randomly selects two non-hub nodes and switches their assignments. The process is described as follows:

Set the move process as tabu object. Keep two separate tabu lists: one is tabu_list_shift for shift moves and the other one is tabu_list_exchange for exchange moves. The initial value is set 0. Tabu_size is set $\sqrt{n}$ , where n is the number of nodes.

Assess the termination conditions of tabu search algorithm. If the conditions are satisfied, tabu search is terminated, and return to step 8 above, or continue the following steps.

When shift probability $P_{s}$ is set to 1, all shift moves are performed in the neighborhood search, and the shift move that minimizes the objective function is the optimal solution. When shift probability is set to 0, all exchange moves are performed in the neighborhood search, and the exchange move that minimizes the objective function is the optimal solution. When shift probability is set to a number between 0 and 1, and a random number $r$ is generated. If $r$ is less than or equal to shift probability, shift moves are performed. If the solution is not the optimal solution, however, exchange moves are performed, and the minimum of the best shift move and the best exchange move is the optimal solution. Otherwise, if $r$ is greater than shift probability, exchange moves are performed, and then shift moves are performed. The minimum of the best shift move and the best exchange move is considered the optimal solution.

Designate the optimal solution as the current solution and determine whether the current solution satisfies the despised criterion. If the despised criterion is satisfied, update despised criterion and the current solution, or continue the following steps.

Update the tabu list.

Return step 2.

Computational result and analysis

The model is computed and analyzed with a set of urban and rural public transport survey data from Guangrao County in Shandong province, China, in 2013. The research area is shown in Figure 3. Guangrao County has a total area of 1167.55 km², which administers six towns, one township, two streets, and one economic development zone. According to the basis of traffic district division, Guangrao County is divided into 54 districts, and residents’ public transport trips are surveyed by a sampling survey to obtain the data of public transport trips. The article uses the distance between the centroid of traffic districts instead of the distance between two districts. To analyze the influence of some parameters on the total cost and hub location, considering the balanced distribution, this article, respectively, chooses 15, 20, 25, and 30 traffic districts with more flow volume as demand points (represented by circles). Some districts are chosen as a possible set of level I hubs (depicted by triangles) and some districts are chosen as a possible set of level II hubs (represented by squares). The distances and traffic volumes among districts are listed in Tables 2 and 3. The article assumes that the unit transportation cost is 0.2 yuan per passenger-kilometer. Based on planning, the maximum capacity of a level I hub ranges from 5000 to 10,000 and the maximum capacity of a level II hub ranges from 2000 to 5000. The planned construction cost of a level I hub is 3,000,000, and the planned construction cost of a level II hub is 1,500,000.

Figure 3.

The map for the 30 node instance.

Table 2.

Traffic volumes between demand nodes.

	1	3	6	8	10	11	12	17	18	22	23	24	25	27	28	30	33	35	37	38	39	40	41	44	45	47	48	51	52	54
1	110	46	263	28	114	0	94	0	23	28	65	10	0	0	0	142	0	26	0	0	0	0	0	0	20	0	126	0	0	0
3	46	92	185	116	23	300	141	0	70	72	114	0	0	0	0	42	18	49	48	52	23	27	0	0	24	0	0	0	0	23
6	263	185	146	180	113	131	42	14	47	161	147	0	120	16	20	152	42	105	95	52	0	161	427	25	264	222	210	298	80	0
8	28	116	180	118	160	55	0	70	0	72	0	0	39	0	0	74	0	184	0	37	0	80	0	0	0	0	0	0	53	0
10	114	23	113	160	346	238	215	75	187	106	148	31	33	0	80	311	18	79	0	83	0	322	0	59	72	24	22	72	0	0
11	0	300	131	55	238	56	325	0	0	412	93	0	0	0	20	55	0	0	0	45	0	27	80	0	0	0	0	0	0	0
12	94	141	42	0	215	325	100	0	0	109	98	0	0	0	12	50	165	105	12	65	47	0	0	0	25	0	12	24	0	0
17	0	0	14	70	75	0	0	140	23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	94	0	0
18	23	70	47	0	187	0	0	23	140	0	0	0	0	0	0	0	0	303	0	17	0	0	0	0	0	24	0	0	0	0
22	28	72	161	72	106	412	109	0	0	1326	941	0	29	0	0	0	233	108	0	0	0	0	0	0	0	0	0	0	27	0
23	65	114	147	0	148	93	98	0	0	941	382	42	16	0	0	16	16	16	0	0	0	0	0	0	0	0	0	72	0	0
24	10	0	0	0	31	0	0	0	0	0	42	502	228	369	63	0	46	31	0	17	0	0	0	0	0	0	0	0	0	0
25	0	0	120	39	33	0	0	0	0	29	16	228	22	181	20	44	44	11	159	28	23	38	80	11	48	0	87	359	117	0
27	0	0	16	0	0	0	0	0	0	0	0	369	181	32	0	272	0	0	0	33	0	16	0	0	0	0	0	0	0	0
28	0	0	20	0	80	20	12	0	0	0	0	63	20	0	120	277	0	0	0	0	0	0	0	0	0	0	0	0	0	0
30	142	42	152	74	311	55	50	0	0	0	16	0	44	272	277	272	0	19	0	289	0	0	27	0	0	19	0	24	27	0
33	0	18	42	0	18	0	165	0	0	233	16	46	44	0	0	0	322	213	95	261	23	27	668	541	982	24	22	24	0	0
35	26	49	105	184	79	0	105	0	303	108	16	31	11	0	0	19	213	368	239	103	0	27	240	74	216	24	91	167	79	0
37	0	48	95	0	0	0	12	0	0	0	0	0	159	0	0	0	95	239	184	95	64	159	27	737	0	0	0	0	0	0
38	0	52	52	37	83	45	65	0	17	0	0	17	28	33	0	289	261	103	95	1240	17	0	0	688	17	0	0	0	27	0
39	0	23	0	0	0	0	47	0	0	0	0	0	23	0	0	0	23	0	64	17	0	164	97	0	0	23	0	72	0	0
40	0	27	161	80	322	27	0	0	0	0	0	0	38	16	0	0	27	27	159	0	164	1288	188	0	0	0	22	0	27	0
41	0	0	427	0	0	80	0	0	0	0	0	0	80	0	0	27	668	240	27	0	97	188	214	0	0	0	0	0	0	0
44	0	0	25	0	59	0	0	0	0	0	0	0	11	0	0	0	541	74	737	688	0	0	0	50	0	0	0	0	0	0
45	20	24	264	0	72	0	25	0	0	0	0	0	48	0	0	0	982	216	0	17	0	0	0	0	96	575	0	0	24	0
47	0	0	222	0	24	0	0	0	24	0	0	0	0	0	0	19	24	24	0	0	23	0	0	0	575	534	0	0	53	0
48	126	0	210	0	22	0	12	0	0	0	0	0	87	0	0	0	22	91	0	0	0	22	0	0	0	0	1048	0	27	0
51	0	0	298	0	72	0	24	94	0	0	72	0	359	0	0	24	24	167	0	0	72	0	0	0	0	0	0	48	722	167
52	0	0	80	53	0	0	0	0	0	27	0	0	117	0	0	27	0	79	0	27	0	27	0	0	24	53	27	722	1860	59
54	0	23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	167	59	0

Table 3.

Distances between demand nodes.

	1	3	6	8	10	11	12	17	18	22	23	24	25	27	28	30	33	35	37	38	39	40	41	44	45	47	48	51	52	54
1	0.00	1.97	3.69	5.05	4.02	4.87	5.41	5.33	4.75	8.34	11.36	10.17	10.99	14.50	17.61	14.51	6.09	6.33	11.26	10.03	14.33	15.24	19.66	11.78	10.28	13.86	19.81	20.37	26.07	45.32
3	1.97	0.00	1.83	3.11	2.39	3.59	3.59	7.25	5.90	10.97	9.39	8.34	9.49	12.76	16.25	13.31	5.59	7.10	11.95	9.55	14.39	16.08	20.10	13.16	12.06	15.83	21.78	22.05	27.53	46.56
6	3.69	1.83	0.00	1.42	0.83	2.26	1.75	9.02	7.67	10.20	7.95	6.51	7.74	10.93	14.54	11.71	4.81	7.39	11.96	8.56	13.78	16.17	19.75	13.86	13.26	17.49	23.40	23.04	28.21	46.94
8	5.05	3.11	1.42	0.00	1.66	2.70	0.95	10.36	8.69	9.09	6.55	5.31	6.99	9.83	13.81	11.20	5.44	8.53	12.90	8.84	14.29	17.13	20.42	15.11	14.65	18.89	24.80	24.37	29.42	48.00
10	4.02	2.39	0.83	1.66	0.00	1.43	1.50	9.32	8.29	10.73	8.12	6.19	7.10	10.48	13.86	10.97	4.03	6.87	11.31	7.74	12.99	15.54	19.01	13.45	13.10	17.64	17.64	22.74	27.76	46.37
11	4.87	3.59	2.26	2.70	1.43	0.00	2.03	9.97	9.42	11.72	8.61	5.83	6.13	9.82	12.75	9.73	2.74	6.13	10.25	10.25	10.25	14.48	17.72	12.83	12.93	17.97	23.71	22.27	27.02	45.40
12	5.41	3.59	1.75	0.95	1.50	2.03	0.00	10.74	9.37	9.70	6.71	4.77	6.13	9.18	12.96	10.28	4.71	8.09	12.28	7.96	13.45	16.50	19.63	14.76	14.57	19.13	24.99	24.13	29.00	47.42
17	5.33	7.25	9.02	10.36	9.32	9.97	10.74	0.00	4.15	16.98	16.47	15.50	16.06	19.75	22.43	19.16	10.32	8.31	12.44	13.79	16.72	15.56	20.85	10.60	7.37	8.74	14.76	17.30	23.80	43.55
18	4.75	5.90	7.67	8.69	8.29	9.42	9.37	4.15	0.00	13.46	13.84	13.98	15.39	18.51	22.14	19.15	10.84	10.39	15.13	14.76	18.76	18.74	23.66	14.28	11.44	12.28	18.26	21.45	27.88	47.57
22	8.34	10.97	10.20	9.09	10.73	11.72	9.70	16.98	13.46	0.00	4.92	9.39	12.73	12.47	18.13	16.97	14.40	17.58	21.97	17.20	22.84	26.20	29.16	24.03	22.96	25.63	31.65	33.01	38.40	57.09
23	11.36	9.39	7.95	6.55	8.12	8.61	6.71	16.47	13.84	4.92	0.00	4.65	7.98	7.60	13.22	12.10	10.98	14.75	18.56	13.06	18.68	22.72	25.07	21.44	21.20	25.17	31.15	30.84	35.60	53.66
24	10.17	8.34	6.51	5.31	6.19	5.83	4.77	15.50	13.98	9.39	4.65	0.00	3.37	4.58	9.35	7.64	7.45	11.55	14.66	8.68	14.20	18.68	20.59	18.19	18.74	23.78	29.57	27.75	31.95	49.49
25	10.99	9.49	7.74	6.99	7.10	6.13	6.13	16.06	15.39	12.73	7.98	3.37	0.00	4.20	6.83	4.45	6.39	10.41	12.52	6.08	11.27	16.29	17.60	16.67	17.94	23.75	29.27	26.21	29.83	46.78
27	14.50	12.76	10.93	9.83	10.48	9.82	9.18	19.75	18.51	12.47	7.60	4.58	4.20	0.00	5.73	5.74	10.53	14.60	16.57	10.03	14.69	20.16	20.81	20.85	22.11	27.74	33.35	30.37	33.78	50.21
28	17.61	16.25	14.54	13.81	13.86	12.75	12.96	22.43	22.14	18.13	13.22	9.35	6.83	5.73	0.00	3.46	12.19	15.56	15.76	9.71	12.33	18.47	17.58	20.70	23.00	29.47	34.62	29.76	31.99	46.86
30	14.51	13.31	11.71	11.20	10.97	9.73	10.28	19.16	19.15	16.97	12.10	7.64	4.45	5.74	3.46	0.00	8.85	12.10	12.46	6.26	9.49	15.44	15.29	17.32	19.53	26.03	31.16	26.49	29.07	44.73
33	6.09	5.59	4.81	5.44	4.03	2.74	4.71	10.32	10.84	14.40	10.98	7.45	6.39	10.53	12.19	8.85	0.00	4.13	7.62	3.98	8.97	11.83	14.99	10.74	11.58	17.45	22.90	20.30	24.66	42.78
35	6.33	7.10	7.39	8.53	6.87	6.13	8.09	8.31	10.39	17.58	14.75	11.55	10.41	14.60	15.56	12.10	4.13	0.00	4.93	6.01	8.48	8.99	13.36	6.71	7.57	13.95	19.10	16.22	20.91	39.57
37	11.26	11.95	11.96	12.90	11.31	10.25	12.28	12.44	15.13	21.97	18.56	14.66	12.52	16.57	15.76	12.46	7.62	4.93	0.00	6.55	4.97	4.23	8.53	5.13	8.56	15.77	19.84	14.04	17.33	35.16
38	10.03	9.55	8.56	8.84	7.74	10.25	7.96	13.79	14.76	17.20	13.06	8.68	6.08	10.03	9.71	6.26	3.98	6.01	6.55	0.00	5.65	10.21	12.01	11.14	13.30	19.95	24.94	20.50	23.78	40.83
39	14.33	14.39	13.78	14.29	12.99	10.25	13.45	16.72	18.76	22.84	18.68	14.20	11.27	14.69	12.33	9.49	8.97	8.48	4.97	5.65	0.00	6.23	6.39	9.92	13.53	20.74	24.73	17.88	19.67	35.56
40	15.24	16.08	16.17	17.13	15.54	14.48	16.50	15.56	18.74	26.20	22.72	18.68	16.29	20.16	18.47	15.44	11.83	8.99	4.23	10.21	6.23	0.00	5.72	5.66	9.93	16.86	19.79	11.76	13.66	30.95
41	19.66	20.10	19.75	20.42	19.01	17.72	19.63	20.85	23.66	29.16	25.07	20.59	17.60	20.81	17.58	15.29	14.99	13.36	8.53	12.01	6.39	5.72	0.00	11.38	15.64	22.56	25.20	15.96	15.44	29.44
44	11.78	13.16	13.86	15.11	13.45	12.83	14.76	10.60	14.28	24.03	21.44	18.19	16.67	20.85	20.70	17.32	10.74	6.71	5.13	11.14	9.92	5.66	11.38	0.00	4.27	11.28	14.81	9.58	14.38	33.57
45	10.28	12.06	13.26	14.65	13.10	12.93	14.57	7.37	11.44	22.96	21.20	18.74	17.94	22.11	23.00	19.53	11.58	7.57	8.56	13.30	13.53	9.93	15.64	4.27	0.00	7.22	11.64	10.18	16.44	36.19
47	13.86	15.83	17.49	18.89	17.64	17.97	19.13	8.74	12.28	25.63	25.17	23.78	23.75	27.74	29.47	26.03	17.45	13.95	15.77	19.95	20.74	16.86	22.56	11.28	7.22	0.00	6.02	12.19	19.36	38.98
48	19.81	21.78	23.40	24.80	17.64	23.71	24.99	14.76	18.26	31.65	31.15	29.57	29.27	33.35	34.62	31.16	22.90	19.10	19.84	24.94	24.73	19.79	25.20	14.81	11.64	6.02	0.00	11.22	17.87	36.40
51	20.37	22.05	23.04	24.37	22.74	22.27	24.13	17.30	21.45	33.01	30.84	27.75	26.21	30.37	29.76	26.49	20.30	16.22	14.04	20.50	17.88	11.76	15.96	9.58	10.18	12.19	11.22	0.00	7.17	26.88
52	26.07	27.53	28.21	29.42	27.76	27.02	29.00	23.80	27.88	38.40	35.60	31.95	29.83	33.78	31.99	29.07	24.66	20.91	17.33	23.78	19.67	13.66	15.44	14.38	16.44	19.36	17.87	7.17	0.00	19.85
54	45.32	46.56	46.94	48.00	46.37	45.40	47.42	43.55	47.57	57.09	53.66	49.49	46.78	50.21	46.86	44.73	42.78	39.57	35.16	40.83	35.56	30.95	29.44	33.57	36.19	38.98	36.40	26.88	19.85	0.00

Computational results

According to the genetic and tabu search hybrid optimization algorithm, a simulation is performed with MATLAB. The population size is 100, the crossover probability $P_{c}$ is 0.95, the mutation probabilities $P_{m 1}$ and $P_{m 2}$ are 0.02 and 0.03, respectively, and the maximum iterations is 10. Considering different combinations of discount factors, the model is solved using the genetic and tabu search hybrid optimization algorithm; the results are shown in Table 4.

Table 4.

The change of cost and hub location.

Discount factor	Number of nodes	Total cost	Transportation cost	Location of level I hub	Location of level II hub
$α_{1} = 0.7$ $α_{2} = 0.8$	15	9,074,538.6	74,538.8	33, 35	51, 52
	20	12,109,106.1	109,106.1	10, 33, 35	51, 52
	25	15,144,587.7	144,587.0	10, 12, 17, 33, 35	–
	30	18,184,714.9	184,712.0	6, 8, 10, 17, 33, 35	–
$α_{1} = 0.8$ $α_{2} = 0.8$	15	9,075,358.9	75,359.2	33, 35	51, 52
	20	12,110,826.7	110,827.0	10, 33, 35	51, 52
	25	15,147,711.6	147,711.2	10, 12, 17, 33, 35	–
	30	18,187,357.8	187,359.5	8, 10, 11, 17, 33, 35	–
$α_{1} = 0.8$ $α_{2} = 0.9$	15	9,076,521.1	76,521.0	33, 35	51, 52
	20	12,112,645.6	112,646.0	10, 33, 35	51, 52
	25	15,147,711.6	147,711.0	10, 12, 17, 33, 35	–
	30	18,187,846.5	187,844.0	10, 11, 12, 17, 33, 35	–
$α_{1} = 0.9$ $α_{2} = 0.9$	15	9,077,341.5	77,341.3	33, 35	51, 52
	20	12,114,366.2	114,366.0	10, 33, 35	51, 52
	25	15,150,835.6	150,835.5	10, 12, 17, 33, 35	–
	30	18,190,615.2	190,615.2	8, 10, 11, 17, 33, 35	–

It can be seen that the number and location of level I hubs and level II hubs have changed with different number of demand nodes. With an increase in node number, the number of level I hubs increases, and the number of level II hubs decreases. For example, when $α_{1} = 0.7$ , $α_{2} = 0.8$ , and the number of nodes is 20, then nodes 10, 33, and 35 are the level I hubs and nodes 51 and 52 are the level II hubs. But when the number of nodes is 25, then nodes 10, 12, 17, 33, and 35 are the level I hubs, and no level II hubs are identified. Meanwhile, the location of level I hubs and level II hubs has also changed with different combinations of discount factor. As shown in Table 4 when the node numbers are 15, 20, and 25, the discount factor changes, the number and location of level I hubs and level II hubs do not change. With 30 nodes, the location of level I hubs changes with different values of $α$ . For example, when $α_{2} = 0.8$ , $α_{1}$ changes from 0.7 to 0.8 and the level I hub changes from node 6 to 11. With $α_{1} = 0.8$ , $α_{2}$ changes from 0.8 to 0.9 and the level I hub changes from node 8 to 12. As the discount factor increases, the cost increases; thus, if we want to reduce the total cost, then the hub needs to move to a node with lower cost. The table also specifies that the location has not changed when $α_{1} = α_{2}$ at any time, regardless of the number of nodes.

Parameter analysis

The influence of capacity constraints on hub location and cost

Considering the two cases of the hub with and without capacity constraints, 15, 20, 25, and 30 nodes are selected from the 54 nodes: $n = 15, 20, 25, 30$ . The calculation results are shown in Table 5, where $α_{1} = 0.8$ , $α_{2} = 0.9$ , $F_{1} = 3, 000, 000$ , and $F_{2} = 1, 500, 000$ .

Table 5.

The change of hub number and location.

	Number of nodes	Total cost	Transportation cost	Location of level I hub	Location of level II hub
Without capacity constraint	15	3,094,938.5	94,939.0	35	–
	20	3,147,525.9	147,530.0	35	–
	25	3,179,277.0	179,277.0	33	–
	30	3,225,637.5	225,637.5	33	–
Capacity constraint $M_{1} = 10, 000$ $M_{2} = 4000$	15	9,076,521.1	76,521.0	33, 35	51, 52
	20	12,112,645.6	112,646.0	10, 33, 35	51, 52
	25	15,147,711.6	147,711.0	10, 12, 17, 33, 35	–
	30	18,187,846.5	187,844.0	10, 11, 12, 17, 33, 35	–

When the hub has no capacity constraints, all non-hub nodes are directly assigned to only one level I hub, and no level II hub is selected, because the total cost includes two parts: transportation cost and hub construction cost. The minimum total cost is the cost of building only one level I hub. When the hub has capacity constraints, the number of level I hubs increases, and the location of level II hubs also changes. The results indicate that the number of nodes increases from 15 to 30, the number of level I hubs increases from two to six, and nodes 33 and 35 are required, because the minimum distance is the distance from all nodes to nodes 33 and 35 in the set of possible location of level I hubs.

Figures 4 and 5 depict the trends of total cost and transportation cost for different numbers of demand nodes. Figure 4 reveals a distinct growth trend for total cost when a hub has capacity constraints and a very small change in total cost when a hub has no capacity constraints. Due to the capacity constraints, total cost changes with an increase in the number of selected hubs. From the standpoint of transportation costs, the cost with capacity constraints is lower than the cost without capacity constraints, as shown in Figure 5. Due to capacity constraints, a greater number of hubs can produce a greater economies of scale, which reduces the cost.

Figure 4.

Trend of total cost with different number of demand nodes.

Figure 5.

Trend of transportation cost with different number of demand nodes.

Influence of capacity value on hub numbers, locations, and costs

As planned, the capacity of a level I hub ranges from 5000 to 10,000. A level II hub ranges from 2000 to 5000. Table 6 shows seven different situations when $n = 20$ , $α_{1} = 0.8$ , $α_{2} = 0.9$ , $F_{1} = 3, 000, 000$ , and $F_{2} = 1, 500, 000$ . The results are shown in Table 6.

Table 6.

Cost and location for different capacity constraints.

Capacity constraint	Total cost	Transportation cost	Location of level I hub	Location of level II hub
$M_{1} = 5000$ $M_{2} = 2000$	22,674,063.2	174,068	3, 6, 10, 12, 18, 33, 35	54
$M_{1} = 8000$ $M_{2} = 2000$	15,134,101.2	134,106	3, 6, 10, 33, 35	–
$M_{1} = 10, 000$ $M_{2} = 2000$	12,126,819.0	126,819	10, 12, 33, 35	–
$M_{1} = 10, 000$ $M_{2} = 4000$	12,112,645.6	112,646	10, 33, 35	51, 52
$M_{1} = 10, 000$ $M_{2} = 5000$	12,102,075.8	102,075	10, 33, 35	51, 52
$M_{1} = 8000$ $M_{2} = 5000$	13,617,059.0	117,059	6	24, 25, 38, 44, 45, 51, 52
$M_{1} = 5000$ $M_{2} = 5000$	13,631,032.3	131,033	10	24, 25, 38, 44, 45, 51, 52

When the capacity of a level I hub is constant and the capacity of a level II hub is increased, the number of level I hubs decreases, and the number of level II hubs increases, as the location of hubs changes. If $M_{1} = 10, 000$ and $M_{2} = 2000$ , then level I hubs will include nodes 10, 12, 33, and 35, and no level II hubs will be chosen. If $M_{1} = 10, 000$ and $M_{2} = 5000$ , then level I hubs should include nodes 10, 33, and 35, and level II hubs will include 51 and 52. When the capacity of a level II hub is constant, then the number of level I hubs may increase or decrease as the capacity of level I hubs increases. However, the number of level II hubs will decrease. Additional nodes will become hubs as hub capacity increases. If $M_{2} = 5000$ and $M_{1} = 5000$ , then node 10 is level I hub and nodes 24, 25, 38, 44, 45, 51, and 52 are level II hubs. However, when $M_{2} = 5000$ and $M_{1} = 10, 000$ , nodes 10, 33, and 35 are level I hubs and nodes 51 and 52 are level II hubs. Regardless of the situation, node 10 is always a level I hub, with the exception when $M_{1} = 8000$ and $M_{2} = 5000$ , because the sum of the flow and cost is minimum from all nodes to node 10 among the set of possible level I hubs.

Figures 6 clarifies how level I hub capacity and level II hub capacity affect the transportation costs. When the level II hub capacity is constant, as $M_{2} = 5000$ , increasing the capacity of level I hub will reduce the transportation cost. When the level I hub capacity is constant, as $M_{1} = 10, 000$ , increasing the capacity of level II hub will reduce transportation cost, because the demand nodes will be assigned to the nearest hub nodes as the capacity of a hub increases which will reduce transportation cost.

Figure 6.

Trend of transportation cost with different capacity.

Influence of construction cost on hubs numbers and locations

According to the calculation, the construction costs of a level I hub and a level II hub are estimated as follows: $F_{1} = 3, 000, 000$ , $F_{2} = 1, 500, 000$ , the ratio $F_{1} / F_{2} = 2$ . To analyze the influence of hub construction cost on the hub location, $F_{2}$ is unchanged, and the values of $F_{1}$ are changed to obtain different $F_{1} / F_{2}$ . The calculation results are shown in Table 7, where n = 20, $α_{1} = 0.8$ , $α_{2} = 0.9$ , $M_{1} = 10, 000$ , and $M_{2} = 5000$ . In the case of $F_{1} / F_{2} = 2$ , the location of the level I hubs are 10, 33, 35, and the location of level II hubs are 51 and 52. In the case of $F_{1} / F_{2} < 2$ , the number of the level I hubs increases, whereas the level II hub has no choice. In the case of $F_{1} / F_{2} > 2$ , the number of level I hubs decreases, and the number of the level II hubs increases. When the ratio decreases, the construction costs of the level I hub and the level II hub have no significant difference, and the economy of scale for the level I hub is larger. Thus, if we allocate all demand nodes to level I hub, the total cost decreases. As the ratio increases, the construction costs of level I hub and level II hub are significantly different. Since the construction cost of the level II hub is considerably lower, if we assign additional demand nodes to level II hub, the total cost will be relatively low. As shown in Table 6, an increase in $F_{1} / F_{2}$ causes an increase in the total cost, whereas the transportation cost tends to decrease and then increase. When $F_{1} / F_{2} = 2$ , the lowest transportation cost is achieved.

Table 7.

Hub quantity and location for different construction costs.

Construction cost	$F_{1} / F_{2}$	Total cost	Transportation cost	Location of level I hub	Location of level II hub
$F_{1} = 2, 000, 000$ $F_{2} = 15, 00, 000$	1.300	8,126,819.0	126,817.0	10, 12, 33, 35	–
$F_{1} = 2, 250, 000$ $F_{2} = 1, 500, 000$	1.500	9,126,819.0	126,817.0	10, 12, 33, 35	–
$F_{1} = 2, 812, 500$ $F_{2} = 1, 500, 000$	1.875	11,376,819.0	126,817.0	10, 12, 33, 35	–
$F_{1} = 3, 000, 000$ $F_{2} = 1, 500, 000$	2.000	12,102,075.8	102,075.0	10, 33, 35	51, 52
$F_{1} = 4, 000, 000$ $F_{2} = 1, 500, 000$	2.600	13,129,118.9	129,118.9	10	24, 25, 38, 44, 45, 52
$F_{1} = 4, 500, 000$ $F_{2} = 1, 500, 000$	3.000	13,629,118.9	129,118.9	10	24, 25, 38, 44, 45, 52
$F_{1} = 5, 625, 000$ $F_{2} = 1, 500, 000$	3.750	14,754,118.9	129,118.9	10	24, 25, 38, 44, 45, 52

Conclusion

The application of a hub-and-spoke network in urban and rural public transport planning is a relatively new idea. This work can integrate the resources of urban and rural public transport and reduce the travel cost of residents by utilizing economies of scale. Combining the actual background of integration of urban and rural public transport and considering three-level nodes of urban public transport hub, central town hub and demand nodes, a multi-level hub-and-spoke network is constructed, and a mixed-integer programming model is presented in this article. The effectiveness of the model is computed, verified, and analyzed using a genetic and tabu search hybrid optimization algorithm and actual data of urban and rural passenger transportation.

The main contribution of the article is described as follows: first, combining the practical problems of integration of urban and rural public transport, a multi-level complete network that considers the connections among level II hubs, which differs from existing network, is constructed. Second, to address existing problems of separately locating urban hubs and central town hubs, a hierarchical hub location model is constructed. The model can effectively and simultaneously determine the locations of urban public transport hubs (level I hubs) and central town hubs (level II hubs), which minimizes the total cost of the network. Third, the capacity constraints of two-level hubs in the hub-and-spoke network are also considered. The results reveal that the capacity constraints of two-level hubs not only significantly influence the locations and quantities of hubs but also have a significant impact on transportation costs. Moreover, the capacity constraints make the network more reasonable and enable the layout of hubs to fit the actual travel characteristics.

However, due to lapse of time and development of economy, the network structure of integration of urban and rural public transport will change. Establishing a dynamic and uncertain urban and rural public transport hub location model will be studied in the future. The genetic algorithm and tabu search hybrid optimization algorithm in this article are aimed at small scale demand nodes; Abdinnour-Helm proves its effectiveness in solving the problem of single layer network location when the number of demand nodes is large. However, additional research is necessary to determine whether the algorithm is superior in solving multi-layer hub location problem.

Footnotes

Handling Editor: Daniel Gutierrez-Reina

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by “Chunhui” planning project of Ministry of Education of the People’s Republic of China (S2016012). This research was also supported by Science & Technology Development program of Jilin Province (20180418101FG).

References

Alumur

Kara

BY.

Network hub location problems: the state of the art. Eur J Oper Res 2008; 190: 1–21.

O’Kelly

ME.

A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 1987; 32(3): 393–404.

Farahani

Hekmatfar

Arabani

et al . Hub location problems: a review of models, classification, solution techniques, and application. Comput Ind Eng 2013; 64: 1096–1109.

Gao

Study on layout of passenger station under urban-rural passenger transport integration. Master’s Thesis, Chang’an University, Xi’an, China, 2008.

Wang

Study on of integrated development of urban and rural passenger transport. Master’s Thesis, Chang’an University, Xi’an, China, 2010.

Yin

JJ.

Study on macro-layout of passenger station under urban-rural passenger transport integration. Master’s Thesis, Shandong University of Science and Technology, Qingdao, China, 2011.

Wang

MK.

Research on integrated passenger transport system based on urban and rural coordination and development. PhD Thesis, Southwest Jiaotong University, Chengdu, China, 2010.

Nutley

SD.

Indicators of transport and accessibility problems in rural Australia. J Transp Geogr 2003; 11: 55–71.

Widener

Horner

MW.

A hierarchical approach to modeling hurricane disaster relief goods distribution. J Transp Geogr 2011; 19: 821–828.

10.

Sheu

Lin

AYS

. Hierarchical facility network planning model for global logistics network configurations. Appl Math Model 2012; 36: 3053–3066.

11.

Teixeira

Antunes

AP.

A hierarchical location model for public facility planning. Eur J Oper Res 2008; 185: 92–104.

12.

Baray

Cliquet

Optimizing locations through a maximum covering/p-median hierarchical model: maternity hospitals in France. J Bus Res 2013; 66: 127–132.

13.

Barros

Dekker

Scholten

A two-level network for recycling sand: a case study. Eur J Oper Res 1998; 110: 199–214.

14.

Juan

ZC.

Kernel search algorithm for two-level emergency repair system location problem. Appl Res Comput 2013; 30: 3232–3235.

15.

Elmastas

. Hub location problem for air-ground transportation systems with time restrictions. M.S Thesis, Bilkent University, Ankara, 2006.

16.

Yaman

The hierarchical hub median problem with single assignment. Transport Res Part B: Meth 2009; 43: 643–658.

17.

Alumur

Yaman

Kara

BY.

Hierarchical multimodal hub location problem with time-definite deliveries. Transport Res Part E: Log 2012; 48: 1107–1120.

18.

Davari

Zarandi

MHF

. The single-allocation hierarchical hub median location problem with fuzzy demands. Afr J Bus Manag 2012; 6: 347–360.

19.

Karimi

Eydi

Korani

Modeling of the capacitated single allocation hub location problem with a hierarchical approach. Int J Eng 2014; 27: 573–586.

20.

Dükkanci

Kara

BY.

Routing and scheduling decisions in the hierarchical hub location problem. Comput Oper Res 2017; 85: 45–57.

21.

Zheng

Kuang

Location of regional and international hub ports in liner shipping. Mar Bus Rev 2017; 2(2): 114–125.

22.

Tingting

Rui

Shiwei

et al . Optimization model of comprehensive passenger hub in urban agglomeration based on hierarchical layout. China J Highway Transp 2016; 29: 116–122.

23.

O’Kelly

ME.

Hub location with flow economies of scale. Transport Res Part B: Meth 1998; 32: 605–616.

24.

Ernst

Krishnamoorthy

. Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Sci 1996; 4: 139–154.

25.

Ebery

Solving large single allocation p-hub problems with two or three hubs. Eur J Oper Res 2001; 128(2): 447–458.

26.

Lin

Chen

YC.

The capacitated p-hub median problem with integral constraints: an application to a Chinese air cargo network. Appl Math Model 2012; 36(6): 2777–2787.

27.

Topcuoglu

Corut

Ermis

et al . Solving the uncapacitated hub location using genetic algorithms. Comput Oper Res 2005; 32: 967–984.

28.

Kratica

Stanimirovic

Tosic

et al . Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. Eur J Oper Res 2007; 182: 15–28.

29.

Abdinnour-Helm

A hybrid heuristic for the uncapacitated hub location problem. Eur J Oper Res 1998; 106: 489–499.

30.

Cunha

Silva

MR.

A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. Eur J Oper Res 2007; 179: 747–758.

31.

Skorin-Kapov

O’Kelly

Tight linear programming relaxation of uncapacitated p-hub median problems. Location Sci 1996; 94: 582–593.