Keywords

1 Introduction

With the rapid development of the civil aviation industry and airport scale enlargement in China, the problem of the low efficiency of the airport is becoming more and more prominent; thus how to respond quickly to basic business in airport operation has become a key issue to achieve efficient operation of airports. As a key step in ground support services, ground support vehicles with improper scheduling are likely to cause flight delays and affect the subsequent missions, which might bring negative effects to passengers and airports. Therefore, it is economic and socially significant to study the problem of ground guarantee vehicle scheduling.

Because of the characteristics of computation complexity, multiple objectives, multiple constraints and dynamic randomness, the scheduling of actual airport ground support vehicles is a combinatorial optimization problem with NP-hard feature. In recent years, scholars have been widely concerned the problem, and present many heuristic algorithms. For example, Norin et al. in [1] present the scheduling model of scheduling de-icing vehicles, and design a greedy randomized algorithm which minimizes the delay of flights due to de-icing, and the travel distance of the de-icing vehicles. The experiment demonstrates the effectiveness of the optimal scheduling model, and the dynamic optimization method is further demonstrated that the optimized scheduling model can effectively reduce the waiting time of deicing. Cheung et al. in [2] aim to minimize the total flow time of the vehicle, and carry out the separate dispatch of the tractor, the clean water car and the cleaning car. Due to the low efficiency of airport ground support service, Jie et al. in [3] considered the time window constraints of the ground service guarantee vehicle scheduling and the different resource requirements of the vehicle during the service process, and then proposed the multi-objective mathematical programming model and the two stage heuristic algorithm for solving in the problem. Li et al. in [4] developed an ant colony optimization (ACO)-based hyperheuristic (ABH) for intercell scheduling with single processing machines and batch processing machines.

There are mainly two kinds of optimization methods for vehicle scheduling problem. One is mathematical exact algorithm, the other is heuristic algorithm based on knowledge information and stochastic characteristics. The most commonly used exact algorithms include branch and bound algorithm, enumeration method based on Disjunctive graph model, mixed integer programming model, Lagrange relaxation algorithm and priority rule scheduling algorithm. Although these algorithms can guarantee the global optimal solution of the resource scheduling problem, they can only solve the problems with small scale instead of the problems with large scale in a given time. For this reason, many scholars study the heuristic algorithms with random characteristics to solve large scale problems, such as greedy algorithm, simulated annealing, ant colony algorithm, genetic algorithm [5], particle swarm optimization algorithm [6] and so on.

The greedy algorithm is an approximate method to solve the optimization problem [7]. Its basic idea is to refine and improve the quality of the solution of the problem based on gradient descent direction and heuristic information, which is difficult to search from the global viewpoint and generally makes local improvement. The execution process of a greedy choice is an improvement for the solution, and finally the global solution or approximate optimal solution is obtained through a series of local optimal selection.

Greedy algorithm is widely used in scheduling problems because it has the characteristics of simple procedure, high efficiency and low time complexity. For example, a hybrid iterated greedy algorithm for the distributed no-wait flow shop scheduling problem [8]. A task scheduling algorithm combining greedy algorithm with granularity control is designed for scheduling problem of structured parallel control mechanism on cluster system [9].

While considering the influence between the waiting time on the arrival of the vehicle and the distance between the vehicle and the flight, the optimization model is given, and an evaluation value function with respect to two greedy strategy is set up so that the flight with a minimal evaluation value can be taken as the next service object and the best service process can be searched.

The rest of the paper is as follows. In the second section, the mathematical model of airport vehicles scheduling optimization is established while considering the total distance and the number of the vehicles for the scheduling problem of the airport vehicle. Section three gives the scheduling algorithm based on greedy algorithm. The fourth part in this paper shows the experimental study and comparative analysis. The last part outlines the conclusion of the paper and discusses future works.

2 Airport Refueling Vehicle Scheduling Problem (ARVSP)

2.1 Problem Description

Airport refueling vehicle scheduling problem can be described as follows: There are N vehicles providing refueling services for M flights. The vehicles starts from the parking lot and returns to the parking lot when the number of service flights is reached to the maximum number of the vehicles allowed. Vehicles number set is set to U = {1, 2, 3… N}, flights number set is P = {1, 2, 3… M}. The capacity of oil required for the flight i is Qi, and the maximum allowable capacity of each vehicle is Q. Thus the aim of ARVSP is to plan the service flight sequence of each vehicle. At the same time, the following conditions are required to meet, a vehicle is only allocated to a flight anytime, and a flight is only serviced by a vehicle. All flights must be serviced in the specified time window.

2.2 Mathematical Model

