Air refueling tanker allocation based on a multi-objective zero-one integer programming model

Abstract

The need to refuel aircraft traveling long distances is important because fuel tank capacities limit the range of aircraft, and landing to refuel may not be practical or even possible. To overcome this difficulty, aerial refueling can be performed en route along the aircraft’s travel path to extend its range. This paper considers the problem of identifying the locations along an aircraft flight path at which to conduct aerial refueling, given a limited number of refueling stations. Due to the inherent uncertainty of real-world cases, the cost of refueling is considered as an interval number, and the problem is mathematically presented as an interval multi-objective zero-one integer programming model. To solve the model, a new version of the modified label-correcting method and a genetic algorithm are proposed. Moreover, the applicability and efficiency of the proposed solution approaches are examined and compared using some randomly generated test problems.

1 Introduction

Vehicles have different fuel tank capacities, and these capacities limit their range. Thus, any vehicle can travel a limited distance even with a full fuel tank. Aerial refueling is necessary for aircraft traveling beyond their fuel tank range when landing to refuel is undesirable, impractical, or impossible. To perform refueling operations, the following initial information may be needed in advance.

• The number of required refuelings along a certain route to reach the destination;

• The proper locations for a set of refueling operations;

• The amount of fuel that the vehicle consumes while traveling along a route.

Refueling problems have attracted attention from researchers in areas such as ground transportation and aviation organization (Berman and Krass 1998; Kuby et al. 2009; Jin et al. 2006; Kaplan and Rabadi 2012).

In the ground transportation area, Kuby and Lim (2005) presented a flow refueling location model (FRLM). The FRLM determines optimal locations for refueling stations considering the limitation of vehicle ranges. To solve the FRLM, Lim and Kuby (2010) adopted three heuristic algorithms. However, their algorithms took a long time to solve problems in large-scale networks. To overcome this shortcoming, Capar and Kuby (2011) presented a radically different mixed-integer programming formulation. The proposed model solved the FRLM to optimality as fast as or faster than the aforementioned heuristic algorithms. Wang and Lin (2009) proposed a refueling-station-location model based on a mixed-integer programming problem. The major advantage of this model is that it does not require additional preprocessing for the model solutions, in contrast to the FRLM. A hybrid model with two objective functions was also investigated by Wang and Wang (2010). They used a mixed-integer programming model to locate the refueling stations serving inter-city and intra-city travel. MirHassani and Ebrazi (2013) reformulated a previously introduced FRLM, and proposed a new mixed-integer linear programming problem. The computation time of the proposed model was also compared with that of Wang and Lin’s (2009) model. Other studies concerning the FRLM include the capacitated flow refueling location model (Upchurch et al. 2009), comparison of p-median and the FRLM (Upchurch and Kuby 2010), drivers’ deviations (Kim and Kuby 2012), heuristic approaches to solve the deviation flow refueling location (Kim and Kuby 2013), and dispersion of candidate sites on arcs (Kuby and Lim 2007).

As mentioned above, refueling problems have also been investigated in aviation organizations. Sundar and Rathinam (2014) presented a mixed-integer linear programming formulation for routing a small unmanned aerial vehicle by a series of targets and refueling depots. This formulation minimized the total required fuel such that all targets are visited. Moreover, Levy et al. (2014) considered a multiple depot, multiple unmanned vehicle routing problem such that all the specified targets should be visited and the total travel cost of the vehicles should be minimized.

Aerial refueling is one of the solutions used to refuel aircraft conducting operations over an extended duration. Transferring fuel from a tanker aircraft to a receiver aircraft in the air is called aerial refueling. Tanker aircraft can carry a significant amount of fuel to meet the requirements of receiver aircraft using special equipment and techniques during their flights. The first aerial refueling was performed in 1917 by the Russian-American Alexander de Seversky (Thomas et al. 2014). The key purpose of aerial refueling is to increase aircraft endurance. Due to its advantages, aerial refueling has been extensively investigated, developed, and employed in many aerial missions. Its first military application was in the Korean War (Thomas et al. 2014). A number of studies have been devoted to aerial refueling problems. In this context, Bush (2006) investigated the problem of routing an aircraft, locating a fixed number of aerial refueling points to be served by tanker aircraft based on predetermined locations, and minimizing the total fuel consumptions of both the receiver aircraft and the tanker aircraft. The problem of finding the least costly route for an aircraft between a fixed origin and destination locations while ensuring sufficient fuel is either on board or acquired en route via aerial refueling for the completion of the route was studied by Kannon et al. (2014). Kannon et al. also proved that this problem is NP-hard. Kannon et al. (2015) subsequently considered the aircraft routing problem with aerial refueling. To deal with this problem, they presented a multi-objective mixed-integer programming model.

Our main focus in this paper is the aerial refueling operation for an aircraft. An arbitrary route between a fixed origin and a specified destination from a network is considered. The aircraft should travel this route without running out of fuel. Obviously, if the amount of fuel that the aircraft needs to travel the route is greater than its range, one or more refueling operations are needed. Moreover, it is assumed that there are refueling tankers in some predetermined stations on the ground. We would like to determine the nodes at which aerial refueling should be performed and allocate the stations containing tanker aircraft to these nodes. As the allocation process and refueling operations involve some costs, it would be reasonable to seek appropriate solutions that minimize the total cost as well as the number of refueling operations. To deal with the problem mathematically, parameters such as the costs of serving aerial refueling nodes by tanker aircraft and fuel consumption of the receiver aircraft should be available. In some of the real-world situations, the values of parameters cannot be determined exactly. For instance, the amount of fuel that an aircraft needs to travel a route depends on weather conditions, altitude, gross weight of the aircraft, etc. Any change in the values of these parameters affects the amount of fuel consumed. Uncertainty is an inherent aspect of measurements, and it would be more realistic to consider uncertain inputs for the parameters of the aerial refueling problem. Uncertainty may be interpreted as randomness or fuzziness (Wu 2009). However, specifying distributions of random parameters and membership functions of fuzzy numbers is very questionable. Interval programming may provide an alternative choice for dealing with uncertain parameters (Oliveira and Antunes 2009; Urli and Nadeau 1992; Rivaz and Yaghoobi 2015; Hladik 2016). In interval programming, uncertain parameters are modeled by closed intervals, which may be easier to handle.

To deal with the newly proposed aerial refueling problem, a multi-objective zero-one integer programming model with interval objective function coefficients is proposed in this paper. The combination of multi-objective programming, interval programming, and refueling requirements of a receiver aircraft with limited range in this problem sets it apart from existing aerial refueling research. To handle the model, two new algorithms are developed based on the inherent multi-objective nature of the problem. Moreover, the performance of the algorithms is analyzed and compared through some examples.

