Optimal Fleet Assignment Using Ant Colony

Algorithm
Rashid Anzoom M. Ahsan Akhtar Hasin
Department of Industrial and Production Engineering Department of Industrial and Production Engineering
Bangladesh University of Textiles Bangladesh University of Engineering and Technology
Dhaka, Bangladesh Dhaka, Bangladesh
rashidanzoom@butex.edu.bd aahasin@ipe.buet.ac.bd

Abstract— Demand for logistical services is highly dynamic, selection of routes and aircraft. Flight routes are selected
due to its high market growth. In Bangladesh, air logistics is through cautious analysis of customer demand in different
evolving at a fast pace, both in terms of passenger and cargo locations. Similarly, aircraft are selected on the basis of
transportation. As a result, several local private and different performance parameters. Next, the airline is
international airlines are trying to capture market share in this required to optimally fulfill the customer demand with the
promising sector. For survival in such tough competition, available aircraft, which is known as the fleet assignment
optimization in operations is indispensable. This research problem (FAP). It involves properly assigning aircraft of
focuses on the optimal fleet assignment with Ant Colony different capacities to the scheduled flights, based on
algorithm. In this rapidly expanding market, short to mid-term
equipment capabilities, operational costs, and potential
demands of passenger were estimated using regression
analysis. Then, from a database of routes and aircraft capacity,
revenues. The objective of the Fleet Assignment Model
a model was developed to estimate profitability from fleet (FAM) is to maximize the profit from these assignments.
assignment with relative ease. Finally, ant colony algorithm This model can also be useful in directing which types of
was used to find the optimal assignment. Although previous aircraft to acquire, especially when a new airline enters the
researches on fleet assignment were done using Genetic market or an existing airline extends its route.
algorithm, only current-level of demand for logistical service For a better understanding of the fleet assignment
was considered. This research considers it as dynamic and
problem, a popular reference is the basic fleet assignment
projected into the future. The results obtained in this research
model, provided by Hane et al. (1995) [2]. The objective of
show that dynamic demand consideration gives much better
results as well as better utilization of resources. And these
this model is to select the fleet assignment that maximizes
contributed to the reduction of operational cost as well as the profitability, or equivalently, minimizes operating costs less
increase in revenue. As a result, profit was optimized. For mid- total revenue. In this research work, a modified form of
term and long-term projection, demand becomes gradually Hane’s Model has been developed and used for fleet
probabilistic. However, this research considered it as assignment. The objective remains unchanged- that is to
deterministic; otherwise, the problem becomes an NP-hard assign aircraft to scheduled routes with a view to maximizing
problem, which is difficult to solve. This research is expected to the profit. However, the calculation of profit requires the
be of immense help to the air industry of Bangladesh. Because knowledge of revenue and cost from flight operation-that is
of similarity in business nature, this can be marginally adapted where the modification has occurred.
in other countries as well.
Calculation of airline cost can be conducted in two ways-
Keywords— logistics; fleet assignment problem; ant colony Functional and Administrative Approach. [3] In the
algorithm administrative approach, airline cost consists of Salaries,
Materials Cost, Service Cost, Landing Fee etc. Functional
Approach, on the other hand, divides operating cost into
I. INTRODUCTION
three sub-groups: Aircraft operating cost, Ground operating
Airline industry is one of the fastest growing industries in cost and System operating costs. However, majority of the
the world. According to Air Transport Action Group revenue obtained by airlines generate from a single source-
(ATAG), in 2016, the global airline industry consisted of Ticket Sales. As a result, earnings from a flight is heavily
1402 commercial airlines operating 32.8 million flights with dependent upon the pricing of the ticket. Traditionally, there
26065 commercial aircraft and providing service to 3883 are two tiers of seat available- business and economy [4].
airports carrying roughly 4.1 billion customers [1]. This However, now-a-days, airlines offer different categories of
inclination towards air transportation can be attributed to the seats based on factors like - date of purchase, available
increasing significance of time and convenience among amenities, and seat location. Pricing the ticket too low might
people. The airline industry is also highly advanced in bereft the company of attainable profit. Contrarily,
technological aspects. With a persistent focus on identifying overpricing of tickets might lead to curtailment of customer
new and emerging technologies, they strive to enhance and market share. Hence, it is essential to select a ticket price
business efficiency and improve customer experiences. in the light of both the profitability of the company as well as
However, to stay conversant with the contemporary the pricing of the competitors. Another important factor to be
technologies, the required expenditure has to be quite lofty- noted is Load Factor- the percentage of total seats sold on a
comprising both the costly acquisition of aircraft as well as route. [5] As the value of load factor differs along flight time,
maintaining high operating cost for regular flights. These route and other factors, its incorporation in fleet assignment
have turned the task of retaining profitability into a grueling model should provide a better and realistic estimation of the
one for the airlines. possible income from a flight.
For ensuring competitiveness and profitability In this paper, the profit from a fleet assignment is
simultaneously, planning in an airline needs to be done with modeled to be a function of aircraft seat capacity and the
utmost vigilance. Two key decisions in this regard are the

