A Family of Heuristic-Based Inequalities for Maximizing Overall Safety Margins in Aircraft Parking Stands Arrangement Problems

Abstract

We consider the problem of arranging a set of aircraft in a maintenance hangar operated by an independent aircraft service provider. The overall safety margins of the parking layout need to be maximized within the limited available space, measured by the weighted sum of the individual discrete safety margins of each aircraft. A mixed-integer linear programming model is developed, and the positions of the aircraft are determined by the position-controlling binary variables associated with a set of revised No-Fit Polygons (NFPs). Due to the nonconvex irregular shape of aircraft, the model involves a great number of binary variables associated with the revised NFP. The default branch-and-bound algorithm is inefficient in solving such a model as the infeasibility information of the precedent visited solution cannot be directly utilized by the default method to update the bounds. A heuristic algorithm is developed to provide practical solutions, and the intermediate infeasible solutions identified during searching are utilized to develop valid and approximate inequalities, tightening the optimality gap. The computational results demonstrate that the addition of inequalities improves the computational efficiency in solving a wide range of instances and in tightening the optimality gap while the stopping criterion is met.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The problem of arranging a set of aircraft of different sizes in a maintenance hangar arises due to the increasing outsourcing of aircraft hangar maintenance activities to independent aircraft service companies [1, 2]. The aircraft maintenance problem can be viewed from different perspectives, including the airline company, the line maintenance service provider, the hangar maintenance service provider, and the military mission department [2–12]. From the perspective of the aircraft service company, after receiving aircraft maintenance requests from a number of clients, one needs to consider which subset of maintenance requests to serve during a planning period to attain maximal profit, as well as to come up with an aircraft parking layout to minimize the risk of collision during the movement operations of the aircraft. In actual operations, the practitioner typically gathers a subset of aircraft with similar maintenance times in a batch and then arranges the batch in the maintenance hangar to facilitate the maintenance procedures. The literature related to the maintenance scheduling problem in the context of an aircraft maintenance base operated by single airline seldom considers the variation of hangar capacity [13], i.e., the number of aircraft that can be accommodated in the hangar at the same time, along the planning period, as the parking stands have been predetermined at the hangar design stage due to the limited type of aircraft to be maintained. However, as the maintenance base operated by the maintenance service company receives aircraft of different sizes within the planning period, the hangar capacity varies from time to time, and therefore optimizing the hangar space within the planning period is essential. The aircraft parking stands arrangement problem (PSAP) aims to maximize the hangar utilization with maximal overall safety margins for the aircraft placed in the hangar. After determining the aircraft to be parked in the hangar, we aim at finalizing the aircraft parking layout by arranging aircraft parking with maximal safety margins [14]. Given the complexity of the problem, we aim to enhance the computational efficiency of heuristic algorithm used in previous studies [14] by developing a family of inequalities based on the intermediate infeasible solutions during the process of heuristic searching for determining the optimal parking layout with maximal overall safety margins or tightening the optimality gap for the challenging problems. Given a set of aircraft $P^{\prime }$ to be served, the objective of the problem is maximizing the overall safety margins measured by the weighted sum of the individual safety margins of each aircraft, preventing the overall risk of collision during the batch movement operation prior to and after the maintenance operations in the hangar.

The PSAP has not been extensively studied in the literature and the most closely related reference we are aware of refers to the irregular item packing problems [14], according to the classification of by Wäscher et al. [15]. The problem studied here can be regarded as an extended version of the two-dimensional irregular item packing problem in a fixed dimension container [15, 16], since aircraft need to be modelled as irregular polygons to accurately measure the capacity of the hangar accommodating the aircraft. PSAP is different from the general packing problem which aims to arrange the items to be as compact as possible. Instead, PSAP aims to optimally arrange the parking position of the aircraft while reserving a moderate distance between each pair of aircraft. The item cutting and packing problem in two-dimensional space has been widely studied in the literature because of its practical use in various industries, and such packing problems can be classified as either regular items packing problems or irregular items packing problems [15, 17–24]. Many mathematical formulations solving irregular items packing problems have been proposed in the literature [25–30]. The No-Fit Polygon (NFP) has been widely used in detecting if two irregular items overlap with each other [31, 32], while other approaches also exist [33]. The main difficulty in tackling irregular shape item problems is the great number of binary variables determining the relative position between each pair of aircraft in the container. Generally, solving an instance including more than 10 irregular items becomes challenging and intractable with the current approaches [26]. In our problem, we assume that each aircraft has to select an individual safety margin within the admissible discrete range $lb$ and $ub$. In this regard, there are a number of $\left|P^{\prime }\right|·(ub-lb+\mathrm{1})$ NFPs involved in each problem instance for the proposed problem, which are extremely challenging using the existing approach.

Many heuristic algorithms have been developed to utilize infeasible solutions that are identified during the searching process. For example, some researchers focusing on the vehicle routing problem (VRP) with loading and unloading constraints in a two-dimensional space adopted infeasible solutions to develop heuristics, and there are some similarities with the problem studied in this paper. Specifically, both these two problems have large numbers of candidate solutions to explore and the feasibility of the candidate solution can be examined only after fixing all decisions. To compare these two problems, the VRP has to determine the routing of each vehicle first, and the parking stand arrangement problem has to determine the individual safety margins for each aircraft first. Afterwards, there is a set of decision variables determining the position of the items to be placed in the container in both problems afterwards. As the items are arranged in a two-dimensional space in both problems, the feasibility of the solution cannot be directly checked by a single resource constraint as in classic assignment problem but needs to be examined with a set of geometrical constraints, including nonoverlapping constraints and boundary constraints. To utilize these infeasible solutions identified during the searching process, one can eliminate a set of unvisited unpromising candidate solutions that has the same pattern of those identified infeasible solutions. In particular, the identified infeasible solutions are recorded in a list; then the respective inequalities are generated and inputted into the mathematical model according to the information in the list, so as to eliminate unvisited unpromising solutions with the same patterns. For example, Felipe et al. [34] used the intermediate infeasible solution to diversify the search process in a heuristic algorithm, tackling the vehicle routing problem with precedence and loading constraints. Iori et al. [35] proposed an exact approach based on a branch-and-cut algorithm to solve the vehicle routing problem with two-dimensional constraints. The infeasible route identified during the feasibility checking process is recorded and converted to a cut, which is added to the original problem. Hokama et al. [36] developed a branch-and-cut algorithm to deal with the unpackable path generated from the master problem. They used a hash table to record the feasibility information for the route or subroute visited earlier. The feasibility of the tentative route can be examined by comparing the elements in the route. If the tentative route has the same elements as the infeasible subroute recorded in the hash table, the tentative route can be referred to as an infeasible route without further examination by the branch-and-bound algorithm. Some heuristic searching strategies exist to detect the feasibility of a given solution in the packing problem, such as sequence based heuristics [37], the robust hyperheuristic algorithm [38] for the rectangular packing problem, and the recursive algorithm for the rectangular guillotine strip packing problem [39, 40]. However, using these methods may lead to being trapped in local optima as the complexity of the polygons increases. The technical roadmap is organized as follows: a mathematical model is firstly presented to formulate the aircraft parking stands arrangement problem in the context of aircraft maintenance service providers. Due to the large number of binary variables involved, the mathematical model can only solve the small problem instance to optimal within a reasonable time, and the medium- to large-sized instances are intractable, solely by the mathematical model. To provide a warm start and tighten the bounds of the mathematical model, a heuristic algorithm aiming at tackling large-scale instances is developed, which uses the mathematical model as the foundation. In detail, the heuristic algorithm determines a candidate solution first, and then a branch-and-bound based feasibility checking approach is incorporated in the heuristic algorithm to examine the feasibility of a given combination of individual safety margins for the set of aircraft to be maintained in the hangar. To examine the feasibility of the tentative solution, the feasibility check approach inputs the tentative solution into the mathematical model with all safety-margin-related decision variables fixed in the model and then implements the model to check whether infeasibility returns. The heuristic adjusts the candidate solution if the previous candidate solutions are infeasible, and the warm start solution for the mathematical model would be determined by the end of the heuristic. During the feasibility checking process, the identified infeasible solutions are recorded to further prune down the set of infeasible solutions by adding several forms of inequalities to exclude infeasible combinations, before initiating running the original model so as to enhance the efficiency of mathematical model. Specifically, a set of inequalities is developed to convert the recorded infeasible solutions that were identified during the heuristic searching process as constraints in the model. The developed approach has been extensively tested on problem instances derived from the actual situation in an aircraft maintenance service company.