The remainder of this paper is organized as follows. Some preliminaries are stated in Sect.  2. Section  3 describes the problem and proposes its mathematical programming model. In Sect. 4, two algorithms are presented to solve the proposed model. Numerical examples and computational results are provided in Sect. 5. Finally, Sect. 6 is devoted to the conclusion.

2 Preliminaries

In this section, some initial concepts and definitions that will be used later are reviewed.

A closed interval in ${\mathbb{R}}$ is defined as

$$\begin{aligned} \left[ a^{l}, a^{u}\right] = \left\{ t \in {\mathbb {R}} \vert a^{l}\le t \le a^{u} \right\} , \end{aligned}$$

where $a^{l}$ and $a^{u}$ denote the lower and upper bounds of the interval, respectively. An interval with equal lower and upper bounds identifies a real number, i.e., $a=[a, a], a \in {\mathbb {R}}$.

Let $A= [a^{l}, a^{u}]$ and $B= [b^{l}, b^{u}]$ be two closed intervals in ${\mathbb {R}}$. Then, by definition, their sum is

$$\begin{aligned} A+B= \lbrace a+b \vert a \in A, b\in B\rbrace =\left[ a^{l}+b^{l}, a^{u}+b^{u}\right] . \end{aligned}$$

Different order relations have been proposed on closed intervals (Zapata et al. 2013; Wu 2009). The strong order, $\hbox{``}\leqslant _{I}\hbox{''}$, will be applied in this paper. A is strongly less than or equal to B (written as $A \leqslant _{I} B$) if and only if $a^{u} \le b^{l}$. In fact, $A\leqslant _{I} B$ indicates that any value from the interval $A= [a^{l}, a^{u}]$ is smaller than or equal to any value from the interval $B= [b^{l}, b^{u}]$. The strong order is the common and by far most prominent sense of interval order (Zapata et al. 2013). It is not difficult to say that $\hbox{``}\leqslant _{I}\hbox{''}$ is a partial order on the set of all closed intervals in ${\mathbb {R}}$. The word “partial” in the name “partial order” is used as an indication that not every pair of intervals need be comparable. Intervals are frequently partially ordered and cannot be compared. When we are forced to compare many intervals, many incomparable intervals may exist (Okada and Gen 1993). To select the smaller interval of a set of incomparable intervals, some studies suggest converting them to crisp values (Sengupta et al. 2001). An important deficiency of this approach is that a considerable portion of the information of the data of the problem may be ignored during the conversion. Therefore, to overcome this deficiency in comparisons, we retain all incomparable intervals for further consideration. For more details on interval analysis, the studies of Okada and Gen (1993) and Moore et al. (2009) are suggested.

In the following, a traditional multi-objective integer programming problem is defined as

$$\begin{aligned} \min :\mathbf{C }{\mathbf{x }}&= (\mathbf{c }_{1}{\mathbf{x }}, \ldots , \mathbf{c }_{p}{\mathbf{x }})\\ s.t. \quad {\mathbf{x }}&\in X,\\ \end{aligned}$$

(1)

where

• $X \subseteq \mathbb {Z}^{n}$ is a finite feasible set (here $\mathbb {Z}$ denotes the set of all integers).

• $\mathbf{c }_{i}{\mathbf{x }}= \sum \nolimits _{j=1}^{n}c_{ij}x_{j}$ for $i=1, \ldots , p$ and $c_{ij}, i=1, \ldots , p$, $j=1, \ldots , n$ are real numbers.

More explicitly, $X=\lbrace {\mathbf{x }} \in \mathbb {Z}^{n} \vert A{\mathbf{x }}={\mathbf{b}} , {\mathbf{x }}\ge 0 \rbrace$, $A \in {\mathbb {R}}^{m\times n }, {\mathbf{b}} \in {\mathbb {R}}^{m}$. Many multi-objective integer programs will actually have $X \subseteq \lbrace 0, 1 \rbrace ^{n}$.

In multi-objective optimization problems, it is rarely possible to find a solution that optimizes all objective functions simultaneously. Hence, the concept of an efficient solution is used instead of the optimal solution. In the efficient solution set, no improvement in any objective function is possible without sacrificing at least one of the other objective functions. To present the definition of efficiency, an order relation in ${\mathbb {R}}^{p}$ is needed. Let ${\mathbf{a}} =(a_{1}, \ldots , a_{p})^{t}$ and ${\mathbf{b}} =(b_{1}, \ldots , b_{p})^{t}$ be two vectors in ${\mathbb {R}}^{p}$ . Then ${\mathbf{a}} \preccurlyeq {\mathbf{b}}$ if $a_{i} \le b_{i}$ for $i=1,\ldots , p$ and there is also at least one $1\le q \le p$ with $a_{q} < b_{q}$.

Definition 1

A feasible solution ${\mathbf{x }}^{0}$ of Problem (1) is efficient if there is no ${\mathbf{x }} \in X$ such that $C{\mathbf{x }} \preccurlyeq C{\mathbf{x }}^{0}$.

The above definition can be found in many references, such as Steuer (1986) and Ehrgott (2005).

A multi-objective integer programming problem with interval objective function coefficients is as follows:

$$\begin{aligned} \min :\quad Z({\mathbf{x }})&=\mathbf{C }{\mathbf{x }}\\ s.t. \quad {\mathbf{x }}&\in X,\\ \mathbf{C }&\in \varPsi , \end{aligned}$$

(2)

where $\varPsi$ is a set of $p\times n$ matrices with each row in the form of $\mathbf{c }_{i}$, with elements $c_{ij} = [c_{ij}^{l}, c_{ij}^{u}]$ and $i=1, \ldots , p$, $j=1, \ldots , n$.

For every ${\mathbf{x }} \in X$, $Z({\mathbf{x }})=([z_{1}^{l}({\mathbf{x }}), z_{1}^{u}({\mathbf{x }})], \ldots , [z_{p}^{l}({\mathbf{x }}), z_{p}^{u}({\mathbf{x }})])=([\sum \nolimits _{j=1}^{n} c_{1j}^{l}x_{j}, \sum \nolimits _{j=1}^{n}c_{1j}^{u}x_{j}],\ldots ,[\sum \nolimits _{j=1}^{n}c_{pj}^{l}x_{j}, \sum \nolimits _{j=1}^{n}c_{pj}^{u}x_{j}])$, is an interval-valued vector. Therefore, Problem (2) could also be written as

$$\begin{aligned} \min :\quad z_{i}({\mathbf{x }})&= \sum _{j=1}^{n} \left[ c_{ij}^{l}, c_{ij}^{u}\right] x_{j},\quad i=1, \ldots , p,\\ s.t.~ ~{\mathbf{x }}&\in X. \\ \end{aligned}$$

(3)

It is clear that if coefficients $[c_{ij}^{l}, c_{ij}^{u}]$, $i=1, \ldots , p$, $j=1, \ldots , n$ are degenerated to real numbers, then Problem (2) is reduced to Problem (1). For simplicity, (2) is called an interval multi-objective integer (IMOI) programming problem.

