Reactive Algorithm for Gate Assignment Problem in Airport Operations
The study delves into the significant research area of gate assignment problems in airport management, presenting a new reactive algorithm developed based on genetic algorithms. The research explores various modeling approaches, objective formulations, and solution methods, emphasizing the challenges posed by the NP-hard nature of the problem. By utilizing heuristic and metaheuristic techniques, the study aims to optimize gate assignments considering factors such as passenger convenience, luggage handling efficiency, and adherence to schedules.
Uploaded on Mar 04, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A New Reactive Algorithm For Gate Assignment Problem In Airport Ground Operations Management M.M. Yenisey, T. zcan (Istanbul niv.) B. Ya mahan (Uluda niv.) A. Aktel (Turkish Inst. Of Man. Sci.) 1
Gate Assignment Problem is an important research area in airport management. Why? 2
The most common modelling approach is 0-1 Integer Linear Programming. We can see graph theory approaches as well. i.e. Flow network, clique partitioning And stochastic features are embedded into models in some studies. 3
The model can be formulated single or multi objective form. Generally, passenger walking distance/time, luggage/cargo load/unload time, no of assigned/unassigned gates, deviation from planned scedule are defined as objectives. 4
Solution approaches are B&B, Dynamic Programming, simplex method, Lagrangian relaxation The problem becomes NP-hard rapidly as the size increases. Hence, exact solution approaches can be unsufficient. 5
Heuristic and metaheuristic approaches are used. Tabu search, greedy algorithm, GA, SA, Bee Colony Optimization, and/or hybrid approaches made of different heuristics or metaheuristics 6
What we did? We developed a reactive algorithm based on GA. This algorithm is originally developed for the hybrid flowshop scheduling problem. We basically used the study of Ding et al (2005). 7
? (1) Min ?=1 Min ?=1 ?=1 ?i,m+1 ?=1 ? ? ?+1 ?=1 ?i,0wi,o ?+1?i,jwk,lyi,kyj,l+ ?=1 ? ? ?0,iw0,i+ ?=1 (2) s.t. ?+1?i,k= 1 (1 i n) (3) ?=1 yi,kyj,k( dj-ai)( di-aj) 0 (1 i, j n, k m+1) yi,k {1,0} (1 i n, 1 k m+1) (5) (4) 8
Proposed Genetic Algorithm 1. Generate the initial population ; 2. Evaluate the fitness values of the individuals in the population; 3. If the last flight is assigned, STOP; 4. While a new fligth come to the airport; 4.1. Select two mates from the population 4.2. Apply crossover on two mates to form two children 4.3. Apply mutation on each child 4.4. Determine the next generation 5. Go to Step 2; 9
Genetic Algorithm: Chromosome Structure A chromosome is composed of permutation of flights and permutation of gates. F5 F2 F1 F3 F4 G4 G3 G1 G2 G10 Random numbers between 0 and 1 is used to form a chromosome 0,35 0,63 0,18 0,42 0,83 0,76 0,39 0,51 0,36 A permutation is determined by sorting the double numbers in ascending 2 7 1 5 9 8 4 6 3 10
Genetik Algorithm: Solution Candidate A solution candidate is determined by assigning the flights to the gates G2 F2,F5,F4,F3,F1 G3 G1 A greedy method is used to assign the fligths to the gates 11
Genetic Algorithm: Solution Candidate Fligths are assigned to the gates according to the permutation order of flights and gates to minimize the difference of flight arrival time and the available time of a gate. Any fligth is assigned to an available gate with latest available time of the gates. If no gates available, the fligth is assignd to the apron. The basic steps are: 1- Sort flights according to the chormosome permutation and sort gates according to the chromosome ermutation. Let ai arrival time of flight i and gk represents available time of gate k. 2- For each flight i, find gate k such that gk < ai and ai - gk is minimized if such k exists, assign flight i to gate k, if k does not exist, assign flight i to the apron. 12
GA: Fitness Function Fitness= Transfer Passengers Total Walking Distance+ Embarking Passengers Total Walking Distance+ Disembarking Passengers Total Walking Distance 13
Parent Selection: Tournament Selection Selected solutions are compared according to the fitness values. 14
GA: Crossover and Mutation Crossover: A child genes are formed by taking the averages of parents genes. Mother Father Child Mutation: A random value (pm , mutation probability) is added to the child genes. 15
GA: Determining Next Generation Next generation is formed according to the fitness values of the parent and child solutions. Initial Pop Parents Selectio n Par1 Par2 Fitness based replacement Pool Childs 16
TABLE 1.TEST PROBLEMS Problem No 1 2 3 Number of flights 15 25 184 Number of gates 6 9 23 17
For the first problem, our algorithm finds the optimum. But the first problem is a small-sized one. TABLE 2.SOLUTION OF 15FLIGHT 6GATES PROBLEM Gate No. Apron 1 2 3 4 5 6 Flight No. 1, 11, 13, 14 6, 9, 12, 15 3, 7 5, 10 8 4 2 18
Our algorithm works well for the second problem and finds the optimum. TABLE 3.OPTIMUM ASSIGNMENT PLAN OF 25FLIGHTS 9GATES PROBLEM Gate No. 1 2 3 4 5 6 7 8 9 Flight No. 21, 22, 23, 24, 25 6, 7, 8, 9, 10 1, 2, 3, 4, 5 Unassigned Unassigned 16, 17, 18, 19, 20 11, 12, 13, 14, 15 Unassigned Unassigned 19
And finally, the third problem; our algorithm produces a good solution in reasonable time. Gate No Flights 1 16, 28, 56, 71, 89, 104, 117, 133, 146, 161, 172 2 18, 40, 70, 99, 123, 139, 153, 181 3 2, 31, 37, 63, 74, 82, 96, 144, 159, 173, 180 4 3, 39, 58, 75, 97, 158, 182 5 22, 38, 65, 87, 124, 143, 164 6 10, 32, 49, 72, 148, 165 7 19, 26, 42, 69, 93, 113, 130, 141 8 36, 57, 76, 94, 118, 134, 147, 162, 175 9 7, 73, 167 10 23, 50, 116, 131, 142, 169 11 1, 24, 126, 157, 171, 179 12 13, 46, 78, 91, 105, 121, 140, 154, 166, 177 13 8, 44, 62, 150, 163 14 21, 33, 52, 66, 79, 95, 108, 120, 132, 155, 176 15 4, 45, 60, 80, 98, 110, 137, 149, 170 16 11, 41, 61, 90, 125, 135 17 17, 27, 47, 59, 81, 107, 127, 136, 156, 168 18 14, 55, 83, 100, 115, 129, 160, 178, 184 19 9, 30, 54, 138, 152, 183 20 5, 48, 64, 88, 103, 114 21 15, 77, 109, 128, 145, 174 22 6, 20, 35, 53, 68, 92, 106 23 12, 34, 51, 67, 84, 119, 151 Apron 25, 29, 43, 85, 86, 101, 102, 111, 112, 122 20
Is our algorithm good enough? We compared against the Greedy Heuristic of Ding et al (2005). TABLE 5.THE COMPARISON OF PROPOSED ALGORITHM AND GREEDY HEURISTIC OF [9] (15,6) 196,490 (25,9) 87,800 (184,23) 1,967,415 GA based heuristic Greedy heuristic 216,490 110,260 1,985,830 21
Yes, our algorithm obtains better solutions. However, we should proceed and check against well-known solution approaches. 22
Thank you for your attention. Questions ??? 23