978-1-5386-9500-5/18/$31.00 ©2018 IEEE

flight distance. This involves developing a method for III. MODEL FORMULATION
determining competitive ticket pricing based on flight length The proposed methodology introduces chronological
as well as consideration of load factor in revenue steps to determine the desired optimal combination of
computation. For facilitating these modifications, regression aircraft and route. The steps are described in the following:
analysis was chosen due to its reasonable accuracy and
simpler implementation [6]. Moreover, the classification of
aircraft and flights have been built upon their seat capacity A. Forecast of Load Factor
and flight distance respectively. Two types of aircraft that In this study, load factor has been considered as a
have been defined are Narrow Body Aircraft (Single Aisle) variable of time only. By applying regression analysis on the
and Wide Body Aircraft (Double Aisle). And flights have load factor data of the last 15 years, the following equation
been identified either as short-haul flight(d d<1000 km) or has been developed for calculating load factor for a particular
long-haul flight (d>1000 km) in this research. year, y-
Finally, Ant Colony Algorithm has been employed to the 75.914 + 0.41375( y − 2001)
modified model to identify the optimal assignment attaining LF = (1)
100
maximum profit. It is a meta-heuristic optimization method
inspired by the foraging behavior of ants using pheromone.
B. Calculation of Average Ticket Price
Inherent parallelism and rapid convergence have contributed
to its increased popularity. The three main components in an As previously mentioned, airlines usually offer two
ACO algorithm are: solution construction, management of categories of air seats- business and economy. However, in
pheromone trails, and additional techniques; e.g. local search this research, considering the variety of prices on tickets
[7]. Furthermore, results obtained from the optimization were offered, the seats have been divided into five categories-
validated using Hungarian Algorithm. premium, business, regular, economic and promotional.
Having known their proportion of the total seats, the average
ticket price can be calculated using the equation below-
II. LITERATURE REVIEW
Fleet Assignment has been defined by Peter Belobaba, Tavg = aRP + BRb + cRr + dRe + eR pr (2)
Amedio Odoni, and Cynthia Barnhart as the profit-
maximizing assignment of fleet types to flight legs in the Here, Rp, Rb, Rr, Re, and Rpr denote the ticket prices of
airline’s network, without using more than the available premium, business, regular, economic and promotional
aircraft and ensuring balance by aircraft type at each airport category seats respectively. And the proportion of the total
location [3]. Several works have been done previously on the seats occupied by these categories are represented by a, b, c,
optimization of fleet assignment problem. Jeph Abara d, and e. While formulating this model, values of a, b, c, d
formulated and solved it as an integer linear programming and e have been assumed as 0.04, 0.06, 0.4, 0.3 and 0.2
model, where the objective functions were proposed to be correspondingly.
profit maximization, cost minimization or optimal utilization
of a particular fleet type [8]. Ahmed Abdelghany and Khaled C. Calculation of Competitive Ticket Price
Abdelghany marked seat capacity and flight distance as the To stay competitive against existing rival airlines, a
two main characteristics of aircraft while planning fleet database has been built consisting ticket prices of different
assignment [9]. William M. Swan & Nicole Adler, in their airlines in different routes. And using equation (2), the
research work, developed an expression for calculating the average ticket prices on different routes were calculated.
total operating cost in a flight as a function of these two Next, with the implementation of regression analysis, the
factors [10]. Further research on airline cost was done by competitive ticket price for a route has been expressed as a
Yongha Park and Morton E. O. Kelly, where data of 22 function of flight distance. Two equations have been used to
aircraft types from 15 major US airlines were used to model do that- equation (3) for short-haul and equation (4) for long-
the financial and operating data as an Integer knapsack haul operation:
problem and optimize aircraft selection [11]. Moreover, J.
Zuidberg indicated that load factor, aircraft utilization, and Tis = 0.262di + 10.886 (3)
aircraft size had influence over determining the operating
Til = 0.088di + 143.646 (4)
cost of an airline [12]. On the other hand, Kevin Pak and
Nanda Piersma discussed several commonly used techniques Here, di denotes the flight distance of route i. And the
for revenue management in the airline industry [13]. competitive ticket price for route i is represented by Tis and
However, there does not exist any quantitative model for Til in case of short-haul and long-haul flights respectively.
estimating revenue. This research intends to fill that gap,
through simultaneous prediction of cost and revenue using
the information of seat capacity and flight distance. As for D. Calculation of Revenue
Ant Colony Algorithm, it was first developed by M Dorigo With the formulation of expressions estimating
and G.D. Cario based on the imitation of foraging behavior competitive ticket price and load factor complete, the next
of Ants through pheromone [14]. John E Bell and Patrick R step leads to the computation of total revenue from a flight.
Mcmullen successfully applied it in solving the vehicle This can be expressed using the following equations for short
routing problem [15]. And H. Lourenco and D. Serra showed and long-haul flight respectively-
that application of Ant Colony Algorithm in general
assignment problem provided better results in terms of Rijs = Tis × LF × s j (5)
solution quality and computational expenditure compared to
Rijl = Til × LF × s j (6)
other methods [16]. This has prompted its inclusion in this
research for optimizing fleet assignment problem.
 Here, Rijs and Rijl denote the revenue from assignment of In case of both models, i designates the scheduled routes