By $[a^{l}, a^{u}] <_{I}[b^{l}, b^{u}]$, we mean $a^{u} < b^{l}$, and hence the following order on interval-valued vectors is stated. Let ${\mathcal {A}}$ and ${\mathcal {B}}$ be two interval-valued vectors as

$${\mathcal {A}}= \left( \left[ a_{1}^{l}, a_{1}^{u}\right] , \left[ a_{2}^{l}, a_{2}^{u}\right] ,\ldots , \left[ a_{p}^{l}, a_{p}^{u}\right] \right)$$

and

$${\mathcal {B}} = \left( \left[ b_{1}^{l}, b_{1}^{u}\right] , \left[ b_{2}^{l}, b_{2}^{u}\right] ,\ldots , \left[ b_{p}^{l}, b_{p}^{u}\right] \right) .$$

By ${\mathcal {A}} \preccurlyeq _{IV} {\mathcal {B}}$, we mean $[a_{i}^{l}, a_{i}^{u}] \leqslant _{I} [b_{i}^{l}, b_{i}^{u}] , i=1,\ldots , p$, and there exists at least one $1\le j \le p$ such that $[a_{j}^{l}, a_{j}^{u}] <_{I} [b_{j}^{l}, b_{j}^{u}]$. Now, considering the above-mentioned order on interval vectors, the concepts of efficiency, nondominance, and dominance are introduced for the IMOI Problem (2).

Definition 2

A feasible solution ${\mathbf{x }}^{0}$ of Problem (2) is IV-efficient if there exists no ${\mathbf{x }} \in X$ such that $C{\mathbf{x }}\preccurlyeq _{IV} C{\mathbf{x }}^{0}$. If ${\mathbf{x }}^{0}$ is IV-efficient, $C{\mathbf{x }}^{0}$ is called a nondominated interval-valued vector. If ${\mathbf{x }}^{1}, {\mathbf{x }}^{2} \in X$ and $C{\mathbf{x }}^{1}\preccurlyeq _{IV} C{\mathbf{x }}^{2}$, $C{\mathbf{x }}^{1}$ dominates $C{\mathbf{x }}^{2}$.

3 Problem statement

Let ${\mathfrak {p}}$ be the shortest path from $s^{{\mathfrak {p}}}$ to $t^{{\mathfrak {p}}}$ with the set of nodes $N^{{\mathfrak {p}}}$ (which also contains $s^{{{\mathfrak {p}}}}$ and $t^{{{\mathfrak {p}}}}$) and the set of arcs $E^{{\mathfrak {p}}}$. Now, consider an aircraft that is traveling from the origin, $s^{{{\mathfrak {p}}}}$, to the destination, $t^{{{\mathfrak {p}}}}$, along the path ${\mathfrak {p}}$. It is assumed that the aircraft has a full tank of fuel at the origin and may not refuel at the destination node (Kannon et al. 2015). Due to the limited range of the aircraft, it may run out of fuel before reaching the destination; therefore, aerial refueling is necessary. It is assumed that the nodes with no possibility of refueling are removed from the path at the beginning. Hence, there is the possibility of refueling on all nodes of the path. To perform aerial refuelings, all valid combinations of refueling nodes are found (Kuby and Lim 2005). Each valid combination is a subset of $N^{{{\mathfrak {p}}}}$, which contains the possible aerial refueling nodes.

Undoubtedly, the range of the aircraft, R, and the amount of fuel that is consumed by the aircraft to travel a subpath between any two nodes i and j on path ${\mathfrak {p}}$, $f_{{\mathfrak {p}}} (i, j)$, play essential roles in determining the valid combinations. The amount of fuel that the aircraft consumes to travel a subpath may change depending on different factors such as weather, airspeed, altitude and gross weight (Kannon et al. 2015). Hence, it would be more meaningful to consider the amount of consumable fuel needed to travel a subpath as an uncertain value. In this sense, it can be interpreted as an interval number, i.e. $f_{{\mathfrak {p}}} (i, j)=[f_{{\mathfrak {p}}_{ij}}^{l}, f_{{\mathfrak {p}}_{ij}}^{u}]$. Here, R could also be considered as an interval number with equal lower and upper bounds.

In what follows, to find valid combinations of aerial refueling nodes on path ${\mathfrak {p}}$, a network denoted by ${\mathcal {G}}^{{\mathfrak {p}}}= {\mathcal {G}}^{{\mathfrak {p}}}({\mathcal {N}}^{{\mathfrak {p}}}, {\mathcal {E}}^{{\mathfrak {p}}})$ is constructed (MirHassani and Ebrazi 2013). In this network, ${\mathcal {N}}^{{\mathfrak {p}}}$ and ${\mathcal {E}}^{{\mathfrak {p}}}$ define the sets of nodes and arcs on path ${\mathfrak {p}}$. Before starting to construct ${\mathcal {G}}^{\mathfrak {p}}$, the notation $ord_{{\mathfrak {p}}}(i)$ is defined as an ordering index of node i in the path sequence ${\mathfrak {p}}$. For instance, the ordering index of node C on path ${\mathfrak {p}}: s^{{\mathfrak {p}}}-A-B-C-D-t^{{\mathfrak {p}}}$ is $ord_{{\mathfrak {p}}}(C)=4$. To construct ${\mathcal {G}}^{\mathfrak {p}}$, each node $i \in N^{ {\mathfrak {p}} }$ should be connected to any other node $j \in N^{ {\mathfrak {p}} }$ if the ordering index of i is less than the ordering index of j in the path sequence ${\mathfrak {p}}$ ($ord_{{\mathfrak {p}}}(i)< ord_{{\mathfrak {p}}}(j)$) and the aircraft is able to start from i with a full tank of fuel and can reach j without running out of fuel. In other words,

$$(ord_{{\mathfrak {p}}}(i) < ord_{{\mathfrak {p}}}(j) ) \& ( f_{{\mathfrak {p}}}(i, j) \leqslant _{I} R) \Longrightarrow (i, j) \in {\mathcal {E}}^{{\mathfrak {p}}}, \quad \forall i, j \in N^{ {\mathfrak {p}} }.$$

As stated before, $\hbox{``}\leqslant _{I}\hbox{''}$ denotes the strong order between interval numbers. Since $f_{{\mathfrak {p}}}(i, j) \leqslant _{I} R$ means that any value from the interval $f_{{\mathfrak {p}}}(i, j)$ is smaller than or equal to any value from the interval R. Thus, the aircraft is guaranteed to never run out of fuel on the subpath between nodes i and j on path ${\mathfrak {p}}$. If in this process we encounter a node that could not be connected to any other nodes with a larger ordering index, then path ${\mathfrak {p}}$ is infeasible, i.e., this path cannot be traveled along due to the fuel capacity restriction. In ${\mathcal {G}}^{\mathfrak {p}}$, each arc corresponds to the consecutive feasible aerial refueling, and each directed path from $s^{{\mathfrak {p}}}$ to $t^{{\mathfrak {p}}}$ shows a feasible combination of aerial refuelings that can refuel path ${\mathfrak {p}}$. To further clarify, a simple example is given here.