The remainder of this paper is organized as follows. Section 2 describes the problem and the notation and formulation of the mathematical model, fundamental to the heuristic and inequalities. Moreover, the complexity of the problem is further analysed in this section. Section 3 presents the heuristic approach and the inequalities derived from the infeasible solutions during the heuristic search process. Section 4 examines the computational results, and the conclusions are drawn in Section 5.

2. Aircraft Parking Stands Arrangement Problem

2.1. Problem Description

The proposed problem can be defined as follows: we are given a subset of aircraft of different shapes to be serviced during a short planning period, and these aircraft can be feasibly arranged in the given maintenance hangar satisfying the minimal safety margin requirements; i.e., the shortest distance between each pair of aircraft is at least equal to or larger than the minimal safety margin. Figure 1 presents a typical maintenance hangar operated by an independent aircraft base maintenance company serving different clients and accommodating aircraft of different shapes and sizes. In the problem, each aircraft has to select an individual safety margin to utilize the unused space in the hangar so as to minimize the risk of collision during the movement and maintenance operations. Two hangar layouts both can accommodate the same set of aircraft while the assigned position for each aircraft is different. In Figure 1(a), the aircraft can be feasibly arranged in the maintenance hangar while they are placed in a concentrated manner even if there is a lot of unused space (the shadow region in Figure 1(a)). In this regard, the problem studied in this paper aims to enlarge the safety margin of each aircraft so as to make the most of the empty space (Figure 1(b)). The safety margin is defined as the shortest distance between two aircraft in the hangar, and the problem aims to have a maximal overall safety margin measured by the weighted sum of the individual safety margins of each aircraft placed in the hangar, as described in [14]. In an actual situation, large-sized aircraft bear more risk of collision, compared with the small- and medium-sized aircraft, as larger aircraft are less manoeuvrable than smaller ones. In this regard, the larger aircraft are given higher priority in reserving larger safety margins in practice, and the weight of the individual safety margin in the objective function is associated with the area of each aircraft. In the developed mathematical model, the aircraft safety margin is discretized for the trade-off between accuracy and computational efficiency, and we also prescribe the individual lower bound ($l{b}_i$) and the upper bound ($l{b}_i$) of the safety margin to represent the minimal safety requirement and the largest safety margin that contribute the overall safety margins, respectively, as reserving too high a safety margin does not necessarily contribute to overall safety but only increases the number of binary variables in solving the problem.

[figure omitted; refer to PDF]

The methodology of preventing irregular items from overlapping refers to the mechanism of No-Fit Polygons [31, 32, 41–43], as shown in Figure 2(a): P1 and P2 are two simple polygons, and we denote the bottom left corner of polygon P2 as its reference point, for illustration purposes. To generate NFP between P1 and P2, polygon P2 slides along the boundary of polygon P1 while keeping in touch with P1, and the trajectory of the reference point of polygon P2 is recorded as the No-Fit Polygon between these two polygons. To prevent overlap, the reference point of P2 must be placed outside or on the boundary of the No-Fit Polygon. To characterize the NFP in the linear programming model, the area outside the NFP is partitioned into several horizontal slices and each horizontal slice is formed by several lines which can be denoted by a linear equation. Accordingly, the equation ${\alpha }_{ij}^{kf}(x_j-x_i)+{\beta }_{ij}^{kf}(y_j-y_i)=q_{ij}^{kf}$ is used to denote the fth line forming the kth slice outside the NFP [25, 27]. If the reference point of polygon j is placed on slice k, then there are several constraints in the form of ${\alpha }_{ij}^{kf}(x_j-x_i)+{\beta }_{ij}^{kf}(y_j-y_i)\le q_{ij}^{kf}$, denoting that the slice k is activated to impose the relative position requirement. For the No-Fit Polygons between each pair of aircraft, we denote the reference point of the aircraft by the middle of the bottom edge of the aircraft because of its symmetrical shape. To enforce the prescribed safety margin between each pair of aircraft, we move the edges of the original NFP outward, with a distance equal to the prescribed safety margin (Figure 2(b)), and the reference point of aircraft j must be placed outside or on the boundary of the revised NFP. For a pair of aircraft, the safety margin used to separate them is determined by the aircraft with the larger safety margin in that pair, as shown in Figure 2(b). Aircraft j has larger individual safety margin than aircraft i and therefore the revised NFP associated with the safety margin of the aircraft is activated to separate the pair.

[figure omitted; refer to PDF]

2.2. MILP Formulation for the Problem

We list the notations and decision variables for the formulation of the problem.

Notations

 

$W$ : width of hangar

 

$H$ : length of hangar

 

$Are{a}_i$ : area of aircraft i

 

$w_i$ : width of aircraft i

 

$h_i$ : length of aircraft i

Decision Variables

 

$z_i^n$ : binary decision variable that takes the value 1 if aircraft i is placed in hangar with safety margin n, and 0 otherwise

 

$x_i$ : position of reference point of aircraft i on x-axis in two-dimensional space

 

$y_i$ : position of reference point of aircraft i on y-axis in two-dimensional space

 

$b_{ijk}^n$ : binary decision variable that takes the value 1 if the reference point of aircraft j is placed into slice $s_{ijn}^k$, and 0 otherwise

 

$g_{ij}^n$ : auxiliary decision variable that takes value 1 if the shortest distance between aircraft i and j is n and $NF{P}_{ij}^n$ is activated, and 0 otherwise.

