Optimizing the Airline Routing Cost using Linear Programming and PSO Algorithm
الموضوعات : International Journal of Data Envelopment AnalysisShahram Saeidi 1 , Sahar Khoshfetrat 2
1 - Department of Industrial Engineering, Faculty of Engineering, Islamic Azad University, Tabriz Branch, Tabriz, Iran.
2 - Department of Mathematics, Islamic Azad University, Tabriz Branch, Tabriz, Iran.
الکلمات المفتاحية: Crew Scheduling Problem, Airline Routing, Linear Programming, Particle Swarm Optimization,
ملخص المقالة :
The transportation industry of any country represents the economic situation and the level of industrial development of that country, so this industry should be considered as one of the most essential factors in any society's economic, cultural, and social development. Exact planning and scheduling in airline transportation is inevitable. The crew scheduling problem is defined as creating a set of tasks to provide daily transportation services by creating a set of trips and assigning crews to them at minimum cost. So far, many studies have been carried out in this field, and researchers have presented several methods and algorithms to solve this problem. This research assumes that the air fleet consists of different types of planes, which are classified into different types based on their capacity and operating cost. The time it takes for a plane to travel back and forth depends on the type of plane and the length of the round trip. However, there may be no flights due to the proximity of the distance or low passenger demand. The main goal of this research is to determine the best flight schedule for the country's airlines using the linear planning method to minimize the total cost of transportation and passenger movement. Due to the non-linearity of the proposed model, a meta-heuristic method has also been developed based on the particle swarm optimization approach and simulated in MATLAB on sample problems in small, medium, and large dimensions. The calculation results indicate the efficiency and stability of the proposed method.
Available online at http://ijdea.srbiau.ac.ir
Int. J. Data Envelopment Analysis (ISSN 2345-458X)
Vol. 12, No. 3, Year 2024 Article ID IJDEA-00422, Pages 1-10
Research Article
International Journal of Data Envelopment Analysis Science and Research Branch (IAU)
|
Optimizing the Airline Routing Cost using Linear Programming and PSO Algorithm
Shahram Saeidi1 1, Sahar Khoshfetrat 2
1 Department of Industrial Engineering, Tabriz Branch, Islamic Azad University, Tabriz, Iran,
2 Department of Mathematics, Tabriz Branch, Islamic Azad University, Tabriz, Iran.
Received 3 March 2024, Accepted 19 June 2024
Abstract
The transportation industry of any country represents the economic situation and the level of industrial development of that country, so this industry should be considered as one of the most essential factors in any society's economic, cultural, and social development. Exact planning and scheduling in airline transportation is inevitable. The crew scheduling problem is defined as creating a set of tasks to provide daily transportation services by creating a set of trips and assigning crews to them at minimum cost. So far, many studies have been carried out in this field, and researchers have presented several methods and algorithms to solve this problem. This research assumes that the air fleet consists of different types of planes, which are classified into different types based on their capacity and operating cost. The time it takes for a plane to travel back and forth depends on the type of plane and the length of the round trip. However, there may be no flights due to the proximity of the distance or low passenger demand. The main goal of this research is to determine the best flight schedule for the country's airlines using the linear planning method to minimize the total cost of transportation and passenger movement. Due to the non-linearity of the proposed model, a meta-heuristic method has also been developed based on the particle swarm optimization approach and simulated in MATLAB on sample problems in small, medium, and large dimensions. The calculation results indicate the efficiency and stability of the proposed method.
Keywords: Crew Scheduling Problem, Airline Routing, Linear Programming, Particle Swarm Optimization
[1] Corresponding author: Email: sh_saeidi@iaut.ac.ir
1. Introduction
Planning in the transportation of airlines, both in the airport and the airline companies is inevitable and includes four stages: program, design, fleet allocation, flight chain allocation to aircraft, and crew planning [1]. The Crew Scheduling Problem (CSP) is divided into two subproblems: crew pairing and crew assignment. In some studies, the importance of producing good quality pairs has been emphasized because the pairs that are the output of the first stage are used as the input of the crew assignment stage. Although good-quality pairs do not always guarantee a good-quality final solution, it is impossible to achieve a good-quality final solution with weak pairs [2]. In program, design, which is the first stage of planning, efforts are made to select and plan the most suitable flight segments to maximize airline revenue. The results of the program design section are used in the fleet allocation section. The purpose of this section is to assign the fleet to scheduled flights, that is, one type of aircraft is assigned to each flight - so that the balance of the fleet flow is established in a chain and maintenance restrictions are not violated. This program should also satisfy the restrictions related to the crew, including the flight crew's working hours and rest time, and the number of aircraft required to implement the program should not exceed the number of available aircraft. Besides, operational costs and opportunity costs of losing passengers should be minimized. In determining the flight chain, which specific aircraft will be used for each flight should be determined. The purpose of this stage is to maximize airline companies' revenue. In the last stage of planning, after allocating each plane to the flight, planning is done for the crew. Crew planning is vital because, after fuel costs, the cost of flight staffing has the largest share among operational costs. The purpose of this section is to allocate crews to all aircraft flights according to the existing restrictions on flight groups, including their working hours and rest time while considering the objective function of the minimization problem. It is the cost of human labor wages. Many efforts are being made to consider a model that includes all four issues, which is expected to optimize the flight schedule to save resources and increase the companies' income [3].
The main goal of this research is to present a mathematical model for the decision regarding the establishment of flight routes between the cities of a country to minimize the total cost. Due to the non-linearity of the proposed model, a solution method based on the meta-heuristic algorithm of particle swarm optimization is also provided and simulated in MATLAB, the details of which are given in the following sections. This article is organized into five sections. The first part contains the introduction and definition of the problem, the second part is devoted to reviewing previous works, and the third is dedicated to presenting the proposed mathematical model. The simulation results of the model are given in the fourth section. The fifth section deals with the general conclusion of the research.
2. Previous Work
Several studies have been conducted in crew planning, and various methods have been presented to solve this problem, which are reviewed in this section.
Saeidi and Shahedi (2019) used the grey wolf algorithm to solve the crew scheduling problem of Ata Airlines [4]. Khanmirza et al. (2017) designed the flight problem and fleet allocation using a Genetic Algorithm (GA) [5]. Shafahi and Jalayer (2010) used a Simulated Annealing (SA) algorithm for flight rescheduling [6]. In their research, Teodorovich and Gubrink (1984) have considered a particular case in which one or more planes are removed from the fleet due to a technical defect, and the airlines are forced to make the rest of the flights with the remaining planes [7]. In this case, the initial schedule is disrupted due to the decrease in the number of available planes, and the rest of the flights are delayed. The purpose of this research was to reduce the delay of passengers in the air network. Teodorovic and Stojkovic (1990) presented a model with two objective functions for maximizing the number of flights and minimizing the delay of passengers, in which the flight's deletion, change, and delay are considered to solve the flight rescheduling problem. To solve the model, the researchers proposed a dynamic programming-based multi-threaded algorithm [8].
Klincewicz and Rosenwein (1995) investigated the feasibility of changes in the initial planning and given flight allocation using a network flow model. The changes considered in this model include adding, removing, or changing the type of aircraft assigned to each flight. Similar to the previous models, the required input information includes the initial flight plan, fleet allocation, and various troubleshooting methods [9]. Jarrah et al. (1993) presented a model for flight rescheduling to minimize the total cost caused by the lack of aircraft. In this research, two separate models have been used for flight: the delay model and the elimination model [10]. In their research, Yan and Yang (1996) assumed that the failure of only one plane caused the disruption, but they tried to consider the options of delaying, removing, and moving the plane to solve the existing disruption. They used the network flow method and Lagrange relaxation to solve the model [11].
Lettovsky et al. (1998) performed crew planning and flight and fleet allocation simultaneously after disruption. They proposed a mixed integer linear programming model, and its calculation results cannot be achieved except in small-size examples in a short time. Therefore, these researchers used an analysis method to solve the problem [12]. Arguello et al. (1997) investigated the flight rescheduling problem after a disruption caused by a delay or the temporary grounding of the plane [13]. Kim et al. (2017) solved the crew scheduling problem to minimize the total cost. Their method was based on the review of previous works in this field [14]. In their article, Kasirzadeh et al. (2017) presented a comprehensive model to define the crew scheduling problem and examined the available solutions [15]. Joung (2017), in his master's dissertation, solved the railway track crew scheduling problem by using the concepts of set coverage and shortest path with limited resources and solved it by branch and cost method [16]. Koch (2021) in his M.Sc. dissertation proposed a multi-objective model for the U.S. Air Force crew scheduling problem and analyzed the results based on numerous metrics [17]. Saemi et al. (2022) presented a model with two objective functions to solve the crew scheduling problem and developed a method based on Ant Colony Optimization (ACO) [18]. Zhao et al. (2022) presented a new mathematical formulation for the crew scheduling problem considering the real-world constraints in China and solved it using the GA method.
A brief study of the literature on the subject shows that most of the previous research has been carried out assuming the existence of a flight path between two or more cities to optimize the desired objective functions. The main contribution of this research is determining whether a flight route between two assumed cities should be established or not, to reduce the total costs of setting up and servicing air travel by choosing the best active routes, allocating suitable planes for each route, and determining their number. In this paper, the flight schedule (including the time of preparation of the landed aircraft for the subsequent request), the demand of each flight, and the characteristics of the fleet ready for operation (capacity and operation cost) are assumed to be known. The restrictions related to the crew schedule and aircraft repairs are not considered. Besides, the planning period is assumed to be repeated for days.
3. The Proposed Method
In this section, the definition and method of mathematical modeling of the problem and method of mapping the proposed model to the PSO algorithm are discussed.
3.1. The Mathematical Model
To optimize the airline routing problem, the air transportation system should be examined first, and the variables of the problem should be well defined. In this research, airlines are considered as an inter-airport network, and if there is a flight between two airports, there is a connection between two corresponding nodes. The airport network structure is considered a graph, where each node represents an airport. Economic justification of flights is an important issue that should be considered before crew planning. In other words, it should be determined whether establishing a flight line between two specific airports (cities) is economical or not, considering the number of passengers applying, the air fleet's structure, and the airline company's policy. So, the first research question is: Should a flight route be established between given two cities? This concept has been implemented using a binary decision variable in the proposed model.
3.1.1. Parameters and Assumptions
: Binary decision variable, should the air route be established between city i and j or not?
: Integerthe decision variable, the number of aircraft of type k that is used on the route i to j.
: The number of passengers requesting to travel from city i to city j.
: Travel distance from city i to city j.
: Cost per kilometer of travel from city i to city j.
: Capacity of type k aircraft.
L: The minimum distance required to establish a flight between two cities.
P: The minimum number of passengers required to establish a flight between two cities.
N: Number of cities.
M: A very big number.
: Number of available planes of type k.
3.1.2. The Objective Functions and Constraints
The proposed linear programming model is defined by relations (1) to (6). Due to the presence of product statements of decision variables in the objective function and constraints, the proposed model is non-linear.
Equation (1) is the model's objective function and is defined to minimize the total travel costs. This relation has been used as the fitness function in the PWO meta-heuristic algorithm. The relation (2) guarantees that the number of flights in airlines must have sufficient capacity to transport passengers because if the number of passengers exceeds the transportation capacity, the airline system cannot provide proper services to passengers. Based on equation (3), it is guaranteed that the flight will be carried out in distances with a length greater than a minimum required value; for the cities whose distance is less than L, a flight path will not be created. The relation (4) guarantees that the number of passengers between two cities is more than a minimum value so that a flight between two cities can be created because, in addition to the distance limitation, the creation of a flight must also be economical in terms of the number of passengers. Constraints (5) and (6) also specify the type of decision variables.
3.2. The Proposed PSO Algorithm
The PSO algorithm is similar to other population-based algorithms, such as the genetic algorithm, which is based on the social behavior of particles. However, there is no direct recombination of the individuals in the population. In each generation, each particle adjusts its path based on its best position (local best) and the position of the best particle in the entire population (global best). This concept enhances the stochastic nature of the particle and fast convergence to a global minimum with a reasonably good solution.
To use this algorithm, it is necessary to map the model to the concepts of the PSO algorithm. First, the components of this algorithm should be defined. Each particle consists of a square matrix of zero and one in two-dimensional space, which indicates the existence of a route between cities. If the value of the entry is one, it means there is a route between two cities located at the intersection of the row and column, and if zero, there is no route between the two cities. Table (1) is an example of a particle that shows the sum of the numbers located in the ith row and column, the number of flights (round trip) from city i. For example, the total number of round-trip flights to Yazd will be six.
In the particle swarm algorithm, the particles' initial speed is assigned, and the communication channels between the particles are considered. Then, these particles move in the solution space, and the results are calculated based on fitness, and the particles accelerate towards more worthy particles. So, the best particle is determined by its position in the population and speed. In the implementation of the method, the following relations are used.
Table 1. The structure of a particle
Ardabil | Gorgan | Zahedan | Yazd | Ahwaz | Shiraz | Esfahan | Kish | Gheshm | Tabriz | Cities | |
1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | Tabriz | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | Gheshm | |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | Kish | |
1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | Esfahan | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | Shiraz | |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | Ahwaz | |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | Yazd | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | Zahedan | |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | Gorgan | |
0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | Ardabil | |
Where 
and 
represent the speed and position of the 
particle at the 
moment (repetition), respectively. The right side of this equation consists of three parts: the first part is the current speed of the particle and the second and third parts are the change of the speed of the particle and its rotation towards the best personal experience (
) and the best group experience (
). The rand() function generates a random number in the interval [0,1]; 
and 
are called effect constants, which respectively show the importance of the best condition of each particle and the importance of the best condition of the neighbors. The parameter w also represents the inertia of the movement and, it is the coefficient of the particle's previous speed, which determines how much the previous speed of the particle is involved in the calculation of the current speed of the particle, and its value is always a number less than one.
If the number of swarm populations is N and each particle randomly has position 
, the fitness function 
at the current position xi is evaluated for each particle. If is greater than 
, then will be updated. If is greater than 
, the 
will be updated. Particle movement depends on individual movement and group movement. Combining these movements leads to an efficient model to find the best target point in optimization problems. If the particles only pay attention to individual movement, soon their group will break up, and each one will move in a different direction.
Moreover, if they move toward the best member of the group, they may lose their way or arrive late. The particle swarm algorithm is affected by two cognitive and social components, i.e., the position of a particle in one stage, a component of the previous position, the best position of the individual that the particle has experienced so far, and the best position of the entire community of particles which has been experienced so far.
Updating the position of particles also depends on the amount of cost (fitness function) of that particle. In each iteration of the algorithm, the cost of particle x in the new position is compared with its cost in its previous best position. If the cost of the current position of the particle is lower than its value in its previous best position, the current position of the particle and its cost replace the cost and the best previous position of that particle.
4. Simulation and computational results
In this section, the efficiency of the proposed method has been evaluated. For this purpose, the proposed method is coded in MATLAB and some problems in small dimensions (10 cities), medium (25 cities), and large (50 cities) are simulated until the time of sufficient convergence (no change in the value of the objective function in the last 60 iterations). Figure (1) shows the convergence diagram of the objective function of a large-size sample problem. In this Figure, the vertical axis represents the value of the objective function (cost in millions of Rials), and the horizontal axis represents the repetition number in the program execution.
Figure. 1. The Convergence Diagram of the Objective Function for 50 Cities
Cost (Objective Function) |
|
Figure 2. The stability diagram of the proposed method in ten consecutive runs
As shown in Figure (1), the proposed method reached convergence in the 30th iteration, and the value of the objective function remained constant. To evaluate the stability of the proposed method, the same problem was solved ten times, and the final solution was recorded. Figure (2) shows the values obtained from implementing the proposed method in 10 different implementations; considering the slight difference in the resulting solutions, it can be concluded that the proposed method has high stability.
5. Conclusions
In this paper, a linear programming model was presented to minimize the total cost of travel in the airline route. Unlike the previous methods that assumed the flight routes between the cities to be predefined and known, the proposed method first specifies which flight routes should be created between which cities, then determines the type and required number of aircraft to be used to serve the passengers of that route. The objective function of the proposed model is to minimize the total travel costs. Considering the nonlinearity of the model, a solution method based on a meta-heuristic particle swarm algorithm was presented to solve the proposed model, and it was coded in MATLAB on a personal computer. The assumed limitations force the model as follows: the air transportation system must have sufficient capacity to carry passengers, the number of passengers and the air distance between the two cities should be more than a minimum standard. In this case, it will be economical to create a flight. To test the proposed method, the problem was examined in small, medium, and large dimensions; the simulation results revealed that the dispersion and variance in the number of different iterations were minimal. Therefore, the proposed method has high stability. The future study suggestions are mentioned as the following:
• Considering several objective functions such as service quality and passenger convenience
• Using other evolutionary approaches to solve the model
• Considering more restrictions and similarities to the real world
References
[1] Valdes, V., Andres, V. (2010). “Integrating Crew Scheduling and Rostering Problems”, Ph.D. thesis, Universitá Di Bologna.
[2] Ozdemir, U. (2009). “Methodology for Crew-Pairing Problem in Airline Crew Scheduling”, Ph.D. thesis, Boğaziçi University.
[3] Naseralavi, S., Saffarzadeh, M. (2009). “Flight planning using search optimization methods”. Journal of Transportation, 2(6). In Persian.
[4] Saeidi, S., Shahedi, P. (2019). “Solving the crew scheduling problem of Ata airline using the Grey Wolf optimization algorithm”. 12th International Conference of Operation Research, Babolsar, Iran, In Persian.
[5] Khanmirza, E., Haghbeigi M, Nazarahari M. (2017). “Schedule Design and Fleet Assignment Based on Modified Intelligent Algorithms”. Modares Mechanical Engineering, 17 (6):59-66.
[6] Shafahi, Y., Jalayer, M. (2010). “Rescheduling the flight after the disruption, taking into account the crew's scheduling limitations”. 5th National Civil Engineering Congress, Ferdowsi University of Mashhad, In Persian.
[7] Teodorovic D. and Guberinic S. (1984). “Optimal dispatching strategy on an airline network after a schedule perturbation", European Journal of Operational Research, 15,178-182.
[8] Teodorovic D. and Stojkovic G. (1990). “Model for operational daily airline scheduling”, Transportation Planning and Technology, 14,273-285.
[9] Klincewicz J. and Rosenwein M. (1995). “The airline exception scheduling problem”, Transportation Science, 29, 4-16.
[10] Jarrah A., Krishnamurthy N., and Rakshi A. (1993). “A decision support framework for airline flight cancellations and delays”, Transportation Science, 27,266-280.
[11] Yan S., Yang, D. (1996).” A decision support framework for handling scheduling perturbations”. Transportation Research Board. 30,405-419.
[12] Lettovsky L., Johnson E., Nemhauuser G. (1998). “Airline Crew Recovery”. The Logistics Institute, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta.
[13] Arguello M. Bard F and Yu G. (1997).” A grasp for aircraft routing in response to groundings and delays”. Journal of combinational optimization, 5, 211-228.
[14] Kim, J., Jung, S., Lee, S. (2017). “Revisiting on the Problems of Crew Scheduling”, International Journal of Transportation, 5(2), 55-64.
[15] Kasirzadeh, A., Saddoune, M., Soumis, F. (2017). “Airline crew scheduling: models, algorithms, and data sets”, Eero Journal on Transportation and Logistics, 6(2), 111-137.
[16] Joung, H. (2017). Solving the Train Scheduling Problem, M.Sc. Dissertation, Department of Mathematics, Faculty of Science, Radboud University.
[17] Koch, M.J. (2021)." Air Force Crew Scheduling: An Integer Optimization Approach”. M.Sc. Dissertation in Operations Research, Sloan School of Management, Massachusetts Institute of Technology.
[18] Saemi, S., Komijan, A., TavakkoliMogaddam, R., Fallah, M. (2022). “An Integrated Crew Scheduling Problem Considering a Reserve Crew in Air Transportation: Ant Colony Optimization Algorithm”, Journal of Optimization in Industrial Engineering, 15(2), 167-177.
[19] Zhao, C.; Chen, J.; Zhang, X.; Cui, Z. (2022). “Solution of Multi-Crew Depots Railway Crew Scheduling Problems: The Chinese High-Speed Railway Case”. Sustainability, 14, 491. https://doi.org/10.3390/su14010491