Fig. 1

Network ${\mathcal {G}}^{\mathfrak {p}}$ for Example 1

Example 1

Consider a specified path ${\mathfrak {p}}$ with six nodes, $s^{{\mathfrak {p}}}-A-B-C-D-t^{{\mathfrak {p}}}$, and an aircraft with $R=[90{,}000, 90{,}000]=90{,}000$ (measured in pounds) that is going to fly from origin $s^{{\mathfrak {p}}}$ to destination $t^{{\mathfrak {p}}}$. Moreover, suppose $f_{{\mathfrak {p}}}(s^{{\mathfrak {p}}}, A)=[20{,}000, 25{,}000]$, $f_{{\mathfrak {p}}}(A, B)=[38{,}000, 42{,}000]$, $f_{{\mathfrak {p}}}(B, C)=[69{,}000, 73{,}000], f_{{\mathfrak {p}}}(C, D)=[30{,}000, 32{,}000]$ and $f_{{\mathfrak {p}}}(D, t^{{\mathfrak {p}}})=[8000, 11{,}000]$ (measured in pounds). To find all valid combinations of aerial refueling nodes, the mentioned rules are applied. Obviously, $ord_{{\mathfrak {p}}} (s^{{\mathfrak {p}}})< ord_{{\mathfrak {p}}}(A)$ and $f_{{\mathfrak {p}}}(s^{{\mathfrak {p}}}, A)\leqslant _{I} R$; accordingly, ${\mathcal {G}}^{\mathfrak {p}}$ includes arc $(s^{{\mathfrak {p}}}, A)$. Furthermore, $ord_{{\mathfrak {p}}}(s^{{\mathfrak {p}}}) < ord_{{\mathfrak {p}}}(B)$ and $f_{{\mathfrak {p}}}(s^{{\mathfrak {p}}}, B) = f_{{\mathfrak {p}}}(s^{{\mathfrak {p}}}, A)+f_{{\mathfrak {p}}}(A, B)\leqslant _{I} R$ imply that ${\mathcal {G}}^{\mathfrak {p}}$ contains arc $(s^{{\mathfrak {p}}}, B)$. By performing similar comparisons for all nodes, ${\mathcal {G}}^{\mathfrak {p}}$ is constructed (Fig. 1). According to Fig. 1, the four valid combinations of aerial refueling nodes are $\lbrace A, B, C, D\rbrace$, $\lbrace B, C, D \rbrace$, $\lbrace A, B, C\rbrace$, and $\lbrace B, C\rbrace$.

There are several criteria for selecting one or more appropriate combinations for aerial refuelings among all valid combinations. In an aerial refueling operation, a tanker aircraft must fly from its specified station on the ground to an aerial refueling node in the air. Obviously, each refueling operation includes some costs, which are affected by different factors, such as the distance that should be covered by the tanker aircraft and the fuel consumed by the tanker aircraft to reach the aerial refueling node. Thus, it is reasonable to search for refueling operations with minimum cost. Furthermore, to avoid wasting time and cost, identifying the minimum number of necessary aerial refuelings to complete the aircraft mission is another criterion for selecting one or more valid combinations of aerial refueling nodes. Therefore, minimizing the total cost of refueling and minimizing the number of refuelings are the two criteria considered in this paper. In addition, it is assumed that there sufficient fuel and tanker aircraft available at each station. Hence, there is no limitation on the frequency of use of the stations.

To find appropriate aerial refueling combinations among all valid combinations on the specified path ${\mathfrak {p}}$, according to the mentioned criteria, a bi-objective programming model is presented. The following set, parameter, and decision variables are used in the proposed model.

K::

The set of possible stations.

$[c_{kj}^{l}, c_{kj}^{u}]$::

The interval cost of an aerial refueling operation at node j, which is served by a tanker aircraft from the k-th station.

$y_{kj} ^{{\mathfrak {p}}}$::

1 if the aerial refueling at node j on path ${\mathfrak {p}}$ is served by a tanker aircraft from the k-th station; otherwise 0.

$x_{ij}^{{\mathfrak {p}}}$::

1 if arc $(i, j)\in {\mathcal {E}}^{{\mathfrak {p}}}$ is traveled along by the aircraft; otherwise 0.

The model is formulated as follows:

$$\begin{aligned} \min :\quad Z_{1}&=\sum _{k\in K} \sum _{\begin{array}{c} j\in {\mathcal {N}}^{{\mathfrak {p}}} \\ j\ne s^{{\mathfrak {p}}}, t^{{\mathfrak {p}}} \end{array}} \left[ c_{kj}^{l}, c_{kj}^{u}\right] y_{kj}^{{\mathfrak {p}}}, \end{aligned}$$

(4)

$$\begin{aligned} \min : \quad Z_{2}&= \sum _{k\in K} \sum _{\begin{array}{c} j\in {\mathcal {N}}^{{\mathfrak {p}}} \\ j\ne s^{{\mathfrak {p}}}, t^{{\mathfrak {p}}} \end{array}} ~ y_{kj}^{{\mathfrak {p}}}, \end{aligned}$$

(5)