Objective: Maximize Overall Safety Margin$$\begin{array}{}\text{(1)}& \max {\displaystyle \sum }_{i\in P^{\prime }}\hspace{0.17em}{\displaystyle \sum }_{n=lb}^{ub}{z}_i^n·n·Are{a}_i\end{array}$$s.t.$$\begin{array}{}\text{(2)}& x_i+\frac{w_i}{\mathrm{2}}\le W,\hspace{1em}\forall i\in P^{\prime }\text{(3)}& x_i\ge \frac{w_i}{\mathrm{2}},\hspace{1em}\forall i\in P^{\prime }\text{(4)}& y_i+h_i\le H,\hspace{1em}\forall i\in P^{\prime }\text{(5)}& {\alpha }_{ijn}^{kf}\left(x_j-x_i\right)+{\beta }_{ijn}^{kf}\left(x_j-x_i\right)\le q_{ijn}^{kf}+M·\left(\mathrm{1}-b_{ijk}^n\right),\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}\forall k=\mathrm{1,2},\dots ,m_{ij}^n,\hspace{0.17em}\hspace{0.17em}\forall f=\mathrm{1,2},\dots ,t_{ijn}^k,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(6)}& {\displaystyle \sum }_{k=\mathrm{1}}^{m_{ijn}}{b}_{ijk}^n=g_{ij}^n,\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(7)}& g_{ij}^n\ge z_i^n-{\displaystyle \sum }_{n=n+\mathrm{1}}^{ub}{z}_j^n,\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(8)}& g_{ij}^n\ge z_j^n-{\displaystyle \sum }_{n=n+\mathrm{1}}^{ub}{z}_i^n,\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(9)}& g_{ij}^n\le \mathrm{1}-{\displaystyle \sum }_{n=n+\mathrm{1}}^{ub}{z}_i^n,\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(10)}& g_{ij}^n\le \mathrm{1}-{\displaystyle \sum }_{n=n+\mathrm{1}}^{ub}{z}_j^n,\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(11)}& {\displaystyle \sum }_{n=lb}^{ub}{g}_{ij}^n=\mathrm{1},\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\}\text{,}\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(12)}& {\displaystyle \sum }_{n=lb}^{ub}{z}_i^n=\mathrm{1},\hspace{1em}\forall i\in P^{\prime }\text{(13)}& \mathrm{1}-z_i^n\ge {\displaystyle \sum }_{k=n+\mathrm{1}}^{ub}{z}_j^k,\hspace{1em}i,j\in A_u,\hspace{0.17em}\hspace{0.17em}i<j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(14)}& b_{ijk}^n\in \left\{\mathrm{0,1}\right\}\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}k=\mathrm{1,2},\dots ,m_{ijn},\text{(15)}& g_{ij}^n\in \left\{\mathrm{0,1}\right\}\hspace{1em}\forall i,j\in P^{\prime },\hspace{0.17em}\hspace{0.17em}i\ne j,\hspace{0.17em}\hspace{0.17em}n=\max \left\{l{b}_i,l{b}_j\right\},\dots ,\max \left\{u{b}_i,u{b}_j\right\}\text{(16)}& x_i,y_i\ge \mathrm{0}\hspace{1em}\forall i\in P^{\prime }\end{array}$$In the problem formulation, the objective function (1) maximizes the overall safety margins. Constraint sets (2)-(4) are bound constraints. Constraint (5) is a nonoverlapping constraint that separates each pair of aircraft by the safety margin n. Variables $b_{ijk}^n$ are binary and one of them must take value 1 if $NF{P}_{ij}^n$ is activated in separating aircraft i and j. Constraint (12) prescribes that each aircraft must take a safety margin value within the prescribed bounds of each pair of aircraft. $g_{ij}^n$ is the auxiliary variable used to activate/deactivate the revised NFP with safety margin n. Constraint (11) imposes the condition that there should be only one revised NFP activated to separate each pair of aircraft. According to the description of the problem, the safety margin used to separate aircraft i and j is determined by the larger individual safety margin in this pair, and constraints (7)–(10) imply that the $g_{ij}^n$ associated with the revised NFP with safety margin n is activated if and only if one aircraft has a safety margin n and the other has a safety margin smaller than or equal to n; then constraint (6) activates/deactivates the respective revised NFP with binary variable $g_{ij}^n$, respectively. Constraints (14)-(15) indicate that $b_{ijk}^n$ and $g_{ij}^n$ are binary variables. Constraint (13) is imposed to avoid duplicate solutions and prescribes that the safety margins for the aircraft belonging to the same aircraft type are in a decreasing order: $\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{i}{\mathrm{n}}_{i\mathrm{1}}\ge \mathrm{m}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{i}{\mathrm{n}}_{i\mathrm{2}}\ge \cdots \ge \mathrm{m}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{i}{\mathrm{n}}_{i\mathrm{3}}$.

3. Solution Methodology

3.1. Heuristic Algorithm

The feasibility of a tentative solution (a given combination of safety margins $z_i^n$)) is determined by fixing a set of position-controlling binary variables $b_{ijk}^n$ for every pair of aircraft placed in the hangar. When the problem scale becomes larger, the default branch-and-bound provided by a solver such as CPLEX becomes inefficient, as the optimizer would try to find the set of safety margins $z_i^n$ that achieves maximum overall safety margins as the promising tentative solution at first, while such a tentative solution reserves too large a distance between each pair of aircraft that exceeds the capacity of the hangar. However, the infeasibility of the tentative solution can only be confirmed by the branch-and-bound when all $b_{ijk}^n$ values for every pair of aircraft have been fathomed; however such search progress is time-consuming for the large-scale instance mentioned above. In this regard, a heuristic algorithm is firstly proposed to provide a practical solution for the problem within a reasonable time in the actual situation; then the mathematical model is tightened by recording the intermediate solutions for later use in the development of inequalities and in providing a moderate upper bound of safety margin, known as threshold of the safety margin, as well. Therefore, the heuristic provides fundamental information for the development of the inequalities discussed later.

The notations and the flowchart of the heuristic algorithm are presented in Table 1 and Figure 3, respectively.

Table 1

Notations in the heuristic algorithm.

Heuristic algorithm for problem
Notations	Meanings
P’	set of aircraft with maximal overall profit and satisfying minimal safety requirement
totalorder	number of aircraft in set P’
s(i)	the safety margin of aircraft i, i$\mathrm{\hspace{0.17em}\hspace{0.17em}}\in P^{\prime }$
Prioirty_List	set of aircraft
Aug_List	set of aircraft
j,k	notation of aircraft, j, k$\mathrm{\hspace{0.17em}\hspace{0.17em}}\in$ Prioirty_List
l	notation of aircraft, l;$\in$ Aug_List
best-known fitness	the best-known fitness value
current fitness	the fitness value of the decision under current iteration
ub i ,lb i	the lower bound and the upper bound of safety margin associated with aircraft i, respectively
th	the threshold value of safety margin
$$u_i^m$$	safety margin of aircraft i under infeasible solution m
R	set of infeasible solutions at overall augmentation stage and individual decrementation stage
r	infeasible solution r, r $\in$ R
Q	set of infeasible solutions at individual augmentation stage
q	infeasible solution q, q $\in$ Q
Input: Hangar Length L, Hangar Width W, Geometry Information of Aircraft (length and width of aircraft), Safety Margin Upper Bound ubi, Safety Margin Lower Bound lbi, Set Original NPF, Set P’
Output: Safety Margin s(i) for aircraft i$\mathrm{\hspace{0.17em}\hspace{0.17em}}\in$P’, Set of infeasible solution Q and R, threshold value th

[figure omitted; refer to PDF]

The procedures shown in Figure 3 can be generalized in three steps. The feasibility of a given tentative solution is examined by creating an MIP model feasibility check, which tries to place all aircraft with the revised NFPs determined by a set of safety margins. If the feasibility check model is able to accommodate all aircraft in set $P^{\prime }$, then the hangar is feasible for the problem. Otherwise, such a tentative solution is infeasible because there is at least one aircraft that cannot be placed in the hangar with the given safety margin in the tentative solution. The heuristic algorithm consists of three main steps.

Step 1.

The algorithm first calls for the feasibility check and places the set of aircraft in $P^{\prime }$ with a combination of safety margins $z_i^n$ for $i\in P^{\prime }$. The initial individual safety margins for each aircraft is initially set to be the lower bound of the safety margin of individual aircraft i (lb_i). If a feasible solution returns, the respective objective value (1) determined by the tentative solution examined in this iteration can be updated as the lower bound of the model in Section 2.2. After that, the safety margins of all those aircraft are augmented until returning an infeasible solution, with the highest individual safety margin in this infeasible solution defined as the threshold of the safety margin of the current problem.

Step 2.

The safety margins of some aircraft need to be reduced in order to obtain a feasible parking plan again. Step 2 is called the individual safety margin decrementation and augmentation stage. Firstly, the priority of each aircraft is assigned according to the physical size of the aircraft (larger aircraft are assigned with higher priorities), and the priority value of each aircraft is kept constant during the heuristic search process. For easy understanding, we can simply regard the value of the priority of each aircraft to be equal to its size $Are{a}_i$. Afterwards, all aircraft in $P^{\prime }$ are put into the set Priority_List , and the Priority_List acts as a sequence of adjustment of individual safety margins. According to the expression of the objective function, the weightiness of the individual aircraft safety margin that each aircraft contributes depends on the physical size ($Are{a}_i$) of each aircraft. Therefore, larger aircraft have higher priority in getting larger safety margin to contribute more to the objective function, and the largest size aircraft’s safety margin should be considered decremented at last after decrementing the safety margins of aircraft with lower priorities and no feasible solution returns. In this connection, the first adjusting strategy is that the individual safety margin for the aircraft with the lowest priority in the Priority_List is decremented first until a feasible solution returns, or the aircraft is moved to the waiting list set, i.e., Aug_List. If it reaches the lower bound of safety margin associated with that aircraft then the algorithm selects another aircraft with lowest priority in the Prioirty_List instead. After obtaining a feasible solution after decrementation, the algorithm selects the aircraft with highest priority for safety margin augmentation from the Priority_List and checks the feasibility of the tentative solution. If the infeasible solution returns, such an aircraft is removed from further augmentation consideration. The algorithm in this step continues until the Priority_List is empty.