The mathematical model of ARVSP is to determine the scheduling strategy of vehicle while considering the constraint conditions, so that the total distance of the vehicle flight service and the number of vehicles to be dispatched are all minimum. The objective function and constraint conditions in the model are described as follows.

$$ Min\quad f(x) = [f_{1} (x),f_{2} (x)] $$
(1)
$$ f1(x) = \sum\limits_{{k \in {\text{U}}}} {\sum\limits_{{k \in {\text{U}}}} {\sum\limits_{{k \in {\text{U}}}} {d_{ij} y_{i,j,k} } } } $$
(2)
$$ f2(x) = \sum\limits_{{k \in {\text{U}}}} {\sum\limits_{{j \in {\text{P}}}} {y_{o,j,k} } } $$
(3)
$$ s{.}t.\;{ \hbox{min} }\sum\limits_{{k \in {\text{U}}}} {\left( {\sum\limits_{{i \in {\text{P}}}} {y_{i,j,k} - \frac{M}{N}} } \right)} $$
(4)
$$ { \hbox{min} }\sum\limits_{{k \in {\text{U}}}} {\left( {\sum\limits_{{i \in {\text{P}}}} {Q_{i} x_{ik} - \frac{Q}{D}} } \right)} ,Q = \sum\limits_{{i \in {\text{P}}}} {Q_{i} } $$
(5)
$$ \sum\limits_{{j \in {\text{P}}}} {y_{o,j,k} } + \sum\limits_{{i \in {\text{P}}}} {\sum\limits_{{j \in {\text{P}}}} {y_{i,j,k} } } + \sum\limits_{{i \in {\text{P}}}} {y_{i,o,k} } \le E,\forall k \in {\text{U}} $$
(6)
$$ \sum\limits_{{i \in {\text{P}}}} {} \sum\limits_{{j \in {\text{P}}}} {Q_{i,j,k} } < Q,\forall k \in {\text{U}} $$
(7)
$$ A_{i} < s_{ik} < B_{i} ,\forall i,j \in {\text{P}},k \in {\text{U}} $$
(8)
$$ s_{ik} + t_{i} + t_{ij} < s_{jk} ,\forall i,j \in {\text{P}},k \in {\text{U}} $$
(9)
$$ y_{i,o,k} \in \{ 0,1\} ,\forall i \in {\text{P}},k \in {\text{U}} $$
(10)
$$ y_{o,j,k} \in \{ 0,1\} ,\forall j \in {\text{P}},k \in {\text{U}} $$
(11)
$$ x_{ik} \in \left\{ {0\left. {,1} \right\}} \right.,\forall j \in {\text{P}},k \in {\text{U}} $$
(12)
$$ y_{i,j,k} \in \{ 0,1\} ,\forall i,j \in {\text{P}},k \in {\text{U}} $$
(13)

Where dij is the distance between adjacent flight served. yi,j,k represents the vehicle k has finished service for the previous flight i and then service for the next flight j. yo,j,k means that a new vehicle k is sent out from parking lot, and begins service for the flight j. yi,o,k means that the vehicle k completes service for the flight i, and exits service. D is the number of the vehicles sent out. xik is a flag variable. xik is set to 1 if the vehicle k refuels for the flight i, else xik is 0. E represents the maximum number of service times for each vehicle. Ai indicates the earliest start time for the service on the flight i. Bi indicates the latest time for the service on the flight i. sik indicates the time when the vehicle k arrives at the stop of the flight i. ti is time how long it takes for to the vehicle complete refueling service for the flight i. tij indicates the time of the vehicle from the stop of the flight i to the stop of the flight j. f(x) is the objective function in (1). Equation (2) indicates the total distance of the refueling vehicle flight service are minimum. Equation (3) indicates the minimum number of dispatched vehicles. Equation (4) represents the difference in the number of tasks between each of the refueling vehicle is minimize. Equation (5) represents the minimum difference for each vehicle task. Equation (6) means the restraint of service times for each vehicle. Equation (7) indicates capacity constraint of the refueling vehicle. Equation (8) indicates that all flights must receive refueling service within its specified time window. Equation (9) translates the end of the previous flight is earlier than the start of the next flight. Equation (10) indicates the range of yi,o,k value. yi,o,k is 1 if the vehicle k starts from the parking lot for the flight i service. Equation (11) means the range of yo,j,k value. yo,j,k is 1 if the vehicle k return to the parking lot after serves flight j. Equation (12) indicates the range of xik value. xik is equals 1 if the vehicle k provides service for the flight i. Equation (13) indicates the range of yi,j,k value. yi,j,k is 1 if the vehicle k serves the flight i firstly, and then serves the next flight j.

3 Airport Vehicle Scheduling Algorithm Based on Greedy Strategy (AVSAGS)

