Beta 1


Title Indføring af "Pedestrain Scramble" i lyskrydskaoskryds
Author Larsen, Jesper
Supervisor Hels, Tove (Trafiksikkerhed, Institut for Transport, Danmarks Tekniske Universitet, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2008
Abstract The purpose of this thesis is to investigate how various optimization methods from Operations Research can be applied to a Business Jet Airline Rostering Problem (BJARP). Business Jet Airlines are sometimes also referred to as Fractional Jets. Customers buy a share of an airplane, contrary to regular commercial airlines, where they buy a ticket for a certain pre-scheduled flight. Fractional shareholders (customers) can request customized flight(s) on a short notice. The BJARP deals with the scheduling of pilots for expected demand over a planning period, while satisfying various rules and regulations. Methods guaranteeing optimal solutions are studied and developed in order to achieve insight into the problem. The problem is modeled as a Binary Integer Problem and as a Multi-Commodity Network Flow Problem. Both models provide optimal results for very small problem sizes within a short time. Even for medium-sized problems and definitely for any problem sizes derived from real- life problems, the models cannot be solved. We demonstrate how the problem sizes grow drastically. Methods which do not guaranteeing optimal solutions are applied. A Simulated Annealing heuristic is implemented. This provides quick and fairly good solutions to problems of all sizes. The heuristic is not stable; the quality of each solution can vary greatly. To counteract this, a Matheuristic method inspired partly by Column Generation is applied. Instead of a ”usual” Sub Problem, the Simulated Annealing is used when needed to generate new columns to be added to the master problem. Due to formulation, columns are greatly intertwined - choosing one column can easily rule out choosing many other columns and vice versa. The consequence hereof is that the master problem is only solvable to a certain problem size. A Column Management Scheme is utilized in order to iii keep the size of the column pool under a certain limit. In effect this enables solving real-life problem sizes. Finally the performance of the Simulated Annealing and the Matheuristic is compared. We show that even though the Matheuristic ”builds” on Simulated Annealing, this solution approach is a great improvement with regards to solution quality. When compared on stability issues, the Matheuristic outperforms the Simulated Annealing. The conclusion drawn from this project is that the use of a Matheuristic approach makes it possible to solve real-life problem sizes with quite good solution results. In future work, improving on the Simulated Annealing embedded in the Matheuristic or exchanging it with another heuristic approach, would most likely render even better results. Keywords: business jet airline rostering problem; BJARP; business jet airline; fractional management; fractional ownership; mathematical modeling; mathematical programming; optimization; heuristic; matheuristic; hybrid heuristic; integer pro- gramming; column generation; multi-commodity network flow; crew scheduling; crew rostering; workforce scheduling
Admin Creation date: 2009-01-08    Update date: 2009-01-08    Source: dtu    ID: 233245    Original MXD