Step 3.

After Step 2, the algorithm again obtains a set of aircraft pending for safety margins augmentation again in the waiting list Aug_List. The adjustment strategy in this step is that the safety margin for aircraft with the highest priority in Aug_List is augmented first, until an infeasible solution returns, and such an aircraft is removed from the Aug_List for further consideration of safety margin augmentation.

3.2. Inequalities for Problem

3.2.1. Valid Inequalities

We utilize the infeasible solutions derived from the heuristic search and propose four inequalities to tighten the upper bound of the problem. After presenting the inequalities, we provide examples to illustrate the idea of the respective inequalities accordingly. The sets R and Q in the parameter list of the heuristic denote the infeasible solutions under Step 2 (individual safety margin decrementation/augmentation in Priority_List set) and Step 3 (individual safety margin augmentation in Aug_List set) of heuristic algorithm, respectively. As the inequalities derived from the infeasible solutions of Steps 2 and 3 in the heuristic algorithm are presented with different expressions, we use sets R and Q to differentiate the infeasible solutions to be inputted in inequalities 2 and 3, respectively. We find that when the safety margins reach a relatively large value, i.e., a threshold value, during the overall augmentation stage, not all the aircraft in the subset can be feasibly placed in the hangar. Therefore, a safety margin that is larger than or equal to the threshold value cannot obtain a feasible parking plan. Inequality 1 expressed in (17), i.e., threshold inequality, is proposed to remove infeasible solutions that exceed the threshold value. Example 1 shows how inequality 1 eliminates the set of infeasible solutions that exceeds the threshold value.$$\begin{array}{}\text{(17)}& {\displaystyle \sum }_{i\in P^{\prime }}\hspace{0.17em}{\displaystyle \sum }_{n=th}^{u{b}_i}{z}_i^n\le \left(totalorder-\mathrm{1}\right)\end{array}$$

Example 1.

Assume that an instance with three aircraft has a feasible parking plan when the safety margin for all aircraft is assigned a value n, but the feasibility check cannot find a feasible solution when all the safety margins are augmented to a value n+1. In this case, the value n+1 is the threshold for augmentation. Therefore, a bunch of combinations can be excluded from the solution space. Specifically, $\left\{n+\mathrm{1},n+\mathrm{1},n+\mathrm{1}\right\}$, $\left\{n+\mathrm{2},n+\mathrm{3},n+\mathrm{1}\right\}$, and $\left\{n+\mathrm{3},n+\mathrm{4},n+\mathrm{2}\right\}$ (the numbers in brackets denote the respective safety margin for three aircraft) can be excluded.

However, there are still large numbers of infeasible solutions left in the solution space since the threshold inequality 1 only eliminates the infeasible solutions such that each safety margin exceeds the threshold value. Therefore, we further propose the two inequalities 2 and 3 expressed in (18)-(19) to remove infeasible solutions during the individual adjustment stage when an infeasible solution is found. $$\begin{array}{}\text{(18)}& {\displaystyle \sum }_{i\in P^{\prime }}\hspace{0.17em}{\displaystyle \sum }_{n=u_i^r}^{u{b}_i}{z}_i^n\le \left(totalorder-\mathrm{1}\right),\hspace{1em}\forall r\in R\text{(19)}& {\displaystyle \sum }_{n=u_l^q}^{u{b}_i}{z}_l^n\le \left(totalorder-\mathrm{1}\right)-{\displaystyle \sum }_{i\in P^{\prime }\setminus \left\{q\right\}}{z}_i^{u_i^q},\hspace{1em}\forall q\in Q\end{array}$$Inequality 2 is derived during the process of the safety margin decrementation/augmentation stage at Step 2 of the heuristic. We denote the set of the infeasible solutions identified during the individual safety margin decrementation/augmentation at Step 2 as R. When the safety margin of each aircraft reaches the threshold value and an infeasible solution returns from the feasibility check, the decrementation of the safety margin begins and aircraft i with the lowest priority in the Priority_List is decremented at first. Therefore, we can infer that before obtaining a feasible solution, any augmentation of the safety margin of any aircraft is infeasible, and we denote S as the set of safety margins in that iteration. Similarly, selecting the highest priority aircraft in the Priority_List for safety margin augmentation with the infeasible solution in Step 2 also implies that any augmentation of the safety margin of any aircraft is infeasible. Moreover, inequality 3 is identified at the individual safety margin augmentation in Step 3: the safety margin of the aircraft with the highest priority in the Aug_List is augmented first (denoted as l in (19)). If the safety margin of aircraft i with the highest priority is augmented to $s$ and the feasibility check finds it infeasible, then any safety margin value larger than $s$ for aircraft i cannot produce a feasible solution, and we denote Q as the set of infeasible solutions identified during the individual safety margin augmentation stage. Example 2 shows how inequalities 2 and 3 eliminate the unvisited infeasible solution by utilizing the intermediate visited infeasible solution during the individual safety margin decrementation and augmentation stage in the heuristic algorithm.

Example 2.

Assume an instance with three aircraft has a threshold value n+1. Taking the safety margin decrementation in Step 2 as an example, a feasible solution can be found after several individual safety margin decrementations, and the safety margins are assumed to be $\left\{\mathrm{1,3},n+\mathrm{1}\right\}$. If the priorities of these three aircraft are in increasing order, we can infer that any combination when the safety margin of the third aircraft is n+1, and the safety margins of the first and second aircraft are larger than 1 and 3, respectively, are infeasible, and therefore inequality 2 is proposed to remove these combinations as well as the infeasible solutions identified during the safety margin augmentation in Step 2. Similarly, inequality 3 is proposed to remove an infeasible solution whenever it is found during the individual augmentation stage in Step 3. We assume that the feasibility check finds a feasible solution for the decision $\left\{k-\mathrm{1,2},\mathrm{3}\right\}$ and the priority of the three aircraft are in decreasing order. During the individual augmentation stage in Step 3, the safety margin of the first aircraft is augmented to k at first. If the feasibility check finds that the solution is infeasible after augmentation, i.e., $\left\{k,\mathrm{2,3}\right\}$, then any other value for the safety margin of the first aircraft larger than or equal to k is infeasible, with the safety margins for the other two aircraft remaining unchanged.

3.2.2. Approximate Inequality

Intuitively, the problem can be viewed as a nesting problem that places “enlarged” aircraft in the hangar, and the enlarged area of the aircraft is determined by the safety margin of each aircraft. Inequality 4 expressed in (20) is derived from the implication mentioned above: the sum of the “enlarged” area of aircraft determined by its safety margin cannot exceed the capacity of the hangar. Due to the irregular shape of the aircraft, it is found that the highest utilization of hangar space obtained in the numerical examples is around 50% (i.e., used area of the hangar/total area of the hangar) as shown in computational results (Table 2) in Section 4.2. Therefore restricting the sum of the enlarged area by the hangar area cannot effectively restrict the safety margin of the aircraft. An alternate method for measuring the capacity of the hangar is to adopt the threshold value derived from the heuristic algorithm: the capacity of the hangar is approximately equal to the sum of the “enlarged” aircraft area determined by the threshold value, as the feasibility check cannot find a feasible solution when all the aircraft safety margins are larger than the threshold value. We would like to point out that the latent assumption in the problem is that overlaps of the “buffer area” of aircraft are allowed since the larger safety margin in a pair activates the respective revised NFP to separate the two aircraft (Figure 2(b)). However, inequality 4 regards the buffer area of an aircraft as a part of the aircraft since the inequality calculates the sum of the area of the enlarged aircraft and limits the sum to a defined value (the sum of area determined by the threshold value). Therefore, the interpretation of inequality 4 is as follows: the sum of the area of the enlarged aircraft area cannot exceed its counterpart determined by the threshold value derived from the heuristic in Section 4.2. In inequality 4, $aircraft\_revisedare{a}_i^n$ refers to the area of enlarged aircraft i associated with safety margin n.$$\begin{array}{}\text{(20)}& {\displaystyle \sum }_{i\in P^{\prime }}{z}_i^n·aircraft\_revisedare{a}_i^n\le {\displaystyle \sum }_{i\in P^{\prime }}aircraft\_revisedare{a}_i^{threshold}\end{array}$$

