# A Method to Optimize Routing Paths for City-Pair Airlines on Three-Layer Air Transport Networks
## 2 Multi-Layer Air Transport Networks
### Problem Description  
Generally, a city-pair airline (or a pair of airports) in an airline network \(G_{AN}\) may correspond to multiple routing paths on the air route network \(G_{ARN}\) as shown in Figure 4. In Figure 4a, given a city-pair airline from Jinan to Hefei, there are three candidate routing paths on the air route network, including  
(1) \(\mathrm{JiNan}\rightarrow\mathrm{P200}\rightarrow\mathrm{P64}\rightarrow\mathrm{ P223}\rightarrow\mathrm{P181}\rightarrow\mathrm{ATV}\rightarrow\mathrm{P42}\rightarrow\mathrm{Hefei}\)  
(2) \(\mathrm{JiNan}\rightarrow\mathrm{P86}\rightarrow\mathrm{P182}\rightarrow \mathrm{ATV}\rightarrow\mathrm{P42}\rightarrow\mathrm{Hefei}\)  
(3) \(\mathrm{JiNan}\rightarrow\mathrm{P197}\rightarrow\mathrm{P182}\rightarrow \mathrm{ATV}\rightarrow\mathrm{P42}\rightarrow\mathrm{Hefei}\)In Figure 3(b), given a city-pair airline from Jinan to Shanghai, there are three candidate routing paths on the air route network, including  
**Figure 4. An example of multi-routing paths on air route network for city-pair airlines.**  
However, in reality, air traffic managers usually take default routing paths for each city-pair airline, and all the traffic flows between the pair of cities are along the default routing path. However, the simple routing path selection strategy for city-pair airlines may incur the congestion of some air route segments on the air route network. For example, if the city-pair airline \"Jinan \(\rightarrow\) Hefei\" takes the routing path that \"JiNan \(\rightarrow\) P197 \(\rightarrow\) P182 \(\rightarrow\) ATV \(\rightarrow\) P42 \(\rightarrow\) Hefei\", and airline \"JiNan \(\rightarrow\) ShangHai\" takes the routing path that \"JiNan \(\rightarrow\) P197 \(\rightarrow\) NJHLD \(\rightarrow\) SZPOI \(\rightarrow\) ShangHai\", the shared air route segment \"JiNan \(\rightarrow\) P197\" may be congested.  
Therefore, it is necessary to select the optimization routing path for each city-pair airline, in the strategy stage, from the alternative pre-planned routing paths, such that the traffic flow distribution of the air route network can be optimized, and the work load and congestion issue of the air route network can be minimized.  
To simplify the discussion, the candidate routing paths in the air route network for each city-pair airline \(l_{i,j}\) can be labelled as \(S_{crp}^{i,j}\). Therefore, the routing-path optimization problem can be defined as follows.  
Consider the following inputs:the air route network, \(G_{ARN}\), which is the basis of national airspace and will affect the flight distance and operational capacity of the air transportation system; - the city-pair airline network, \(G_{AN}\), which represents the existence of flights between a pair of airports or not; - the flight operation network, \(G_{FN}^{t}\), at different time intervals \([t,t+1)\), \(1\leq t\leq 24\), which represents the air traffic flows based on the timetable of flights; - the coupling relationship between the three-layer air transport networks, as discussed in Section 2.2. - the candidate routing paths \(S_{crp}^{ij}\) for the each city-pair airline \(l_{i,j}\) in \(G_{AN}\).  
Our goal is to select the optimization routing path from the candidate set \(S_{crp}^{ij}\) for each city-pair airline \(l_{i,j}\) in \(G_{AN}\) such that the flights from airport \(a_{i}\) to \(a_{j}\) of the flight operation network \(G_{FN}^{t}(1\leq t\leq 24)\) can fly along the optimization routing paths (a sequence of waypoints) on the air route network \(G_{ARN}\), with minimal congestion of the air route network.