This section firstly gives the idea of the algorithm, then defines the evaluation function used in the algorithm, and finally describes the process of the algorithm.

3.1 The AVSAGS Idea

The refueling service of different flights is connected, and the flight service sequences of the vehicles are planned. In the process of looking for the optimal service sequence, an evaluation function (VF) is designed while considering the two factors, i.e. the distance between the vehicles and flight, and the arrival time difference between the arrival time of the tanker and the upper limit of the flight service time window. A flight is served by a candidate vehicle with the minimum VF value. In this way we could get the vehicle scheduling order so that the smallest total travel distance of the vehicle is obtained. By limiting the maximum number of refueling vehicles, the mission of the refueling vehicle is balanced, thus the number of refueling vehicles reaches the smallest value.

3.2 Evaluation Function Index

Two goals of airport vehicle scheduling are considered for the proposed algorithm. The first goal is to minimize the sum of service distances for the fligh, and the second one is that times of the vehicles to be sent out is required to be minimized. To make the vehicle as early as possible for the flight service, it will enable the vehicle to serve more flights for a period of time, so as to achieve the target of fewer vehicles. The two goals are relevant, the nearest flight is always served by the same vehicle while considering time window. Because the two goals are very important which affecting the vehicle scheduling in actual situations, we propose the evaluation function (VF) to choose the flight to serve as early as possible while considering time window of flight service. The evaluation function (W) is defined as follows.