Table 2

Computational results of the problem.

Instance	Aircraft in Instance total_S/M/L	Number of aircraft placed in the hangar1	Proportion of used hangar space	Binary variables	Safety Margin upper bound by heuristic	CPLEX + Threshold Safety Margin upper bound				Heuristic Warm Start + Inequalities 2&3 + Threshold Safety Margin upper bound
						LB	UB	CPU	Gap	CPLEX with Heuristic warm start and inequalities 2&3			Heuristic	CPU CPLEX + Heuristic
										LB	UB	Gap	Value
1	6_4/1/1	6	0.29	2792	8	29357.92	29357.92	0.36	0	29357.92	29357.92	0	29357.92	1.91
2	6_3/2/1	6	0.30	2732	8	28823.36	28823.36	0.30	0	28823.36	28823.36	0	28823.36	2.11
3	7_4/1/2	7	0.35	3822	8	35110.96	35110.96	0.89	0	35110.96	35110.96	0	35110.96	3.00
4	7_3/2/2	7	0.39	4038	8	38709.12	38709.12	4.57	0	38709.12	38709.12	0	38709.10	4.55
5	8_5/2/1	8	0.32	4832	8	41349.36	41349.36	0.69	0	41349.36	41349.36	0	41349.36	4.39
6	8_4/2/2	8	0.44	4498	7	34591.16	37303.56	18000	7.84	34188.06	36522.06	6.83	31711.08	18175.03
7	9_7/1/1	9	0.34	6888	8	33723.12	33723.12	444.99	0	33723.12	33712.12	0	33723.12	7.67
8	10_8/1/1	10	0.38	8508	8	33926.74	37107.52	18000	9.38	35037.98	36680.60	4.69	34516.98	19781.78
9	11_9/1/1	11	0.33	10224	8					37334.12	37334.12	0	35674.76	1484.81
10	12_8/3/1	12	0.46	7172	5	N/A	33833.65	18000	N/A	28269.22	33260.65	17.66	25176.41	18647.12
11	6_1/3/2	6	0.45	1356	4	16836.14	16967.43	44423.36	0.78	16836.14	16836.14	0	16836.14	1868.15
12	6_0/4/2	6	0.38	2944	8	35671.28	35671.28	2159.54	0	35671.30	35671.30	0	34943.28	1517.73
13	7_0/5/2	7	0.47	2464	5	22436.38	29243.1	18000	30.34	23591.4	27658.8	17.24	23591.4	18624.09
14	8_1/5/2	7	0.51	920	2	N/A	11069.32	18000	N/A	7643.21	12735.22	66.62	7643.21	19324.23
15	8_2/4/2	8	0.45	3688	6	27928.82	31022.16	18000	11.08	27928.82	30109.36	7.81	27928.82	20538.05
16	8_1/5/2	8	0.49	2580	3	N/A	24539.8	18000	N/A	16477.6	22955.5	39.31	17068.8	20110.42
17	9_2/5/2	9	0.44	5100	6	27226.98	30949.08	18000	13.67	27936.34	30360.08	8.68	26945.48	19849.69
18	10_3/7/0	10	0.29	8286	8	27062.56	27062.56	1117.42	0	27062.56	27062.56	0	27062.56	41.83
19	11_1/9/1	10	0.45	2534	3	N/A	16240.14	18000	N/A	10628.76	10628.76	0	9491.5	2834.62
20	12_2/9/1	10	0.48	2945	2	N/A	16663.38	18000	N/A	15941.92	16155.38	1.34	13049.46	20368.88
21	4_1/1/2	4	0.33	1136	8	34028.08	34028.08	0.41	0	34028.08	34028.08	0	34028.08	1.38
22	6_1/2/3	5	0.44	741	3	12882.54	12882.54	31.57	0	12882.54	12882.54	0	11640.36	330.94
23	6_2/1/3	6	0.43	1041	3	12950.94	12950.94	2042.04	0	12950.94	12950.94	0	11716.44	5521.64
24	7_2/1/4	6	0.44	1107	3	12962.70	12962.70	847.48	0	12962.70	12962.70	0	11693.80	1411.98
25	7_2/2/3	6	0.44	1518	3	13543.04	18485.04	18000	36.49	13023.54	13023.54	0	12323.36	1563.5
26	7_1/2/4	5	0.44	486	2	5564.0	5564.0	29.38	0	5564.40	5564.40	0	5564.40	41.92
27	8_2/2/4	6	0.46	1065	3	12652.53	12652.53	5458.65	0	12652.53	12652.53	0	11487.02	4847.19
28	10_3/3/4	8	0.50	2058	3	14417.81	19359.81	18000	34.28	14417.81	18631.81	29.23	12906.54	20630.42
29	10_3/2/5	8	0.48	1998	3	14263.70	19205.70	18000	34.65	14263.70	18882.90	32.38	12803.80	19505.05
30	12_2/5/5	9	0.54	1730	2	N/A	14254.66	18000	N/A	9018.16	13890.66	54.03	8574.11	19939.41
31	6_2/2/2	6	0.36	2700	8	34444.88	34444.88	0.28	0	34444.88	34444.88	0	34444.88	2.53
32	6_2/2/2	6	0.34	2876	8	37012.80	37012.80	0.33	0	37012.80	37012.8	0	37012.80	1.75
33	6_2/2/2	6	0.41	2736	8	39290.44	39290.44	73.59	0	39290.44	39290.44	0	38305.84	169.19
34	9_3/3/3	8	0.50	1922	3	16096.74	18519.21	18000	15.05	16307.07	17948.01	10.06	16307.07	19728.98
35	9_3/3/3	9	0.51	1714	2	N/A	13392.80	18000	33.58	10104.6	13231.40	30.94	10035.1	19351.76
36	9_3/3/3	8	0.49	1956	2	13752.47	18694.47	18000	35.94	13752.47	17966.47	30.64	12462.98	18468.44
37	12_4/4/4	9	0.50	2114	2	N/A	21408.24	18000	N/A	16466.24	21085.44	28.05	14692.84	19059.45
38	12_4/4/4	8	0.45	1368	2	N/A	12895.14	18000	N/A	8592.68	12323.94	43.42	8592.68	18812.17
39	12_4/4/4	8	0.39	1710	2	N/A	12745.04	18000	N/A	7802.04	11168.64	43.15	6931.07	20034.97
40	12_4/4/4	10	0.53	2100	2	N/A	13897.12	18000	N/A	10166.10	13735.72	35.11	10166.1	20101.02

${}^1\mathrm{T}\mathrm{h}\mathrm{e}$ number of aircraft placed in the hangar is predetermined by maximizing the utilization of hangar space in problem.

4. Computational Results

This section presents the results of computational experiments that were carried out on instances based on real-life data provided by an aircraft maintenance company in Hong Kong. All the procedures described in the previous sections are coded in C# in Visual Studio 2010 and run on a computer with an Intel Core i7 processor, at 3.6 GHz with 32 Gb of RAM. The mixed-integer linear programming is solved by the CPLEX 12.7 serial model.

4.1. Description of Instances