aircraft j to route i in short haul and long-haul operation while j denotes the type of aircrafts available. Furthermore,
respectively. sj on the other hand represents the seat capacity m and n represent the total number of flights and aircraft
of aircraft model j. models respectively. The first constraint ensures that the
total number of assignments matches the total number of
flights. The second constraint has been employed to verify
E. Calculation of Flight Operating Cost
that only one aircraft is assigned to a single route. The third
In this study, the cost of operating a flight has been constraint indicates the binary nature of the decision of
estimated using the equation provided by Adler and Swan assignment xij -that is a flight is either assigned or not
[6]. The equations express cost as a function of flight assigned. And the final constraints ensure that the two
distance and number of seats in the aircraft and are found in different models are applicable to short-haul and long-haul
the following- flights accordingly.
Cijs = (di + 722) × ( s j + 104) × 0.019 (7)
Cijl = (di + 2200) × ( s j + 211) × 0.0115 (8)
IV. NUMERICAL ILLUSTRATION
cijs and cijl in these equations denote the costs associated
For the illustration of this model, two distinct assignment
with short-haul and long-haul flight operation respectively problems have been developed for long-haul and short haul
for aircraft j in route i. flights- each containing 5 aircraft and 5 routes. For ease of
understanding, the two problems have been named as Short-
F. Calculation of Flight Operating Cost haul Problem and Long-haul Problem. The basic information
(Aircraft seat capacity and route distance) of these two
With cost and revenue known for each route and aircraft, problems are shown in Table I and Table II.
it is now possible to calculate profit in each route-aircraft
combination. The formulations for both short and long route Firstly, estimation of the load factor needs to be done.
become- Using equation (1), the load factor for 2017 was found to be-
Pijs = Rijs − Cijs (9) 75.914 + 0.41375 × (2017 − 2001)
LF = = 0.825
Pijl = Rijl − Cijl (10) 100
Equation (9) can be used for calculating assignment profit Secondly, the values of the flight distance of the routes
for short haul operation while equation (10) should be used were applied in equation (3) and (4) to calculate their
for doing the same in long haul operation. corresponding competitive average ticket price. Table III
lists the competitive ticket price of the 10 routes mentioned
G. Final Model Formulation in the two problems.
With the formulation of profit calculation complete, the
modified Fleet Assignment Model can be developed for TABLE I. INFORMATION FOR SHORT HAUL PROBLEM
both Short and Long-haul flights. Their final formulations
are given below- Seat Flight
Aircraft Model Route
Capacity Distance (km)

Short-Haul Model:
m n
A333 335 Dhaka-Barishal 112
Maximize¦¦ Pijs xij
i =1 j =1
B735 132 Dhaka-Jessore 142
m n
s.t. ¦¦ x
i =1 j =1
ij =m (11) B739 177 Dhaka-Chittagong 211

n
A319 142 Dhaka-Sylhet 200
¦ xij = 1
j =1
(12)
B762 290 Dhaka-Rajshahi 198

xij = 1 or 0 (13)
di ≤ 1000 (14)
TABLE II. INFORMATION FOR LONG HAUL PROBLEM
Long Haul Model:
Seat Flight
m n Aircraft Model Route
Maximize¦¦ Pijl xij
Capacity Distance (km)
i =1 j =1
m n A336 266 Dhaka-Beijing 3025
s.t. ¦¦ x
i =1 j =1
ij =m (15)
MD83 410 Dhaka-Tehran 3960
n

