{'fraction_non_alphanumeric': 0.026459918913151716, 'fraction_numerical': 0.011878511985205207, 'mean_word_length': 4.7860082304526745, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
BI-OBJECTIVE COLLABORATIVE SCHEDULING OPTIMIZATION OF AIRPORT FERRY VEHICLE AND TRACTOR

With the continuous growth of aviation business, the flight ground support capability of airport is facing great challenges. The resources of ferry vehicle and tractor are important factors that restrict the flight service level of the airport. This paper analyses the collaborative scheduling of airport ferry vehicle and tractor through innovatively constructing a bi-objective mixed integer programming model, one objective is to minimize the number of ferry vehicles and tractors, and the other is to balance the vehicle usage. To deal with this problem, two methods based on standard particle swarm optimization are adopted: the lexicographic method and Pareto method, and virtual flights are introduced for the convenience of particle coding. The effectiveness and comparison of two methods are illustrated by employing the real flight data of Beijing Capital International Airport. The results of this study may provide reference for the evaluation and optimization of the airport ground support vehicles.


INTRODUCTION
In recent years, the main production indicators of most Chinese airports have maintained rapid growth. For example, the passenger transportation volume of domestic airports in 2018 has reached 1.2 billion, with a year-on-year growth of 10.2 %. The cargo and mail transportation volume has exceeded 16 million tons, with a year-on-year growth of 3.5 %. The annual passenger throughput of Beijing Capital International Airport in 2018 exceeded 100 million for the first time, the cargo and mail transportation volume exceeded 2 million tons [1]. The flight ground support capability of most hub airports and trunk airports is facing increasing pressure, which leads to the shortage of airport time slot resources, air traffic congestion, serious flight delay and the decline of service quality.
Flight ground support services include disembarkation and embarkation, refuelling, unloading and loading luggage, catering, cleaning and towing. These services are mainly provided by special vehicles such as ferry vehicles, fuelling vehicles, luggage trailers, catering vehicles, potable water vehicles and tractors, with strict service priority and time windows. The flight ground support capacity of airports needs to be improved urgently since it is the main factor causing flight delay. At present, the scheduling of flight ground support vehicles mainly relies on manual scheduling and operation, which leads to low efficiency and insufficient ability in dealing with emergent events, especially in large airports.
At present, the optimization of airport ground handling processes has become a research hotspot [2,3]. The optimal scheduling and allocation of various ground resources of airport including support vehicles, gates and runways have been studied, such as ground support vehicle scheduling problem [4], gate assignment problem [5,6] and runway assignment problem [7,8]. There are few literatures considering airport ground support vehicle scheduling. For example, Padrón et al. [9] studied the bi-objective collaborative scheduling of multiple support vehicles by modelling each of these support vehicle scheduling problems as a VRPTW sub-problem. Du et al. [10] constructed a mixed integer programming model based on the objective of minimizing operating costs, and designed a column generation heuristic algorithm for a tractor scheduling problem. Ip et al. [11] presented a model that minimizes the total flight delay caused by the ground support service with a novel generic algorithm. Norin et al. [12] applied a programming model to minimize the weighted sum of delay time and travel distance of de-icing vehicles. Among them, there are few researches on the collaborative scheduling of ferry vehicle and tractor, and it is often assumed that a flight only corresponds to one ferry vehicle, which is not completely consistent with the actual situation.
In the present study, we put forward a bi-objective mixed integer programming model to optimize the collaborative scheduling of ferry vehicle and tractor, and virtual flights [13] are introduced for the convenience of particle coding in particle swarm optimization (PSO) algorithm. Then the lexicographic method and Pareto method based on standard PSO are adopted to solve the problem. The rest of the paper is organized as follows. Section 2 describes the problem and constructs the model. Section 3 presents the details of the two methods based on standard PSO for this problem. Section 4 uses the flight data of Beijing Capital International Airport for simulation example. Some conclusions are finally drawn in Section 5.

Problem description
The problem can be described as that there are n flights in the airport that require ferry service and towing service in a period of time. The airport has m 1 ferry vehicles and m 2 tractors. The number of ferry vehicles per flight needed depends on the type of aircraft, and each flight requires only one tractor. The goal is to minimize the total number of vehicles and balance the vehicle usage under the constraints of service priority and time windows. Since the model considers the collaborative scheduling of ferry vehicle and tractor, and arrival flights generally do not need towing service except for special circumstances, the flight to be served in the present study is the departure flight by default. Some other assumptions of the model are as follows: (1)A flight needs at least one ferry vehicle and only one tractor. If flight i needs two ferry vehicles, a virtual flight is introduced for the convenience of model construction and solving process. Each of real flights and virtual flights corresponds to one ferry vehicle, and only real flight needs tractor.
(2)The tractor service can only be carried out after the end of the ferry vehicle service on the same flight.
(3)Vehicles are allowed to arrive early rather than late. If the actual arrival time of the vehicle is earlier than the time window (the earliest start time), the vehicle has to wait, and the actual arrival time of the vehicle is not permitted to be later than the time window.

Model construction
A bi-objective mixed integer programming model is constructed based on above assumptions. The parameters and decision variables involved in this model are listed as follows.
∈ The time when the tractor arrives at the parking position of flight , ∈ According to the parameters and decision variables, the mathematical model can be described as follows.
The objective function (1) indicates that the number of ferry vehicles and tractors are minimized. The objective function (2) (11) to (14) indicate the relationship of decision variables  ,  ,  ,  ,  ,  , , and . Constraints (15) indicate that the service end time of the last ferry vehicle for real flight i should be earlier than its latest towing start time.

Problem analysis
Since the special vehicle scheduling problem is essentially a VRP (Vehicle Routing Problem), and particle swarm optimization has certain advantages in solving VRP (such as simple coding, fast convergence, and easy programming [14]), this algorithm is considered to be used to solve this model.
The standard PSO algorithm [15] is as follows: Let the search space be D dimensions, the total number of particles is n. A particle i is defined by three vectors: the current position = ( 1 , 2 , ⋯ , ), the current velocity = ( 1 , 2 , ⋯ , ) and the optimal position it found so far = ( 1 , 2 , ⋯ , ). Furthermore, each particle knows the global optimal position P g found so far by its neighbors. The algorithm proceeds iteratively by updating velocities and positions of particles as follows:

Particle coding based on virtual flights
Construct a 4n-dimensional space corresponding to n flights to be served, each flight requires ferry vehicle and tractor services, vectors x1 and x2 represent the scheduling scheme of ferry vehicles and tractors respectively. Vectors x1 a and x2 a represent the ferry vehicles and tractors serving the flights respectively. Vectors x1 b and x2 b respectively represent the order in which the flights are served by ferry vehicles and tractors. For example, there are 7 flights requiring ferry vehicle and tractor services for a period of time, of which flights 1, 2, 3 and 4 are real flights, and flights 5, 6, 7 are virtual flights respectively corresponding to real flights 1, 2, 3. There are three ferry vehicles and three tractors serving them. The position vector X of a particle at a certain generation is shown in Table III.   Table III as an example, the value in x1 a is 1, which means that this flight is served by ferry vehicle 1, and the value in x1 b is 2, which means that this flight is the second flight served by ferry vehicle 1. The value in x2 a is 2, indicating that flight 4 is served by tractor 2, and the value in x2 b is 2, which means that this flight is the second flight served by tractor 2.
Taking the ferry vehicle 1 in Table III as an example, it departs from the terminal, and then serves the flight 1, 4, 5(1) successively. The flight 5(1) is the virtual flight corresponding to the real flight 1. By analogy, the decoding of the particle is shown in Table IV.

Main process of the lexicographic method and Pareto method
The lexicographic method ranks all objectives according to their importance. First find the optimal solution of the most important objective, and then optimize the next objective under the condition that the optimal value of the previous objective is guaranteed, until the last objective is obtained. In this paper, we first use this method for the solution with the least number of vehicles and the solution with the most balanced vehicle usage respectively, which are the two endpoints of Pareto front. Then, the multi-objective particle swarm optimization (MOPSO) algorithm is also employed for Pareto optimal solutions. The algorithm can be divided into two phases: the initialization of the particle population and the iterative process of the particles. The present study uses the grid method [16] to select the pBest (individual optimal) and gBest (global optimal). The algorithm process is as follows: Phase 1: Initialize the particle population and Archive set.
(1) Randomly generate N particles to form an initial particle population P 1 ; (2) The non-inferior solutions in the initial population P 1 are stored in the Archive set A 1 ; (3) The particles in the initial population P 1 are pBest, and the adaptive grid method is used to find the gBest in the population.
Phase 2: Repeat the following steps until the termination condition is met.
(1) For each particle, update the velocity and position according to (3.1) and (3.2); (2) Update the Archive set, gBest and randomly select the non-inferior solution particles in the previous generations as pBest; (3) The truncation operation of the Archive set; (4) Output the particle solutions in the Archive set.

Data preprocessing
The departure flight data of Beijing Capital International Airport during morning peak from 7:00-8:00 on November 4, 2017 are employed for simulation analysis. Air China company is responsible for the service of flights parking at aprons 3, 4, 5, 9, M and N2. The related data of the flights are given in Table V. STD represents the scheduled departure time of the flight. The type of aircraft is C, which means that the flight requires two ferry vehicles, and then a virtual flight is introduced. In this example, both the number of real flights and virtual flights are 20, ferry vehicles serve real and virtual flights for a total of 40 while tractors only need to serve 20 real flights. Table VI lists the travel time of vehicles.  For PSO parameters, the particle population size N = 100, the inertia coefficient  = 0.7, the acceleration factors c 1 = c 2 = 1.5, and the maximum number of iterations J = 200.

Simulation results
The lexicographic method is firstly used to solve the bi-objective programming, the two endpoints of the Pareto front and several possible Pareto solutions are shown in Table VII.  The vehicle scheduling scheme corresponding to the Pareto solution 1 is shown in Table  IX and Table X.   The MOPSO algorithm is also applied to solve this problem, some Pareto solutions during the iteration are depicted in Fig. 1. Obviously, the Pareto fronts obtained by the MOPSO algorithm are gradually close to the Pareto front of the lexicographic method as the number of iterations increases. Among them, the non-inferior solutions after 199 iterations of MOPSO are listed in Table  XI. The scheduling schemes corresponding to the two endpoints of the Pareto front generated by the lexicographic method and MOPSO algorithm (199 iterations) are shown in Fig. 2.
It can be seen from the above results that as the number of iterations increases, the Pareto front obtained by MOPSO is getting better overall, indicating the effectiveness of algorithm. However, the results obtained by MOPSO are not as good as those by lexicographic method. This is because the value of the first objective can only be an integer, while the minimum value of the second objective can be 0. Regardless of which objective is taken as the first priority, the lexicographic method can be used to obtain the optimal solution. Therefore, it is more suitable for the problem studied in this paper.

CONCLUSION
This paper studies the collaborative scheduling optimization of ferry vehicle and tractor. The minimum number of vehicles and the most balanced usage of vehicles are two objectives of proposed bi-objective mixed integer programming model. To handle the problem, virtual flights are introduced and the lexicographic method based on PSO and MOPSO algorithm are adopted. The effectiveness of the two methods is compared through the simulation example of flight data from Beijing Capital International Airport. The results of this study may provide reference for the evaluation and optimization of the airport ground support vehicles.