We collected data from an aircraft base maintenance service provider in Hong Kong and generated problem instances based on their actual data. The maintenance company we studied has over 50 clients, including airlines, business jet companies, and utility aircraft companies. In particular, the maintenance hangar in the aircraft maintenance area of Hong Kong International Airport is operated by the company. The information related to the estimated arrival time (ETA), departure time (ETD), aircraft type, and maintenance request of each maintenance order from clients was collected. We further figured out the number of aircraft needed to be arranged each day, the frequencies of the days, and number of aircraft to be arranged, as presented in Figure 4. A mix of large-, middle-, and small-sized aircraft to be arranged in the hangar each day is typical, and it is reported that planning for 7 aircraft simultaneously by the manual method is challenging. In this regard, we adopted 40 testing instances based on the observed peak-day scenarios and the number of aircraft maintenance orders in those instances ranged from 6 to 12, which was also used in Qin et al. [14]. We refer interested readers to Qin et al. [14] for the complete instance dataset used in the computational experiments. The peak-day scenarios observed in the actual situation were used as initial instances; then the proportions of small-, medium- and large-sized aircraft were adjusted, together with the adding of new maintenance orders in order to create challenging instances in the experiment.

[figure omitted; refer to PDF]

In the instances set, we have 10 small-sized (i.e., G200, CL600, CL605, F900LX, F2000EX, F2000LX, ERJ135, F7X, G450, and GIV), 11 medium-sized (i.e., GL5T, G550, G5000, G6000, G650, A318, ERJ190, A319, A320, B738, and A321), and 2 large-sized (i.e., A332 and A333) aircraft types, which include large-sized civil aircraft and medium-size civil aircraft as well as business jets. The classification of aircraft models is based on their area. 40 instances are divided into four groups according to the majority of the aircraft type for better presentation of the results, as follows: $(1)$ the majority of aircraft in the instance are small-sized, $(2)$ the majority of aircraft in the instance are medium-sized, $(3)$ the majority of aircraft in the instance are large-sized, and $(4)$ the number of aircraft from different categories in the instance are equal. With regard to the safety margin range, we prescribed the minimal individual safety margins $l{b}_i$ of all small-sized aircraft as 1 meter, medium-sized aircraft as 2 meters, and large-sized aircraft as three meters in our computational experiment, which aligns with the idea that larger size aircraft should have higher safety distance. Referring to the practice adopted in the company, the maximal individual safety margin of all types of aircraft is prescribed as eight meters.

4.2. Computational Results of the Problem

The number of binary variables used to determine the relative positions between each pair of aircraft in the problem is determined by two factors: $(1)$ the number of aircraft to be accommodated in the hangar and $(2)$ the range of the safety margins in the problem. It is reported that the branch-and-bound algorithm with the horizontal slicing MIP model can optimally solve the open-dimensioned nesting problem with, at most, 14 pieces, with convex- and non-convex-shaped pieces [25]. To control the problem size to a moderate level, the upper bound of the safety margin is determined by the threshold value derived from the heuristic in this section, and the results are shown in the fifth column in Table 2. Considering that the problem is similar to the nesting problem with $piece·(ub-lb+\mathrm{1})$ pieces (ub and lb stand for the upper bound and lower bound of safety margin), such a problem size is challenging, so we referred to the stopping criterion adopted in literature. Alvarez-Valdes et al. [25] set several time milestones (1h, 2h, 5h, and 10h) in solving difficult instances that involve more than 12 complex irregular items. We therefore selected and prescribed the time limit for each instance as 18,000 seconds (5h), with the upper bound of the safety margin determined by the threshold value derived from the heuristic.

Table 2 shows the computational results for the problem. The number of aircraft to be placed in the hangar with maximal overall profit and satisfying minimal safety margins is indicated in the third column. As inequalities 2 and 3 thoroughly utilize the information of the intermediate solutions during the heuristic search, these two are regarded as the most comprehensive and powerful ones to enhance the computational efficiency. Therefore, we analyse the effectiveness of the proposed heuristic with inequalities 2 and 3 used to provide the initial solution and to remove infeasible solutions before the branch-and-bound algorithm. The computational results of CPLEX solving these instances are derived from the previous work in [14] for comparison. We are able to optimally solve 21 instances, with the upper bound of the safety margin determined by the threshold from the heuristic. We found that, in many instances, the initial solution provided by the heuristic proved optimal by the exact algorithm, after an exhaustive search in some instances. In addition, in 12 instances (those heuristic values being bold and underlined) out of 21 that are solved to optimal, the solution provided by the heuristic algorithm is found to be optimal, demonstrating the applicability of the developed heuristic approach. Although in some cases the objective function value increased in the branch-and-bound algorithm, the searching processes took a long time. In the problem, the difference between the best integer and upper bound corresponds to the pending safety margin of each aircraft. To update the upper bound of the branch-and-bound, one has to prove the infeasibility of the pending safety margins, which corresponds to a single feasibility check. Though the final layout demonstrates a satisfactory result in regard to operation in practice, large gaps have been recorded in instances with packed layouts, since updating the bounds in the problem we studied is far more difficult than the model involving only one NPF to separate each pair of aircraft.

Moreover, the performance of the model and the computation time differ a lot, even comparing two instances from same instance group with the same number of aircraft to be arranged in the problem. Taking instances 23 and 24 as examples, the number of aircraft placed in the hangar satisfying the minimal safety margin requirement and the threshold value derived from the heuristic are the same, and the number of binary variables involved in the two instances is similar, with similar problem settings (three large-size aircraft and 3 small-sized/ medium-sized aircraft), while the exact algorithm takes much more time to solve instance 23 to optimal. It is found out that adding inequalities into the original model can tighten the upper bound but does not necessarily accelerate the searching process of the branch-and-bound algorithm. To ensure the efficiency of the branch-and-cut algorithm, a balance between the generation of the cutting plans and branching must be considered. The searching process might be hindered by adding too many inequalities in the original LPs, although better bounds result in fewer explored nodes [30], which can also be observed in the computational results in Section 4.3.

The computational results in Section 4.2 demonstrate that inserting inequalities 2 and 3 with the warm start provided by the heuristic algorithm is able to shorten the computational time for obtaining an optimal solution or tighten the optimality gap if the optimal solution cannot be obtained within the time limit, for many instances, compared with the original MIP model, without adding inequalities and providing a warm start by the heuristic algorithm. For the large instances 36-40, the inequalities 2 and 3 with the heuristic are able to achieve better solution, and instance 38 can be solved to optimal, compared with the original model. Moreover, improvement of the lower bound is recorded after inserting the inequalities, given the lower bound value provided by the heuristic.

4.3. Comparing Inequalities for the Problem

To compare the effectiveness of the proposed inequalities, we selected those instances that were solved to optimality within 18,000 seconds in the problem in Section 4.2, with the safety margin upper bound less than 8 meters. In this section, we relaxed the safety margin upper bound to the origin upper bound limit (8 meters) in both the MIP formulation and heuristic algorithm in order to find the improvement of the objective value, as well as the effectiveness of the proposed inequalities in tightening the upper bound. Table 3 shows the results of proposed heuristic and a comparison between the four inequalities described in Section 3.2. The first column indicates the testing instances that are optimally solved in Section 4.2. The performance of each strategy is indicated by four values: the lower bound (best known solution), upper bound, optimality gap, and computational time. The time limit for each testing instance is 18,000 seconds, and the layout of the best known solutions in this section can be found in the Appendix.

Table 3

Comparison among the inequalities in solving the problem.

Instance	Binary Variables	Safety	Heuristic		CPLEX				CPLEX + Inequality 1				CPLEX + Inequalities 2 & 3				CPLEX + Inequality 4
		Margin	CPU	Value	LB	UB	Gap	CPU	LB	UB	Gap	CPU	LB	UB	Gap	CPU	LB	UB	Gap	CPU
		upper
		bound