¦x
j =1
ij =1 (16) B737 149 Dhaka-Male 2840

A319 142 Dhaka-Jakarta 3780

xij = 1 or 0 (17)
di > 1000 (18) B77W 550 Dhaka-Sydney 9069
 TABLE III. COMPETITIVE TICKET PRICE OF DIFFERENT ROUTES little time for optimization- only 4 and 6 iterations to reach
(SHORT HAUL AND LONG HAUL)
the optimum profit for short-haul and long-haul operations
Flight Distance
Competitive respectively.
Route Average Ticket
Type (km)
Price ($)
Dhaka-Barishal 112 40.23

Dhaka-Jessore 142 48.09

Short
Haul Dhaka-Chittagong 211 66.17

Dhaka-Sylhet 200 63.29

Dhaka-Rajshahi 198 62.76

Dhaka-Beijing 3025 803.44

Dhaka-Tehran 3960 1048.41

Long
Haul Dhaka-Male 2840 754.97

Dhaka-Jakarta 3780 1001.25

Dhaka-Sydney 9069 2386.96

Finally, ACO was applied to the problem using

MATLAB. The inputs for the two problems were expressed Fig. 1. Optimal Assignment For Short Haul Operation
in the following form
Short-haul Problem:

x = [112 142 211 200 198]

y = [335 132 177 142 290]

Long-haul Problem:

x = [3025 3960 2840 3780 9069]

y = [ 266 410 149 142 550]

Here, x denotes the flight distance whereas y denotes the

seat capacity of the aircrafts. And the parameters were set as
the following-

Maximum Number of Iteration=50

Number of Ants=40
Initial Pheromone, =10 Fig. 2. Optimal Assignment for Long Haul Operation
Pheromone Exponential Weight, =0.3
Evaporation Rate, =0.1

V. RESULT DISCUSSION AND VALIDATION

The result of optimization for both problems in
MATLAB can be inferred from Figure 1,2,3 and 4. The
resultant assignments have been expressed in a graph as
coordinate pairs of seat capacity and distance. Those graphs
are shown in figure 1 and figure 2. And the optimum profit,
as well as the number of iterations taken to reach the
optimum profit, have also been provided through a graph
(Figure 3 and Figure 4). For simplification, these optimum
assignments and the resultant profit has been presented in a
table IV and Table V
From the graphs, it is apparent that the optimization of
fleet assignment results in a profit of 25232.96$ for short
haul operation, whereas, for long-haul operation, the profit
becomes 577266.74$. It is also notable that ACO took very Fig. 3. Profit vs Iteration for Long Haul Operation
 TABLE VII. RESULT OF LONG HAUL OPTIMIZATION USING
HUNGARIAN ALGORITHM