$$\begin{aligned}s.t. \quad &\sum _{\lbrace j| (i, j)\in {\mathcal {E}}^{{\mathfrak {p}}}\rbrace } x_{ij}^{^{{\mathfrak {p}}}} - \sum _{\lbrace j| (j, i)\in {\mathcal {E}}^{{\mathfrak {p}}}\rbrace } x_{ji}^{^{{\mathfrak {p}}}}=\left\{ \begin{array}{rl} 1 &{} {\text {if }}\,\, i=s^{{\mathfrak {p}}},\\ 0 &{} {\text {if }}\,\, i \ne s^{{\mathfrak {p}}}, t^{{\mathfrak {p}}},\\ -\,1 &{} {\text {if }} \,\, i=t^{{\mathfrak {p}}}, \end{array} \right. \forall i\in {\mathcal {N}}^{{\mathfrak {p}}}, \end{aligned}$$

(6)

$$\begin{aligned}&\sum _{k\in K} y_{kj}^{{\mathfrak {p}}} \ge \sum _{\lbrace i| (i, j)\in {\mathcal {E}}^{{\mathfrak {p}}}\rbrace } x_{ij}^{{{\mathfrak {p}}}}, \qquad \forall j\in {\mathcal {N}}^{{\mathfrak {p}}}, j\ne s^{{\mathfrak {p}}}, t^{{\mathfrak {p}}}, \end{aligned}$$

(7)

$$\begin{aligned}&\sum _{k\in K} y_{kj}^{{\mathfrak {p}}}\le 1, \qquad \forall j\in {\mathcal {N}}^{{\mathfrak {p}}}, j\ne s^{{\mathfrak {p}}}, t^{{\mathfrak {p}}}, \end{aligned}$$

(8)

$$\begin{aligned}&x_{ij}^{{{\mathfrak {p}}}} \in \lbrace 0, 1\rbrace , \qquad \forall (i, j)\in {\mathcal {E}}^{{\mathfrak {p}}}, \end{aligned}$$

(9)

$$\begin{aligned}&y_{kj}^{{\mathfrak {p}}} \in \lbrace 0, 1\rbrace , \qquad \forall j\in {\mathcal {N}}^{{\mathfrak {p}}}, j\ne s^{{\mathfrak {p}}}, t^{{\mathfrak {p}}}, \forall k\in K. \end{aligned}$$

(10)

The objective function (4) minimizes the sum of all aerial refueling operation costs. Furthermore, in the objective function (5), the number of aerial refuelings is minimized. Constraints (6) demonstrate that the aircraft must start flying from node $s^{{\mathfrak {p}}}$ and end its flight at node $t^{{\mathfrak {p}}}$. Moreover, they show that when the aircraft enters an intermediate node, it must also exit that node. Constraints (7) ensure that when the aircraft enters a node, it is refueled by a tanker aircraft. To prevent allocating more than one tanker aircraft to an aerial refueling node, Constraints (8) are applied. Constraints (9) and (10) are required as all variables are binary.

In most real-world problems, aircraft refuelings on different paths should be investigated. To extend the proposed problem, it is sufficient to first consider all paths as a network, G(N, E) , where N and E contain the nodes and arcs of all paths, respectively. Then, the network, ${\mathcal {G}}( {\mathcal {N}}, {\mathcal {E}})$, corresponding to G(N, E) can be easily obtained simply by using the previously mentioned rules on each path. Finally, the proposed model is applied to each path in ${\mathcal {G}}( {\mathcal {N}}, {\mathcal {E}})$. Any $O-D$ pairs could be considered as a path. In fact, each node can play the role of an origin or destination.

4 Solution methodology

Before starting to solve the proposed model, its computational complexity is investigated. Here, we attempt to show the computational complexity of the proposed formulation by empirical evidence. For this purpose, the proposed model was solved exactly by considering each objective function separately in non-interval form. Some network instances were generated, and the single objective models were solved by the CPLEX solver of GAMS software. The computational times of the optimal solution obtained for each objective function are presented in Table 1. The network with 50 nodes needs more than 70,000 s of running time to be solved optimally. The phenomenon of combinatorial explosion can be observed here. Exponential functions for the first and second objectives are fit to the CPU times of GAMS with $R^{2}=0.8914$ and $R^{2}=0.8892$, respectively (Figs. 2, 3).

Table 1 The results of computational complexity experiments

Fig. 2

The computational times of the optimal solution for the first objective function and an exponential function fit to them

Fig. 3

The computational times of the optimal solution for the second objective function and an exponential function fit to them

Considering the computational results obtained from the aforementioned empirical evidence as well as the interval multi-objective nature of the proposed problem, for the case of large size instances, the presented model faces serious computational difficulties that must be solved. These difficulties motivated us to develop some algorithms to solve the problem. In this section, we attempt to present effective algorithms for solving the proposed model. An attempt has been made to ensure that the algorithms preserve the interval multi-objective nature of the problem and have acceptable CPU times and reasonable computational efforts. In the rest of this section, two new algorithms based on the modified label-correcting algorithm (Ahuja et al. 1993) and genetic algorithm (GA) are proposed, and their structures are discussed in detail.

4.1 Labeling algorithm

The node labeling algorithm as an applicable method was used by Kannon et al. (2014, 2015) to solve the aircraft routing problem with refueling. A new version of the modified label-correcting method, called the labeling algorithm (LA), is presented in this paper. According to the proposed problem, additional entries are used in the node labels. Instead of using traditional methods for converting two objectives into a single objective function, the values of the two objectives are considered as the elements of a vector. This new algorithm is detailed below.

Generally, in LA, the label corresponding to each node of ${\mathcal {G}}^{\mathfrak {p}}$ is

$$\begin{aligned} L^{\mathfrak {p}}(j)=\left( \left( \left[ w_{j}^{l}, w_{j}^{u}\right] , n_{j}\right) , sta (pred(j)), pred(j)\right) . \end{aligned}$$

The first component of $L^{\mathfrak {p}}(j)$, i.e., $([w_{j}^{l}, w_{j}^{u}] , n_{j})$, is a vector including two elements. Moreover, the first element of this vector represents the total cost of the aerial refueling operations from node $s^{{\mathfrak {p}}}$ to j, which is given by an interval number, where $w_{j}^{l}$ and $w_{j}^{u}$ are lower and upper bounds, respectively. The second element in this vector shows the total number of aerial refueling operations from the origin $s^{{\mathfrak {p}}}$ to node j. The first component of the node label shows that the inherent multi-objective nature of the problem is preserved, which may be considered an advantage of LA. In this manner, both objective functions are investigated simultaneously. Moreover, pred(j) in the second and third components of $L^{\mathfrak {p}}(j)$ denotes the node immediately prior to node j on path ${\mathfrak {p}}$. The station from which a tanker aircraft is allocated to pred(j) is given by sta(pred(j)).

At the beginning of the algorithm, each node of path ${\mathfrak {p}}$ is labeled as follows:

$$\begin{aligned} L^{\mathfrak {p}}(s^{{\mathfrak {p}}})&=( ([0, 0] , 0), -, -),\\ L^{\mathfrak {p}}(j)&=( ([\infty , \infty ] , \infty ), -, -) \quad \forall j \in {\mathcal {N}}^{{\mathfrak {p}}}, \quad j\ne s^{{\mathfrak {p}}} . \end{aligned}$$

A set ${\mathcal {D}}^{\mathfrak {p}}(j)$ of labels is associated with each node $j \in {\mathcal {N}}^{{\mathfrak {p}}}$. Initially, this set contains the abovementioned labels. The set ${\mathcal {D}}^{\mathfrak {p}}(j)$ is updated during the algorithm in such a way that no first component of each element (each label) in ${\mathcal {D}}^{\mathfrak {p}}(j)$ is dominated by another first component of the labels in ${\mathcal {D}}^{\mathfrak {p}}(j)$. We try to improve LA according to the inherent interval multi-objective nature of the proposed problem and to make it more applicable to real-world situations. To do so, the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$ is used in the process of determining the dominant objectives, as explained in detail during the algorithm procedure. Another set that is required is SE. This set initially contains $s^{\mathfrak {p}}$ (i.e., $SE =\lbrace s^{{\mathfrak {p}}} \rbrace$) and is updated during the algorithm. At first, the only member of SE is removed, and all arcs $( s^{{\mathfrak {p}}} , j)$ emanating from node $s^{{\mathfrak {p}}}$ in ${\mathcal {G}}^{\mathfrak {p}}$ are found. Next, to create a new label for each node j on path ${\mathfrak {p}}$, where $( s^{{\mathfrak {p}}} , j)\in {\mathcal {E}}^{{\mathfrak {p}}}$, a label-scanning process should be started. With regard to the label of $s^{{\mathfrak {p}}}$ and the fact that no refueling occurs at node $s^{{\mathfrak {p}}}$, the new label of j will be $L^{\mathfrak {p}}(j)=( ([0, 0] , 0), -, s^{{\mathfrak {p}}})$. Then, $L^{\mathfrak {p}}(j)$ is added to the set ${\mathcal {D}}^{\mathfrak {p}}(j)$, and the first components of the two labels in ${\mathcal {D}}^{\mathfrak {p}}(j)$ are compared with each other according to the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$. Obviously, $([0, 0] , 0) \preccurlyeq _{IV} ([\infty , \infty ] , \infty )$, which indicates that the vector ([0, 0] , 0) dominates the vector $([\infty , \infty ] , \infty )$ due to the minimization inherent in the objectives in the proposed model. Hence, the label of j with the dominated first component is removed from ${\mathcal {D}}^{\mathfrak {p}}(j)$. Accordingly, the set ${\mathcal {D}}^{\mathfrak {p}}(j)$ is updated. Since $j \notin SE$, it is added to the set SE.

In the preceding discussion, the algorithm was described for the case in which the set SE contains only node $s^{{\mathfrak {p}}}$, at which no refueling is performed. In the following descriptions, the algorithm is explained for the case in which SE contains nodes at which refueling may be performed.

In the rest of the algorithm, a member of SE, suppose i, is selected and removed from SE. Then, all arcs $(i, j)\in {\mathcal {E}}^{{\mathfrak {p}}}$ on path ${\mathfrak {p}}$ are determined, and the label-scanning process is performed. Obviously, ${\mathcal {D}}^{\mathfrak {p}}(i)$ may contain some labels whose first components are incomparable, considering the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$. To find possible new labels for each node j, first the following vector is computed regarding the first component of each member of ${\mathcal {D}}^{\mathfrak {p}}(i)$:

$$\begin{aligned} \left( \left[ w_{i}^{l}, w_{i}^{u}\right] , n_{i}\right) +\left( \left[ c_{ki}^{l}, c_{ki}^{u}\right] , 1\right) = \left( \left[ w_{i}^{l}+c_{ki}^{l}, w_{i}^{u}+c_{ki}^{u}\right] , n_{i}+1\right) \quad \forall k \in K. \end{aligned}$$

Then, the vectors obtained for all members of ${\mathcal {D}}^{\mathfrak {p}}(i)$ are compared with respect to the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$, and the nondominated ones are kept. The labels for these nondominated vectors are created and added to the set ${\mathcal {D}}^{\mathfrak {p}}(j)$. Finally, the first components of all labels in the set ${\mathcal {D}}^{\mathfrak {p}}(j)$ are compared with each other, and all dominated ones are removed from ${\mathcal {D}}^{\mathfrak {p}}(j)$. Now, the set ${\mathcal {D}}^{\mathfrak {p}}(j)$ is updated. Node j should be added to the set SE if the set does not include it. Once again a member of SE is selected, and the same process is executed while $SE\ne \phi$. The route traveled by the aircraft and the allocations of tanker aircraft from stations to aerial refueling nodes, which may not be unique, can be determined via post-processing by backtracking through the predecessor labels. The proposed algorithm is shown by the pseudo-code in Fig. 4.

Fig. 4

The pseudo-code of the labeling algorithm

4.2 Genetic algorithm

Recently, genetic algorithms (GA) have been applied to many problems (Roy and Mula 2016; Spiliopoulou et al. 2017; Marinakis et al. 2009). GA is a stochastic search technique based on the mechanism of natural selection and natural genetics (Holland 1992). GA begins with a randomly selected population of chromosomes represented by strings. The chromosomes in the population represent potential solutions to the problem of interest. Each chromosome in the population is evaluated using some measure of its fitness. By using some neighborhood operators, e.g., crossover and mutation, GA can find new solutions (named offspring) with characteristics that may not already exist in the population and that differ from those of some of the selected solutions of the population (named parents). Afterward, the offspring are compared with the population (according to their fitness values) and substituted for the worst chromosomes in the population; thus, the next generation is created. This procedure continues until a termination condition is satisfied. In the following paragraphs, the implementation details of GA according to our problem are explained.

GA requires a genetic representation of the solution domain. An appropriate chromosome representation is important for the successful application of GA. Therefore, according to the problem in this study, we consider each chromosome in a fixed-length multiple-string form (matrix form). Each chromosome represents a feasible solution in ${\mathcal {G}}^{\mathfrak {p}}$. The first string represents the set of nodes ${\mathcal {N}}^{{{\mathfrak {p}}}}$. The locus of the chromosome in the first string shows a node on ${\mathfrak {p}}$. Each gene takes the value 1 if the receiver aircraft enters the corresponding node on path ${\mathfrak {p}}$ and 0 otherwise . The genes of the first locus and the last locus are equal to one and always reserved for the source node, $s^{{\mathfrak {p}}}$, and the destination node, $t^{{\mathfrak {p}}}$, respectively. The length of the chromosome is equal to the total number of nodes on path ${\mathfrak {p}}$. Each of the remaining strings of the chromosome shows one refueling station. In fact, the number of strings in the chromosome is equal to the size of set K plus one. Each gene in the string of the k-th station takes the value 1 if the aerial refueling nodes in the first string are served by a tanker aircraft from the k-th station and 0 otherwise. An example of the chromosome encoding for aerial refueling nodes $\{B, C\}$ on path ${\mathfrak {p}}$, $s^{{\mathfrak {p}}}-A-B-C-D-t^{{\mathfrak {p}}}$, in ${\mathcal {G}}^{\mathfrak {p}}$, assuming two stations (node B is served by a tanker aircraft from the second station and node C is served by the first station) is shown in Fig. 5.

Fig. 5

An example of a chromosome representation

Once the chromosome representation is defined, GA proceeds to generate an initial population of solutions ($pop_{0}$). The initial population is generated randomly. The fitness function of each chromosome in the population is then calculated. In fact, the fitness function measures the quality of the chromosomes. In this study, the fitness function is considered as a vector-valued function including two elements. The first element is an interval that represents the total cost of aerial refuelings, and the second element is the total number of refuelings of the chromosome. Then, the fitness function is used as a criterion for selecting chromosomes for the crossover operation. In this regard, the fitness functions of chromosomes are compared using the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$, and two nondominated chromosomes are selected as parents for the crossover operation.

Now, the selected parents are ready for crossover to create new offspring. The chromosomes selected for crossover (parents) should have at least one gene (node) in common other than the source and destination nodes. If they do not have any nodes in common, another pair of parents should be selected from the population. The node in common is a crossover site. If the parents have more than one node in common, one node is selected randomly as a cross site. To create offspring, the fitness function of the parents should be compared according to the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$ in two steps. First, the fitness functions corresponding to the source node up to the crossover site of the parents are compared, and the nondominated part is preserved for the first part of the offspring. Then, the fitness functions corresponding to the crossover site up to the destination node of the parents are compared and, the nondominated part is preserved for the second part of the offspring. The offspring are thus created. If in each step of the comparison procedure the fitness functions are incomparable according to the order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$, then both parts of the parents are preserved. As an example, the crossover operator of the parents in Fig. 6 can be referred to, where the interval costs of aerial refueling operations at nodes B, C and D, which are served by stations 1 and 2, are $c_{1B} = [3, 4], c_{2B} = [5, 6], c_{1C} = [2, 4]$, and $c_{2D} = [3, 2]$.

Fig. 6

An example of a crossover operation

Once the offspring are created, the mutation operator is applied to them. The purpose of mutation is to preserve diversity. Mutation alters one gene of the offspring with a probability equal to the mutation rate $p_{m}$. In this paper, bit-reverse type mutation is adopted for one of the strings, except the first string of the offspring. In the end, each offspring is compared with all chromosomes of the population, and the worst chromosome is replaced by the offspring. If the offspring are incomparable with the chromosomes, they are added to the population, and the next generation is created. This procedure continues until a termination condition is satisfied, which can be stated in terms of either CPU time or the number of iterations.

5 Numerical experiments

To tackle the problem introduced in Sect. 3, two algorithms were proposed in Sect. 4, and the performance of the algorithms is studied in this section. The required experiments are performed in the following subsections. In Sect. 5.1, an example network with 11 nodes, which is sufficiently small to report the details of the obtained solutions, is presented. In Sect. 5.2, we test and compare the solution methods in 21 instances of networks in different cases, which will allow us to evaluate how well the algorithms perform in large, real-world instances. The algorithms were coded in MATLAB 8.1.0.604 (R2013a), and all experiments were performed on a laptop equipped with a Core i5 Processor (2.40 GHz) and 4.00 GB RAM.

5.1 Network with 11 nodes

Consider an example network with 11 nodes and some arcs (Fig. 7). It is assumed that two predetermined stations containing tanker aircraft exist on the ground. The interval number, which is written on each arc, denotes the interval value for fuel consumption for traveling that arc (measured in pounds). Furthermore, interval costs, $c_{kj}$, $k=1, 2, j=1,2,\ldots , 11$, for allocating stations to the nodes are specified as follows:

$$\begin{aligned} c_{11}&= [3, 4]&c_{12}&= [12, 14]&c_{13}&= [21, 22]&c_{14}&= [4, 5]&c_{15}&= [2, 4]&\\ c_{16}&= [1, 2]&c_{17}&= [7, 8]&c_{18}&= [11, 13]&c_{19}&= [3, 4]&c_{1,10}&= [2, 3]\\ c_{1,11}&= [9, 10]&c_{21}&=[7, 8]&c_{22}&= [20, 21]&c_{23}&= [19, 21]&c_{24}&= [7, 9]\\ c_{25}&= [3, 4]&c_{26}&= [3, 4]&c_{27}&= [10, 11]&c_{28}&= [5, 7]&c_{29}&= [5, 6]\\ c_{2,10}&= [4, 4]&c_{2,11}&= [11, 13]. \end{aligned}$$

Moreover, two ranges are considered for receiver aircraft. One is $R=26{,}000$ pounds, which was also used in the study by Kannon et al. (2015). They utilized $R=26{,}000$ based on the fuel capacity of a specified aircraft. Another range considered in this subsection is $R=22{,}000$ pounds. The shortest path between each $O-D$ pair is found. The results for the 11-node network obtained by using the labeling algorithm for the two ranges, $R=26{,}000$ and $R=22{,}000$ (measured in pounds), are presented in Table 2. Using LA, IV-efficient solutions and their corresponding objective function values for some specific $O-D$ pairs are presented in this table. Here, the symbol i[k] denotes that the aircraft is refueled at node i by a tanker aircraft from the k-th station. $i[-]$ indicates that the aircraft is not refueled at node i. As an example, in Table 2, $2[-] \longrightarrow 4[1]\longrightarrow 6[-]$ is an IV-efficient solution between nodes 2 and 6 when $R=26{,}000$. This solution implies that, for traveling through nodes 2 and 6, refueling at node 4 is necessary. In addition a tanker aircraft from the first station is allocated to node 4. Table 2 indicates that for $R=22{,}000$, three IV-efficient solutions are obtained along the route between nodes 2 and 6. All of these solutions specify the same path, $2\longrightarrow 3\longrightarrow 4\longrightarrow 6$; however, the allocations of the stations to nodes 3 and 4 along this path, at which refueling should be performed, are not the same. The IV-efficient solutions for the $O-D$ pair $1-11$ considering $R=26{,}000$ show that it is possible to have IV-efficient solutions with different numbers of refueling operations. In this sense, the solution $1[-] \longrightarrow 2[1]\longrightarrow 4[1]\longrightarrow 10[1]\longrightarrow 11[-]$ indicates that three refueling operations are necessary. However, the solution $1[-] \longrightarrow 2[1]\longrightarrow 4[1]\longrightarrow 6[1]\longrightarrow 10[1]\longrightarrow 11[-]$ shows that four refueling operations are needed. In total, LA obtained 51 and 71 IV-efficient solutions for all $O-D$ pairs in the 11-node network for ranges 26,000 and 22,000, respectively.

The results for the 11-node network, obtained using GA with population sizes of 5, 10, and 15 for 100 generations with the same ranges as LA are presented in Tables 3, 4, and 5. The IV-efficient solutions and the corresponding objective functions are obtained for the same $O-D$ pairs that were selected for LA.

The results in Table 3 are obtained for $pop_{0}=5$. As shown in the table, for $R=26{,}000$, five IV-efficient solutions are found for traveling from node 1 to node 11. All of these solutions are dominated by the solutions obtained by LA (Table 2) in the same condition. Similar results are obtained for $O=3$ and $D=11$. For $O=2$ and $D=11$, considering $R=26{,}000$, GA yields two solutions. One, ([6, 8], 2), is the same as that obtained by LA. However, the other, ([7, 10], 3), is new and is incomparable with LA’s solutions. In fact, due to the characteristics of LA and the defined order $\hbox{``}\preccurlyeq _{IV}\hbox{''}$ for comparison, LA misses this solution. The final $O-D$ in $R=26{,}000$ with $O=2$ and $D=6$ has the same solution as LA’s solution in Table 2. Consider the solutions in the case of $R=22{,}000$ in Table 3. For $O=1$ and $D=11$, GA can find only three of the nine solutions found by LA in Table 2. For the path from $O=3$ to $D=11$, the vector ([11, 13], 3) in Table 3 is dominated by ([7, 10], 3) in Table 2. Furthermore, GA can find an extra solution, ([10, 14], 3), that is incomparable with all solutions obtained by LA. For $O=2$ and $D=11$, GA finds two more solutions than LA. The solutions in Tables 2 and 3 are the same for the path from $O=2$ to $D=6$.

To obtain the results in Tables 4 and 5, GA is run for $pop_{0}=10$ and $pop_{0}=15$, respectively. With small population sizes such as 5 and 10, some of the solutions generated by GA are dominated by the solutions obtained by LA. In the results obtained by GA when $pop_{0}=15$, all of LA’s solutions plus some extra solutions are obtained for some selected $O-D$ pairs. In this case, as observed in Table 3, the extra solutions are incomparable with all of LA’s solutions. In fact, GA’s results depend on the size of the initial population. Increasing the initial population size improves the solutions obtained by GA and helps GA obtain extra solutions that are incomparable with those of LA. In the 11-node network, GA with $pop_{0}=15$ obtains 53 and 77 IV-efficient solutions for all $O-D$ pairs for $R=26{,}000$ and $R=22{,}000$, respectively. Obviously, the number of GA solutions is larger than the number of LA solutions. However, in this case, the running time also increases. In fact, GA even requires a long time to obtain the same solutions obtained by LA. Computational times are not reported in these tables because the network is very small, but these times are discussed in detail in the next subsection.

Fig. 7

The 11-node network

Table 2 Results of 11-node network for LA

Table 3 Results of 11-node network for GA with $pop_{0}=5$

Table 4 Results of 11-node network for GA with $pop_{0}=10$

Table 5 Results of 11-node network for GA with $pop_{0}=15$

5.2 Randomly generated networks

To generate an example network, n nodes were randomly generated in the square $[0, 30{,}000]\times [0, 30{,}000]$. Then, according to the Euclidean distance between these nodes, each node was connected to at most m (an arbitrary natural number) nearest adjacent nodes. It was assumed that the direction of the arc between nodes i and j was from i to j if $i <j$. The amount of fuel consumed for each arc (i, j) was determined considering the Euclidean distance between nodes i and j. Moreover, we generated integer values for the lower and upper bounds of the fuel consumption interval for each arc (i, j) by multiplying the specified Euclidean distance by the coefficients 0.95 and 1.05, respectively, and subsequently rounding (the values of the coefficients chosen to construct the interval were taken from the study by Kannon et al. (2015)). Then, the shortest path between each $O-D$ pair was found. The network example was constructed using all of these shortest paths.

To investigate the efficiency of the proposed formulation and the algorithms in real-world conditions, seven random networks were generated by the above method. It was assumed that there were 10 predetermined stations on the ground, and the receiver’s range was set to $R=26{,}000$.

Table 7 compares the solution times and the number of solutions of both LA and GA on 21 instances of networks in different cases. In this table, “No. of solutions” is the number of IV-efficient solutions obtained by the algorithms, and “Time” is the CPU time required to run the algorithms to obtain IV-efficient solutions for all $O-D$ pairs. We used the results generated by LA as a guideline to determine whether good solutions were reached by GA. As mentioned previously, on the basis of the initial population, GA may find solutions that are dominated by the solutions of LA that are not in common with those of GA. In Table 7, “No. of solutions in common” shows the number of solutions that LA and GA have in common. To investigate the effect of the initial population size on the obtained solutions and the running time, GA was run with three initial population sizes, $pop_{0}=50, 100$, and 200, for 100 generations. We tested mutation rates of 0.0, 0.1, 0.2, 0.7, 0.8, and 0.9 for only two random networks with 50 and 100 nodes and $pop_{0}=50$ to determine how this rate affects the performance of GA (Table 6). In some cases, as the mutation rate incrased, the number of solutions obtained by GA and the number of solutions in common increased, and the running time decreased. Therefore, we assumed $p_{m}=0.8$ in Table 7.

The results in Table 7 show that GA can find a smaller or equal number of solutions compared with LA. Moreover, GA requires too much time to obtain these solutions. Despite the long time, GA is still unable to find all of LA’s solutions in cases in which “No. of solutions in common” is smaller than “No. of solutions” in LA. In such cases (where GA is unable to find all of LA’s solutions), the solutions obtained by GA that are not in common with those found by LA may be dominated by those solutions of LA that are not in common with the solutions of GA. For example, in the network with 50 nodes and $pop_{0}=50$, LA takes only 183.25 seconds to yield 3118 IV-efficient solutions. GA reports 1952 solutions in a time equivalent to almost seven times longer than the running time for LA. Moreover, GA finds only 1562 of LA’s solutions. Thus, 390 of the solutions ($1952-1562=390$) obtained by GA may be dominated by the 1556 solutions ($3118-1562=1556$) obtained by LA that are not in common with those of GA.

The results show that an increase in the initial population size leads not only to an increase in the number of GA solutions but also to an increase in the running time. In large-scale networks, such as networks with 200, 300, 400, and 500 nodes, as the population increases, the running time increases exponentially. As an example, in the network with 200 nodes and $pop_{0}=200$, GA requires more than 12 hours of running time. Therefore, we terminate GA within 7200 s (i.e., 2 hrs). In contrast to the long running time required by GA, LA can obtain IV-efficient solutions in large-scale networks in a very short running time (less than 3 minutes). Generally, we can conclude that the performance of LA is better than that of GA.

Table 6 Results of using different mutation rates for GA

Table 7 Comparison of LA and GA with different population sizes

6 Conclusion

In this paper, an aerial refueling problem was investigated. Due to the limited range of receiver aircraft, aerial refueling is necessary. In this context, valid combinations of aerial refueling nodes were determined. To select suitable valid combinations, two criteria, minimization of the total cost of tanker aircraft allocations to aerial refueling nodes and minimization of the number of aerial refueling operations, were considered. Furthermore, due to the inherent uncertainty of real-world applications, the main problem of this paper was modeled as an interval multi-objective zero-one integer programming problem. Two new algorithms, namely, customized variants of labeling and genetic algorithms, respectively, were design to solve this model. Comparisons of the performance of the algorithms showed that the labeling algorithm obtains solutions in a short running time. However, as population size increases, the genetic algorithm tends to generate more nondominated solutions than the labeling algorithm at the expense of a much longer running time. As a result, it can be concluded that the performance of LA is better than that of GA.

Because a large set of IV-efficient solutions may be possible, compromise solutions may be desirable. Filtering methods would be suitable for this problem and could be considered as a topic for further research.