11	2680	8	101.14	17661.77	19364.73	27335.08	41.16	18000	19364.73	31771.56	64.07	18000	18857.68	31059.58	64.71	18000	18857.68	22680.29	20.27	18000
19	9954		3036.09	10925.18	11644.28	43307.04	271.92	18000	13080.78	42119.04	221.99	18000	11662.50	40568.64	247.86	18000	11349.78	21210.48	86.88	18000
22	1976		35.63	14636.04	16553.44	25605.54	54.68	18000	16553.44	16553.44	0	4512.38	16553.44	16553.44	0	10149.44	16553.44	16553.44	0	393.62
23	2776		71.28	16798.74	18033.24	46277.44	156.62	18000	18033.24	40728.34	125.85	18000	18033.24	40909.24	126.85	18000	17078.24	19012.05	11.32	18000
24	2930		69.21	16777.84	18560.56	46775.20	152.01	18000	18560.56	39957.28	115.28	18000	18560.56	45645.40	145.93	18000	17430.76	18907.66	8.47	18000
25	3994		796.99	15516.18	16689.54	49293.44	195.36	18000	16689.54	48147.44	188.49	18000	16514.64	46745.44	183.05	18000	16689.54	21132.16	26.62	18000
26	1944		19.21	6532.80	6532.80	25426.2	289.21	18000	6532.80	6532.80	0	9196.88	6532.80	11710.20	79.25	18000	6532.80	6532.80	0	3510.80
27	2840		562.34	14022.68	15940.08	45948.08	188.26	18000	15940.08	40990.72	157.16	18000	15940.08	36442.28	128.62	18000	15299.70	18456.47	20.63	18000
38	5458		1854.96	8451.79	8451.79	50411.76	496.46	18000	8451.79	48917.54	478.78	18000	12652.93	48343.69	282.08	18000	9968.73	14404.17	44.49	18000

N/A: no feasible solution found.

The results in Table 3 show that there is no inequality that is always dominant across all the instances. We find that in some cases the performance of inequality 1 suppresses that of inequalities 2 and 3. We notice that the proposed approximate inequality 4 based on the idea of placing the “enlarged” aircraft into the hangar is able to eliminate a number of combinations of safety margins that significantly exceed the capacity of the hangar and tighten the upper bound in some cases. Although the idea of placing the “enlarged” aircraft in the problem is an approach for controlling the combinations of safety margins and tightening the upper bound, accurate calculation of the sum of the “enlarged” area is required so as to avoid removing a feasible solution, since the overlaps of the “enlarged” part between each pair of aircraft is allowed according to the definition of the safety margin and the methodology applied to separate aircraft. The computational experiments conducted in Section 4.3 focus on the challenging instances created by relaxing the upper bound of safety margin for the instances solved to optimal in Section 4.2. Therefore, we mainly focus on the final optimality gap recorded after inserting different inequalities. The results have demonstrated that inequality 4 is able to tighten the upper bound of the problem but is not necessarily valid for all cases, and therefore we would only consider inserting inequality 4 to tackle large instances and in providing an approximate estimation of the limit of the maintenance hangar.

5. Conclusions

In this paper, we examined the problem of determining the optimal individual safety margins within the admissible range of safety margins for aircraft to be serviced in a maintenance hangar by a maintenance service company during a planning period in order to minimize the risk of collision during aircraft movement operations as well as during the maintenance processes. This problem arises with the increasing number of outsourced maintenance requests from clients, and the maintenance company has to efficiently utilize their limited maintenance base space to meet the requirements of various clients. We first present a complete mixed-integer linear programming model for the aircraft parking stand arrangement problem, considering the accurate shape of aircraft, and then incorporate a set of revised NPFs to enforce the discrete safety margin between each pair of aircraft. To tackle the large number of binary variables involved in the model, we developed a heuristic approach to provide a practical solution within a reasonable time. Moreover, a set of inequalities is proposed to convert the recorded infeasible solutions during the heuristic search as cuts to be added in the mathematical model before implementing the branch-and-bound algorithm provided by CPLEX. Problem instances in computational experiments are derived from an aircraft maintenance company in Hong Kong, and the computational results show that the proposed approaches are applicable and beneficial to the problem in practice. For future research, our model can be extended to incorporate other realistic considerations, such as the availability of technical staff and maintenance equipment as well as the uncertainties encountered in actual situations while fulfilling the maintenance requests from clients.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

The work described in this paper was substantially supported by internal grants from The Hong Kong Polytechnic University Research Committee (Project nos. G-YBFD and G-YBN1); a grant from The Natural Science Foundation of China (Grant no. 71471158); a grant from The Department of Education of Liaoning Province (Grant no. LN2017QN006); and a grant under student account code RUF1.

Appendix

Appendix

For best known parking layouts for instances tested in Section 4.3, see Figure 5.

[figure omitted; refer to PDF]

References

[1] J. Van den, P. Bergh, J. Belien, J. Peeters, Aircraft maintenance operations: state of the art, 2013.

[2] J. Belien, E. Demeulemeester, P. De Bruecker, J. Van den Bergh, B. Cardoen, "Integrated staffing and scheduling for an aircraft line maintenance problem," Computers & Operations Research, vol. 40 no. 4, pp. 1023-1033, DOI: 10.1016/j.cor.2012.11.011, 2013.

[3] P. De Bruecker, J. Van den Bergh, J. Beli\"en, E. Demeulemeester, "A model enhancement heuristic for building robust aircraft maintenance personnel rosters with stochastic constraints," European Journal of Operational Research, vol. 246 no. 2, pp. 661-673, DOI: 10.1016/j.ejor.2015.05.008, 2015.

[4] Z. Liang, Y. Feng, X. Zhang, T. Wu, W. A. Chaovalitwongse, "Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem," Transportation Research Part B: Methodological, vol. 78, pp. 238-259, DOI: 10.1016/j.trb.2015.03.013, 2015.

[5] A. Gavranis, G. Kozanidis, "An exact solution algorithm for maximizing the fleet availability of a unit of aircraft subject to flight and maintenance requirements," European Journal of Operational Research, vol. 242 no. 2, pp. 631-643, DOI: 10.1016/j.ejor.2014.10.016, 2015.

[6] S. Ahire, G. Greenwood, A. Gupta, M. Terwilliger, "Workforce-constrained preventive maintenance scheduling using evolution strategies," Decision Sciences, vol. 31 no. 4, pp. 833-856, DOI: 10.1111/j.1540-5915.2000.tb00945.x, 2000.

[7] J. Beliën, B. Cardoen, E. Demeulemeester, "Improving workforce scheduling of aircraft line maintenance at Sabena Technics," Interfaces, vol. 42 no. 4, pp. 352-364, DOI: 10.1287/inte.1110.0585, 2012.

[8] L. W. Clarke, C. A. Hane, E. L. Johnson, G. L. Nemhauser, "Maintenance and crew considerations in fleet assignment," Transportation Science, vol. 30 no. 3, pp. 249-260, DOI: 10.1287/trsc.30.3.249, 1996.

[9] A. M. Cohn, C. Barnhart, "Improving crew scheduling by incorporating key maintenance routing decisions," Operations Research, vol. 51 no. 3, pp. 387-396, DOI: 10.1287/opre.51.3.387.14959, 2003.

[10] N. Papadakos, "Integrated airline scheduling," Computers & Operations Research, vol. 36 no. 1, pp. 176-195, DOI: 10.1016/j.cor.2007.08.002, 2009.

[11] A. E. E. Eltoukhy, F. T. S. Chan, S. H. Chung, "Airline schedule planning: a review and future directions," Industrial Management Data Systems, vol. 117 no. 6, pp. 1201-1243, DOI: 10.1108/IMDS-09-2016-0358, 2017.

[12] S. H. Chung, Y. K. Tse, T. M. Choi, "Managing disruption risk in express logistics via proactive planning," Industrial Management & Data Systems, vol. 115 no. 8, pp. 1481-1509, DOI: 10.1108/IMDS-04-2015-0155, 2015.