Aircraft Model
Route
A 336 MD83 B737 A319 B77W
Dhaka-
4161.9 641.28 1421.71 814.71 3381.40
Beijing
Dhaka-
6083.9 1362.72 2409.30 1595.20 5037.30
Tehran
Dhaka-Male 10504.75 3022.01 4680.75 3390.60 8846.00
Dhaka-
9799.99 2547.49 4318.63 3104.40 8238.80
Jakarta
Dhaka-
9671.85 2709.39 4252.80 3052.30 8128.50
Sydney
Fig. 4. Profit vs Iterations for Long Haul Operation As both results match, the solution by ACO is proved to
be authentic and believable.
TABLE IV. SUMMARY OF OPTIMAL FLEET ASSIGNMENT IN
SHORT HAUL OPERATION VI. CONCLUSION
Route Assigned Aircraft High growth and propitious future are drawing an ever-
increasing number of investments in the Aviation industry-
Dhaka-Barishal (DHK-BAR) B735 involving the launch of new airlines or expansion of the
Dhaka-Jessore (DHK-JSR) A319 current ones. However, operational complexities constantly
threaten to jeopardize this trend as maintaining profitability
Dhaka-Chittagong (DHK-CTG) A333
gets tougher day by day. That is why proper fleet assignment
Dhaka-Sylhet (DHK-SYL) B762 holds the key to prosperity for an airline. In this paper, a fleet
Dhaka -Rajshahi (DHK-RAJ) B762 assignment model has been developed to calculate
profitability as a function of seat and distance. And the
Optimum Profit= 25232.96$ application of ACO has assured quick convergence of
optimal solution to the problem. Therefore, this might
TABLE V. SUMMARY OF OPTIMAL FLEET ASSIGNMENT IN facilitate less difficulty in planning for new entrants in the
LONG HAUL OPERATION market with easily accessible information. However, the
modeling had been based on the data from airlines having
Route Assigned Aircraft
operations in Dhaka. It might be modeled with a different
Dhaka-Beijing (DHK-BEI) A336 data set to be applicable in different zones or even be
Dhaka-Tehran (DHK-THR) MD83 modified to a global model if data from different regions are
Dhaka-Male (DHK-ML) B737 accumulated. Besides, more factors can be taken into
consideration while calculating the load factor. There is also
Dhaka-Jakarta (DHK-JKR) A319
a scope of inclusion of uncertainty into the model. All these
Dhaka-Sydney (DHK-SDN) B77W ideas can be considered for inclusion in future research work.
Optimum Profit= 577266.74$. Nevertheless, this research is expected to assist airlines in
planning better to maintain profitability in their operation.
For verification of the results, Hungarian Algorithm was
applied to the problems as well. And the results came out to REFERENCES
be the same as ACO for both short-haul and long-haul
[1] Air Transport Action Group, Aviation Benefits Beyond Borders, July
operation. The results are shown in Table VI and Table VII, 2016.
where the cells written in bold italic arrangement represent [2] Hane et al., “The fleet assignment problem: solving a large-scale
the optimal assignment. integer program,” Math. Prog., vol. 70(1-3), October 1995, pp.211-
232.
TABLE VI. RESULT OF SHORT HAUL OPTIMIZATION USING [3] P. Belobaba, A. Odoni and C. Barnhart eds., The Global Airline
HUNGARIAN ALGORITHM Industry, 2nd ed., John Wiley & Sons, 2015.
[4] Q. Zhang, H. Yang & A. Zhang, “Market power and its determinants
Aircraft Model in the chinese airline industry”, Trans. Res. Pt. A: Pol. & Prac., vol.
64, 2014, pp.1-13.
Route
A333 B735 B739 A319 B762 [5] F. C. Y. Chen & C. Chen, “The effects of strategic alliances and risk
Dhaka- pooling on the load factors of international airline operations”, Trans.
4161.90 641.28 1421.71 814.71 3381.40
Barishal Res. Pt. E: Log. & Trans. Rev., vol. 39, no. 1, 2003, pp.19-34.
Dhaka- [6] N. Fumo & M. R. Biswas, “Regression analysis for prediction of
6083.90 1362.72 2409.30 1595.20 5037.30
Jessore residential energy consumption”, Ren. & Sus. Ener. Rev., vol. 47,
Dhaka- 2015, pp.332-343.
10504.75 3022.01 4680.75 3390.60 8846.00
Chittagong
Dhaka- [7] M. Dorigo et al., Ant Colony Optimization and Swarm Intelligenece,
9799.99 2547.49 4318.63 3104.40 8238.80 Springer-Verlag Berlin Heidelberg, 2004.
Sylhet
Dhaka- [8] J. Abara, “Applying integer linear programming to the fleet
9671.85 2709.39 4252.80 3052.30 8128.50 assignment problem”, Interfaces, vol. 19, no. 4,1989, pp.20-28.
Rajshahi
[9] A. Abdelghany and K. Abdelghany, Modeling Applications in the
Airline Industry, Routledge, April 2015.
[10] W. M. Swan and N. Adler, “Aircraft trip cost parameters: a function [14] M. Dorigo, G. D. Caro and L. M. Gambadella, “Ant algorithms for
of stage length and seat capacity”, Trans. Re. Pt. E: Log. And Trans. discrete optimization”, Art. Lif., vol. 5, no. 2, 1999, pp.137-172.
Rev., vol. 42, no. 2, 2006, pp.105-115. [15] J. E. Bell and PR McMullen, “Ant colony optimization techniques for
[11] Y. Park and M. E. O’Kelly, “Examination of cost-efficient aircraft the vehicle routing problem”, Adv. Eng. Info., vol. 18, no. 1, January,
fleets using empirical operation data in US aviation markets”, Jour. 2018, pp.41-48.
Of Air Trans. Man., vol. 69, 2018, pp.224-234. [16] H. R. Lourenco & D. Serra, “Adaptive search heuristics for the
[12] J. Zuidberg, “An econometric analysis of the factors affecting aircraft generalized assignment problem”, Math. & Soft. Comp, vol. 9, ,no. 2-
operating costs”, Jour. Of Air Trans. Man., vol. 40, 2014, pp.86-95. 3, 2002.
[13] P. Kevin and N. Piersma, Airline Revenue Management: An
Overview of OR techniques 1982-2001, ERIM Report Series, 2002.