# Multi-Objective Gate Allocation Problem Based on Multi-Commodity Network Flow Model
## 3 Problem Description  
The gate allocation problem proposed in this paper involves arrival and departure, which are continuous and highly correlated. Airport Collaborative Decision-Making (ACDM) provides accurate and detailed decision-making support from multiple sources in surface control. Additionally, it provides rich information to a large extent for the solution of multi-objective optimization problems. Firstly, the arrival flight lands on the designated runway at the landing time to complete the runway taxiing task, then leaves the runway, enters the taxiway, and meets the surface taxiing task according to the path and designated rules. Then, the aircraft enters the apron taxiway and stops at the pre-allocated gate at the in-block time. After completing the ground support work, the departure process of the corresponding aircraft will be carried out. For a departing aircraft, it first leaves the gate at the off-block time and enters the apron taxiway. Then, according to the corresponding taxi path, it arrives at the runway threshold and enters the runway at the take-off time. Due to the high uncertainty and flexibility of the airport surface, some assumptions are made in the modeling process to realize the multi-objective gate allocation and provide the optimization scheme of surface resource scheduling. The solution to the problem is based on the following assumptions. 1. Solving the gate allocation problem requires multiple sources of information, such as flight plans, aeronautical information publication, airport layouts, etc. We assume that the above information is known and complete to support subsequent studies and experiments. 2. We assume that the total number of flights is kept within the airport capacity, and enough remote gates are set up to allocate each flight. To describe the resource situation of an airport, the network model of the airport gate schedule is established, and the knowledge of graph theory is used to construct the directed graph \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of directed edges. The gate allocation problem is similar to the multi-commodity network flow model, which is the problem of allocating different gates as different commodities from the same origin node to the same destination node in the network. The paradigm of the multi-commodity network flow model is shown in Figure 1a, which includes four types of nodes and five types of arcs, as detailed below:  
(1) Node: The node represents the static state in the gate allocation. The origin node \(O\) is a virtual node, which is the starting point of the gate as the commodity. According to the order of the aircraft on the surface, the gate is first allocated to the corresponding arrival flight, that is, the gate flows from the unique origin node \(O\) to one of the flight arrival nodes \(a_{i}\). Then, the gate is allocated to the corresponding departure flight, that  
Figure 1: Multi-commodity network flow model for gate allocation. (**a**) The basic paradigm. (**b**) An example of the allocation result with three gates and five flight pairs. is, the gate flows from the flight arrival node to the corresponding flight departure node \(d_{j}\). When the gate is no longer occupied, it will eventually flow to the only destination node \(D\) to be recycled, which is also a virtual node. The node set \(V\) can be summarized as follows, where \(N\) is the number of flight pairs. \[V=\big{\{}O,a_{i},d_{j},D\big{\}},i,j\in[1,N]\] (1) Arc: An arc is a directed edge representing the dynamic trend of the gate. The entering arc \(\widehat{OA}\) is the direction from the origin node \(O\) to the flight arrival nodes \(a_{i}\), indicating the allocation status of the corresponding gate designated for the arrival flight. Its existence means that the corresponding gate is occupied. The holding arc \(\widehat{AB}\) is the direction from the arrival to the corresponding departure flight, indicating the gate's continuous occupancy status. That is, the related aircraft is receiving ground service.