[13] G. Chen, W. He, L. C. Leung, T. Lan, Y. Han, "Assigning licenced technicians to maintenance tasks at aircraft maintenance base: a bi-objective approach and a Chinese airline application," International Journal of Production Research, vol. 55 no. 19, pp. 5550-5563, DOI: 10.1080/00207543.2017.1296204, 2017.

[14] Y. Qin, F. T. Chan, S. H. Chung, T. Qu, B. Niu, "Aircraft parking stand allocation problem with safety consideration for independent hangar maintenance service providers," Computers & Operations Research, vol. 91, pp. 225-236, DOI: 10.1016/j.cor.2017.10.001, 2018.

[15] G. Wäscher, H. Haußner, H. Schumann, "An improved typology of cutting and packing problems," European Journal of Operational Research, vol. 183 no. 3, pp. 1109-1130, DOI: 10.1016/j.ejor.2005.12.047, 2007.

[16] T. C. Martins, M. S. G. Tsuzuki, "Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions," Expert Systems with Applications, vol. 37 no. 3, pp. 1955-1972, DOI: 10.1016/j.eswa.2009.06.081, 2010.

[17] H. Dyckhoff, "A typology of cutting and packing problems," European Journal of Operational Research, vol. 44 no. 2, pp. 145-159, DOI: 10.1016/0377-2217(90)90350-K, 1990.

[18] A. Caprara, A. Lodi, M. Monaci, "Fast approximation schemes for two-stage, two-dimensional bin packing," Mathematics of Operations Research, vol. 30 no. 1, pp. 150-172, DOI: 10.1287/moor.1040.0112, 2005.

[19] C. Kenyon, E. Remila, "A near-optimal solution to a two-dimensional cutting stock problem," Mathematics of Operations Research, vol. 25 no. 4, pp. 645-656, DOI: 10.1287/moor.25.4.645.12118, 2000.

[20] N. Bansal, J. R. Correa, C. Kenyon, M. Sviridenko, "Bin packing in multiple dimensions: inapproximability results and approximation schemes," Mathematics of Operations Research, vol. 31 no. 1, pp. 31-49, DOI: 10.1287/moor.1050.0168, 2006.

[21] C. Alves, P. Bras, J. . Valerio de Carvalho, T. Pinto, "A variable neighborhood search algorithm for the leather nesting problem," Mathematical Problems in Engineering, 2012.

[22] Y.-X. Xu, "An Efficient Heuristic Approach for Irregular Cutting Stock Problem in Ship Building Industry," Mathematical Problems in Engineering, vol. 2016, 2016.

[23] B. Amaro, P. R. Pinheiro, R. D. Saraiva, P. Pinheiro, "Dealing with Nonregular Shapes Packing," Mathematical Problems in Engineering, vol. 2014,DOI: 10.1155/2014/548957, 2014.

[24] B. Amaro Júnior, P. R. Pinheiro, P. V. Coelho, "A Parallel Biased Random-Key Genetic Algorithm with Multiple Populations Applied to Irregular Strip Packing Problems," Mathematical Problems in Engineering, vol. 2017,DOI: 10.1155/2017/1670709, 2017.

[25] R. Alvarez-Valdes, A. Martinez, J. M. Tamarit, "A branch & bound algorithm for cutting and packing irregularly shaped pieces," International Journal of Production Economics, vol. 145 no. 2, pp. 463-477, DOI: 10.1016/j.ijpe.2013.04.007, 2013.

[26] L. H. Cherri, L. R. Mundim, M. Andretta, F. M. Toledo, J. F. Oliveira, M. A. Carravilla, "Robust mixed-integer linear programming models for the irregular strip packing problem," European Journal of Operational Research, vol. 253 no. 3, pp. 570-583, DOI: 10.1016/j.ejor.2016.03.009, 2016.

[27] A. M. Gomes, J. F. Oliveira, "Solving irregular strip packing problems by hybridising simulated annealing and linear programming," European Journal of Operational Research, vol. 171 no. 3, pp. 811-829, DOI: 10.1016/j.ejor.2004.09.008, 2006.

[28] A. A. S. Leao, F. M. B. Toledo, J. F. Oliveira, M. A. Carravilla, "A semi-continuous MIP model for the irregular strip packing problem," International Journal of Production Research, vol. 54 no. 3, pp. 712-721, DOI: 10.1080/00207543.2015.1041571, 2016.

[29] A. Martinez-Sykora, R. Alvarez-Valdes, J. Bennell, J. M. Tamarit, "Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts," OMEGA - The International Journal of Management Science, vol. 52, pp. 15-32, 2015.

[30] L. Taccari, "Integer programming formulations for the elementary shortest path problem," European Journal of Operational Research, vol. 252 no. 1, pp. 122-130, DOI: 10.1016/j.ejor.2016.01.003, 2016.

[31] E. K. Burke, R. S. R. Hellier, G. Kendall, G. Whitwell, "Complete and robust no-fit polygon generation for the irregular stock cutting problem," European Journal of Operational Research, vol. 179 no. 1, pp. 27-49, DOI: 10.1016/j.ejor.2006.03.011, 2007.

[32] J. A. Bennell, J. F. Oliveira, "A tutorial in irregular shape packing problems," Journal of the Operational Research Society, vol. 60 no. 1, pp. S93-S105, DOI: 10.1057/jors.2008.169, 2009.

[33] W. Zhang, Q. Zhang, "Finite-circle method for component approximation and packing design optimization," Engineering Optimization, vol. 41 no. 10, pp. 971-987, DOI: 10.1080/03052150902890056, 2009.

[34] A. Felipe, M. Teresa Ortuño, G. Tirado, "Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints," European Journal of Operational Research, vol. 211 no. 1, pp. 66-75, DOI: 10.1016/j.ejor.2010.11.011, 2011.

[35] M. Iori, J.-J. Salazar-González, D. Vigo, "An exact approach for the vehicle routing problem with two-dimensional loading constraints," Transportation Science, vol. 41 no. 2, pp. 253-264, DOI: 10.1287/trsc.1060.0165, 2007.

[36] P. Hokama, F. K. Miyazawa, E. C. Xavier, "A branch-and-cut approach for the vehicle routing problem with loading constraints," Expert Systems with Applications, vol. 47,DOI: 10.1016/j.eswa.2015.10.013, 2016.

[37] F. Alvelos, T. M. Chan, P. Vilaça, T. Gomes, E. Silva, J. M. Valério De Carvalho, "Sequence based heuristics for two-dimensional bin packing problems," Engineering Optimization, vol. 41 no. 8, pp. 773-791, DOI: 10.1080/03052150902835960, 2009.

[38] M. Beyaz, T. Dokeroglu, A. Cosar, "Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems," Applied Soft Computing, vol. 36, pp. 236-245, DOI: 10.1016/j.asoc.2015.06.063, 2015.

[39] Y. Cui, "Heuristic for two-dimensional homogeneous two-segment cutting patterns," Engineering Optimization, vol. 45 no. 1, pp. 89-105, DOI: 10.1080/0305215X.2012.658784, 2013.

[40] Y. Cui, T. Gu, Y. Zhong, "A recursive algorithm for the rectangular guillotine strip packing problem," Engineering Optimization, vol. 40 no. 4, pp. 347-360, DOI: 10.1080/03052150701753356, 2008.

[41] J. A. Bennell, K. A. Dowsland, W. B. Dowsland, "The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon," Computers & Operations Research, vol. 28 no. 3, pp. 271-287, 2000.

[42] J. A. Bennell, X. Song, "A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums," Computers & Operations Research, vol. 35 no. 1, pp. 267-281, DOI: 10.1016/j.cor.2006.02.026, 2008.

[43] J. A. Bennell, J. F. Oliveira, "The geometry of nesting problems: a tutorial," European Journal of Operational Research, vol. 184 no. 2, pp. 397-415, DOI: 10.1016/j.ejor.2006.11.038, 2008.