$$ W = d_{jk} + \alpha \times T_{w} + \beta \times T_{d} $$
(14)
$$ Tw\, = \,\left\{ {\begin{array}{*{20}l} {A_{i} \, - \,s_{ik} ,} \hfill & {T_{w} \, > \, 0} \hfill \\ {0,} \hfill & {T_{w} \, < \, 0} \hfill \\ \end{array} } \right. $$
(15)
$$ T_{d} \, = \,\left\{ {\begin{array}{*{20}l} {s_{ik} \, - \,A_{i} ,} \hfill & {T_{d} \, > \,0} \hfill \\ {0,} \hfill & {T_{d} \, < \, 0} \hfill \\ \end{array} } \right. $$
(16)

Where dkj represents the distance between the refueling vehicle and the flight, α represents the evaluation factor waiting for the refueling vehicle, β represents the evaluation factor for the delay of the refueling vehicle. Tw indicates the wait time of the vehicle, Td is the delay time of the vehicle Ai means the earliest time for flight to be served. Ski represents the time for the vehicle to get to the flight; Eq. (14) defines evaluation function (W) that considers two factors, i.e., vehicle traveling distance and delay time. W is used as the standard for evaluating the quality of scheduling strategy. The smaller of the VF (W) value is, the sooner the selected flight to be served is. Equations (15) and (16) give computation formula of Tw and Td.

3.3 The AVSAGS Description

Based on the above analysis, the AVSAGS can be described as follows.

  • Step 1. The departure flights are arranged on the timetable to form the sequence of services (L1).

  • Step 2. Taking time window constraints as the criterion, the first flight which has not been served is selected to check. Calculate the time when the vehicle arrives at the flight, and if the refueling vehicles do not satisfy the time window [Ai,Bi], then the new one is dispatched; and flight service is joined into the vehicle transmission chain; and go to Step 4. Else continue.

  • Step 3. If only one vehicle meets the time window [Ai,Bi], then flight service is joined into the vehicle transmission chain; Else there are multiple vehicles meet the time window constraint simultaneously, the evaluation function is calculated according to Eq. (14), and the vehicle with the smallest VF value is added.

  • Step 4. In accordance with step two and step three, refueling tasks of flight service is added one by one.

  • Step 5. When the capacity of the transmission chain of the vehicle reaches the maximum allowable service number, the new task is terminated, and the vehicle returns to the parking lot. After a period of rest, the vehicle can be dispatched again.

  • Step 6. Repeat the above steps to the vacant flight to be served.

The flow chart of the algorithm is shown in Fig. 1.

Fig. 1.
figure 1

Flow chart of the AVSAGS

Full size image

4 Results and Discussion

This paper selects the actual flight data of an airport in January 22nd of 2017 year to perform experiment for the proposed algorithm. The airport’s daily arrivals and flights amount to about 250 sorties according to the airport data. As the incoming flights do not need refueling service, 115 departure flights are selected to test.

4.1 Refueling Time

The refueling time required for a flight is related to the aircraft type. According to the number of aircraft passenger seats, China’s civil aviation aircraft is divided into large, medium and small types. Flight with the number of passengers seats below 100 seats belongs to small type; flight with 100 to 200 seats belongs to medium type; and flight with more than 200 seats belongs to large type. After analyzing the flight data, there are Airbus A380 series belonging to large type; A320, A319 series belong to medium type; CRJ-900 series, ERJ-190 series, ARJ21 belong to small type. Based on the flight history refueling data, average refueling time is given as the time required for each flight type, as shown in Table 1.

Table 1. Refueling time of flight type
Full size table

4.2 Airport Stand Distance Matrix

The airport stand is the location of the flight at the airport. The distance between different stops affects the driving time of the vehicle. There are 37 stands in the airport, which are distributed in 3 regions of T1, T2 terminal and parking apron. According to the field calculation, the distance between adjacent parking stands is 40 m. In order to ensure the safety of the airport, the civil aviation authority stipulates that all ground support vehicles at the airport must travel along the prescribed route and cannot enter the other airport areas. The 101 to 108 stands are located in the T1 terminal, and the 109–116 stands are located in the T2 terminal. The remaining is distributed on the parking apron, and the airport stands are shown in Fig. 2.

Fig. 2.
figure 2

Airport stands distribution

Full size image

According to Fig. 2, the distance matrix among airport stands can be obtained, in which the parking lot is expressed using O. The distance matrix of the part of the stands is shown in Table 2 as shown below.

Table 2. Distance matrix of partial stands
Full size table

4.3 Time Window for Refueling Service

The time window of the refueling is a time range between the earliest start of the refueling service and the latest start of the refueling service for the flight. If the vehicle arrives before the earliest start of the refueling time, it needs to wait. If the vehicle arrives after the flight starts at the latest, the flight may be delayed.

According to the relevant documents [10], civil aviation flight must complete fuel refueling operations five minutes before the passengers start boarding. In special circumstances, fuel injection should be completed five minutes before the aircraft is expected to leave. Passengers generally start boarding ahead of 30 min.

The departure flights are divided into two types, i.e. originating flight and passing flight. Their time windows are also different. The former should be served ahead of time before the passengers start boarding; the latter needs be served immediately. The two types of flights time windows of refueling service are as follows.

Service time window for passing flight:

$$ A_{i} = t_{arr} $$
(17)
$$ B_{i} = t_{arr} + 1 0 $$
(18)

Service time window for originating flight:

$$ A_{i} = t_{d} - t_{i} - 35 $$
(19)
$$ B_{i} = t_{d} - t_{i} - 5 $$
(20)

where tarr is arrival time of passing flight, td is the departure time of the flight plan, ti represents the time that service for the flight i. Equation (17) means the time window lower limit of the passing flight is at the arrival time, Eq. (18) means the time window upper limit of the passing flight, Eq. (19) represents the time window upper limit of the originating flight, Eq. (20) represents the time window lower limit of the originating flight. Part of flight service time window for part of the flight, as shown in Table 3.

Table 3. Part of flight service time window
Full size table

4.4 Experimental Data and Analysis

The experimental data are obtained by using the proposed algorithm designed for solving the ARVSP with the above data. Service sequence for a vehicle starts and ends using 0 which means the vehicle starting from the parking lot, providing refueling service for the flights, and returning to the parking lot. The time table for flight service sequence is shown in Table 4. The distance of the driving path and the service number for the vehicles are shown in Table 5.

Table 4. Flight service sequence
Full size table
Table 5. The distance of the driving path and the service number for the vehicles
Full size table

Since no flight need s to be refueled before 7:55, so the flight service sequence was empty from 0:00 AM to 7:55 AM. At 7:55 AM, the first flight 101 needs refueling service, and the 101 flight is added to the first flight service sequence. Because it is a passing flight, The service sequence starts at 7:55 and ends at 8:20. From 8:05 to 8:35, there are 102, 103 and 104 flights which are in service waiting flights. While considering time watch for 102 flight, a new vehicle needs to assign, and flights are added to different service sequences. The results of other service sequences are no longer stated in detail.

The total distance of the refueling vehicle is 61.920 km, which is 30% less than that traditional manual Scheduling (88.560 km) by the results of the experiment. The number of total vehicle dispatched are 24 times that decrease 79.1% compared with the traditional manual scheduling of 115 times. And only five vehicles are needed to provide service for the flights.

5 Conclusion

In this paper, the airport refueling vehicle scheduling problem is analyzed, and its mathematical model is established. A scheduling algorithm based on greedy strategy is designed for solving the model. The test results show that the proposed algorithm has a significant improvement in aircraft vehicle scheduling and service cost reduction.

In the future research, more scenarios and strategies are to be considered so that the model and the algorithm could handle more complex cases such as flight delays and dynamic scheduling. Meanwhile, we apply the proposed algorithm into an actual practice.