Initial Proposal onAn Improved Algorithm for Airline SchedulingLeader NameMeherun Nesa Shraboni (1604016)Member’s NameFatema Tabassum Tania (1604009)Course TeacherMD. Sabir HossainLecturer,Dept. of Computer Science Engineering,Chittagong University of Engineering ; Technology, Bangladesh.
Individual contributionsGroup No Team Member’s ID Team Member’s Name Contributions in Word Contributions in %SPG- 03 1606016 Meherun Nesa Shraboni Write the introduction, find all related research paper, and write the related work, preliminaries, and references. 75% 1604009 Fatema Tabassum Tania Write the related work research paper. 25%An Improved Algorithm for Airline Scheduling1. Introduction:The airplane is the fastest travelling vehicle in the world and it is as well as expensive. Perfect airline scheduling can prevent cost of customer’s money and time. New algorithm are finding out to reduce passengers pain, cost, time. Ford-Fulkerson algorithm, minimum cost algorithm are used earlier to solve airline scheduling problem.
Ford-Fulkerson calculates the maximum flow. Our work is to research airline scheduling algorithm and creating an upgraded one. 2. Related work:Paper 01 (Dobson & Lederer, 1993) The paper is about airline scheduling and routing. Airline Company choose a way in which flight schedules and routine expenses maximum profit, considering competitor’s decisions. Authors try to found an airline which will have all benefits of these.
Implementation is very difficult and large. Hub-and-spoke system suggests that to solve real problem. Magnitude of the potential gain from better scheduling for a large airline and given the exponential increase in computing power that has occurred for several decades, the custom building of such a parallel machine is likely to be economically feasible.
Paper 02 (Reiners, Pahl, Maroszek, ; Rettig, 2012) Provide shortest connection time, maintain passenger’s time, maximum use of flight, preserve an airline schedule in such a way that the airplanes continue to be flight mode for a maximum period of time making use of max flow algorithm. Preserve an airline schedule in such a way that the airplanes continue to be flight mode for a maximum period of time making use of max flow algorithm.Paper 03 (Goldberg, A.
V, & Tarjan, R. E., n.d.) Dynamic trees, maximum-flow problem methods has been used. Here this paper’s contribution is improving an algorithm based upon the pre-flow idea. This algorithm runs so fast than any other known algorithm on dense graph. The block in the serial version of this system is not the saturating pushes.
Paper 04 (Ahmadbeygi, S., Cohn, A., ; Lapp, M., 2010) Linear Programming method has been used in this paper. Contributions are that planned timetable to denotes lost chances to use pricy fresh funds and sinking transmission deferment via dispensing existing loose in the planning process. Constraint of the journal is talking functioning fears in the planning process can be quite puzzling.
Paper 05(Etschmaier, M. M., ; Mathaisel, 1985) here no methods has been used. Here, only showing the development of airline scheduling methodology.
Contribution of this paper are to show airline planning made by procedures research experts through past twenty years and constituting an summary object. The constraint is no algorithm used here, only historical analysis and analysis of future work.Paper 06 (Kenan, N.
, Jebali, A., ; Diabat, A. , 2018)The Paper is based on an flow system of a train airline house showing the ideal of the stochastic problem with 100 situations is sufficient for taking the result of demand ; fare ambiguity and providing a answer with gap less than one percent within a very small computational period. For example average approximation algorithm is use for solving flow network problem .The key contributes are two stage stochastic programming model and this model provides solutions indicating. The limitations of the paper is failed to provide a model.Paper 07 (Barnhart, C., Boland, N.
L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L.
, ; Shenoi, R. G. , 1998)The paper is about a solo model and solution method to solve concurrently the flotilla assignment and airplane moving problems. A string build model and a branch-and-price key style are used.
A very insignificant number of sequences were produced matched to the total possible value. In half the problems less than thirty percent of the entire solution time was consumed producing threads are the difficulties.Paper 08 Rushmeier, R. A.
, ; Kontogiorgis, S. A. (1997).The methods are Mixed-integer multi-commodity flow network encoding activities linking flight departures. The assistances are the model is whole in its ability to capture the detailed linking and resource desires faced by large airlines and the model is strong, returning useful replies in the face of the variations typical of the plan design process and a full economic tradeoff is achieved through a unified dealing of resource restrictions by including penalties in the objective function. Failed to upturn the scope of the model.Paper 09 (Wu, C. L.
, 2006). The paper is about a consecutive optimization procedure is industrialized to improve the operative reliability of airline plans. A successive optimization algorithm is used. The donations are departure interruptions are reduced 30 percent. This serial optimization procedure has not however fully measured in the constraints air company.Paper 10 (Sato, N., Fujimasa, I., Imachi, K.
, Iwai, N., Miyake, H., Takido, N., Atsumi, K. ,1981) The paper is about to reduce delay propagation by intelligently routing aircraft and minimizing the number of passenger’s connections by rearranging the time.
Generate Delay Data Algorithm and the LP Relaxation of RAMR strategies are used. The contributions are minimizing the number of disrupted passengers and minimizes costs and expected propagated delay.3. Preliminaries:Our work is research and find easiest way for airline scheduling. Generally, The Ford-Fulkerson Algorithm calculates path distance of airline. Some scientist worked on an algorithm and their invented algorithm named after their name. In 1956, it was published.
In the Edmonds-Karp algorithm this algorithm was often used. This algorithm is a new form of Ford-Fulkerson algorithm. In a graph, if a path have available weight that is known as an augmenting path. We are going to work on this algorithm and research to improve this algorithm.4. References:1) Dobson, G.
, & Lederer, P. J. (1993). Airline Scheduling and Routing in a Hub-and-Spoke System. Transportation Science, 27(3), 281–297. https://doi.org/10.
1287/trsc.27.3.2812) Reiners, T.
, Pahl, J., Maroszek, M., & Rettig, C. (2012). Integrated aircraft scheduling problem: An auto-adapting algorithm to find robust aircraft assignments for large flight plans. In Proceedings of the Annual Hawaii International Conference on System Sciences.
3)Goldberg, A. V, & Tarjan, R. E. (n.d.). A New Approach to the Maximum-Flow Problem.
4) Ahmadbeygi, S., Cohn, A., & Lapp, M. (2010). Decreasing airline delay propagation by re-allocating scheduled slack. IIE Transactions (Institute of Industrial Engineers). https://doi.org/10.
1080/074081709034686055)Etschmaier, M. M., & Mathaisel, D. F. X.
(1985). Airline Scheduling: An Overview. Transportation Science, 19(2), 127–138. 6) Kenan, N., Jebali, A., & Diabat, A.
(2018). An integrated flight scheduling and fleet assignment problem under uncertainty. Computers and Operations Research, 100, 333–342. https://doi.org/10.1016/j.
cor.2017.08.0147) Barnhart, C.
, Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L.
, & Shenoi, R. G. (1998). Flight String Models for Aircraft Fleeting and Routing.
Transportation Science. https://doi.org/10.1287/trsc.32.3.2088) Rushmeier, R.
A., & Kontogiorgis, S. A.
(1997). Advances in the Optimization of Airline Fleet Assignment. Transportation Science, 31(2), 159–169. 9) Wu, C. L.
(2006). Improving airline network robustness and operational reliability by sequential optimisation algorithms. Networks and Spatial Economics. https://doi.org/10.1007/s11067-006-9282-y10) Sato, N.
, Fujimasa, I., Imachi, K., Iwai, N., Miyake, H., Takido, N.
, Atsumi, K. (1981). Hemodynamic effect of left atrium to aorta bypass (LA-AO LVB) in mechanical assistance of the failing heart (author’s transl). Respiration and Circulation. https://doi.org/10.1287/trsc.1050.0134
