Title Problemi rasporeda u zračnom prometu Title (english) Schedule problems in air traffic Author Ivona Raguž Mentor Marko Vrdoljak (mentor)Committee member Marko Vrdoljak (predsjednik povjerenstva)Committee member Marcela Hanzer (član povjerenstva)Committee member Goran Radunović (član povjerenstva)Committee member Zoran Vondraček (član povjerenstva)Granter University of Zagreb Defense date and country 2020-09-29, Croatia Scientific / art field, NATURAL SCIENCES Abstract Problemi rasporeda u zračnom prometu primjer su složenijeg tipa rasporeda koji u obzir uzima brojna ograničenja i regulative postavljene od strane zrakoplovne indrustrije. U ovom radu naglasak je stavljen na problemu izrade rotacija posade – niz dužnosti s odmorima izmedu koje pokrivaju letove tako da posada počinje i završava putovanje u istoj bazi. Taj problem matematički opisujemo optimizacijskim problemom, i to problemom cjelobrojnog linearnog programiranja. Cilj je pronaći optimalan skup rotacija uz minimalan trošak tako da svaki od letova bude obuhvaćen točno jedanput. Navodimo standardnu formulaciju problema izrade rotacija te predlažemo metode za njihovo rješavanje. Linearna zadaća kojom opisujemo problem izrade rotacija posade obično ima veliki broj uvjeta. Broj uvjeta smanjujemo primjenom Dantzig-Wolfeovom dekompozicije zadaće. Dantzig-Wolfeove dekompozicija zasniva se na teoremu reprezentacije poliedarskog skupa. Poliedarski skup prikazujemo preko njegovih ekstremnih točaka i ekstremnih zraka, čime broj varijabli obično postane vrlo velik. Rješavanje zadaće linearnog programiranja s velikim brojem varijabli je složenije, pa se javlja potreba za efikasnom metodom. Metoda generacije stupaca primjenjuje se na reduciranoj zadaći s manjim podskupom stupaca. U svakoj iteraciji traži nebazičnu varijablu koja će ući u bazu i optimirati funkciju cilja reducirane zadaće. Odluku o generaciji novog stupca dobijemo rješavajući pomoćni problem odredivanja cijena. U slučaju blok-dijagonalne strukture matrice uvjeta, formulacija zadaće linearnog programiranja u obliku Dantzig-Wolfeove dekompozicije u kombinaciji s generacijom stupaca može biti primjenjiva na paralelno rješavanje potproblema umjesto na rješavanje originalnog problema. Iza teorije metode generacije stupaca stoji teorija dualnosti. Još jedan pristup rješavanju problema je Lagrangeova relaksacija. To je pristup koji omogućuje ”preoblikovanje” modela uklanjanjem ”kompliciranih” uvjeta te njihovim prebacivanjem u funkciju cilja, uz pridruživanje Lagrangeova multiplikatora. Razradom teorije Lagrangeove relaksacije dolazi se do zaključka da je za bilo koju vrijednost Lagrangeovog multiplikatora optimalna vrijednost relaksirane zadaće donja ograda na optimalnu vrijednost funkcije cilja izvorne zadaće. Cilj je pronaći najbolju moguću ocjenu odozdo, tj. pronaći što ”kvalitetniji” multiplikator za koji je optimalna vrijednost Lagrangeove relaksirane zadaće što veća moguća – rješavamo Lagrangeovu dualnu zadaću. U nastavku razmatramo konveksifikaciju Lagrangeova duala, što nam omogućuje primjenu Dantzig- Wolfeove dekompozicije, tj. zapis konveksne ljuske skupa preko njegovih ekstremnih točaka i ekstremnih zraka. Opisan je pristup rješavanju zadaće cjelobrojnog linearnog programiranja generacijom stupaca. U konačnici, kako popisivanje rotacija iz prve, tradicionalne formulacije problema može biti vrlo zahtjevno, ponudili smo drugačiju formulaciju problema rotacija posade. Prednost nove formulacije problema je što njegova linearna relaksacija daje ”bolju” ogradu na optimalnu vrijednost funkcije cilja izvorne zadaće u odnosu na linearnu relaksaciju zadaće u skladu s tradicionalnom formulacijom.
Abstract (english) Airline scheduling problems are an example of a more complex type of scheduling that takes into account a lot of restrictions and regulations posted by airline companies. In this paper, the accent is on solving the crew pairing problem – grouping series of duties with breaks which cover flights in the way that crew begins and ends the journey at the same base. Mathematically saying, we describe this problem by optimization problem, or to be more precisely, by the problem of integer linear programming. The goal is finding optimal pairings with minimal cost to cover each flight exactly once. We give a standard formulation of the problem and suggest methods for its solving. The linear problem which is used to describe the crew pairing problem usually has a lot of conditions. We reduce the number of conditions by applying Dantzig–Wolfe decomposition on the problem. Dantzig–Wolfe decomposition is based on representation theorem of polyhedron. We represent polyhedron in terms of its extreme points and extreme rays, which usually makes the number of variables very large. Solving a linear problem with large number of variables is more complex, so there is a need for an effcient method for solving it. The column generation method is applied on a restricted master problem with a small subset of columns. In each iteration, it looks for a non-basic variable to enter the base and optimize the objective function. We get a decision to generate a new column by solving pricing subproblem. If condition matrix has a block–diagonal structure, the formulation of the linear programming problem in terms of Dantzig–Wolfe decomposition in a combination with column generation can be applied to the parallel subproblem solving instead of solving the original problem. There is the theory of duality behind the theory of the column generation. Another approach to problem solving is Lagrange relaxation. It is the approach that enables reshaping the model by removing complicated conditions and putting them to the objective function with addition of a Lagrangian multiplier. Elaboration of the theory of Lagrange relaxation leads to the conclusion that for any value of the Lagrange multiplier the optimal value of the relaxed problem is the lower bound for the optimal value of the objective function of the original problem. The goal is to find the best possible lower bound, i.e. to find the multiplier of the highest quality for which the optimal value of Lagrangian relaxed problem is as large as possible – we solve Lagrangian dual problem. Further, we consider the convexification of the Lagrangian dual, which allows us to apply the Dantzig-Wolfe decomposition, i.e., set formulation in terms of its extreme points and extreme rays. There is a description of an approach for solving the problem of integer linear programming by column generation. Finally, since the enumeration of pairings from the first, traditional formulation of the problem can be very demanding, we offer a different formulation of the crew pairing problem. The advantage of the new problem formulations is that its linear relaxation provides stronger bound on the optimal value of objective function of the original problem compared to the linear relaxation of the problem according to the traditional formulation.
Keywords
zrakoplovna indrustrija
rotacija posade
optimizacijski problem
Dantzig-Wolfeova dekompozicija
Lagrangeova relaksacija
Keywords (english)
airline companies
the crew pairing problem
Dantzig–Wolfe decomposition
Lagrange relaxation
Language croatian URN:NBN urn:nbn:hr:217:198189 Study programme Title: Computer Science and Mathematics Type of resource Text File origin Born digital Access conditions Open access Terms of use Created on 2021-03-04 13:09:35
