Abstract
Сontent
- Introduction
- 1. Actuality of the theme
- 2. Purpose and Objectives
- 3. Formulation of the Problem
- 4. Structure of the System
- Conclusion
- References
Introduction
The airline industry is a fast–growing branch of industry. Airlines are required solving many problems to be competitive, to provide customers with better service. Emerging problems are very complex, some still cannot be solved in its entirety and solved in stages: the main constraint is the lack of computing power. The number of parameters and constraints that need to be taken into view when solving problems in the airline industry is reaching tens. That leads to difficulties in the development of the system.
1. Actuality of the theme
More and more companies in sphere of trade require services of transport of goods. Competing company with minimal transportation costs wins. The urgency of this problem is confirmed by the fact that experts estimate up to 50% of all costs associated with trade in transport costs [1]. The speed and distance of the airline industry has no competitors in the transportation of cargo. In order to increase their profits in the current situation, the airlines want to reduce costs for their services due to the rational use of its own resources and the organization of production.
2. Purpose and Objectives
The purpose of the master's work is to minimize transport costs by finding the best routes and the rational distribution of traffic between the aircrafts.
The main objectives:
- choosing the structure of the system;
- development of the mathematical model of schedule–creation process for cargo air–transporting;
- analyze the parameters of schedule–forming process for cargo air–transporting;
- implementation of the schedule–forming process for cargo air–transporting.
3. Formulation of the Problem
Every airline has a specific list of slots
on which it can realize flights. This fact limited by legislation. There are summer and winter half–periods. For each half–period the schedule is formed one month before [2]. For a schedule–building task that fact is a constraint on the direction of time and of aircraft’s departure. This constraint can be overcome by the flight on behalf of other airlines.
The airline provides cargo transportation services to all points of the globe where there are facilities for landing of their aircraft. More often to perform a specific order of cargo transporting the plane performs a sequence of flights, which is called "chain of flights". Sometimes these chain are performed by different planes, which increases the cost of cargo shipping due to payments for moving cargo between the aircrafts. A secondary problem to be solved is the minimization of the cost of human resources. This problem can be solved by making the entire chain of one airliner in flight.
Any cargo has its own value for the airline and volume. The airline is responsible for the transportation of cargo without the physical and chemical changes.[3]
The capabilities of each aircraft are limited by flight and cargo characteristics. The flight characteristics include: range, fuel consumption, the size of the tank, the price of operation. The cargo characteristics include: limits on the amount of cargo tonnage aircraft.
When creating a schedule air cargo transportation is necessary to consider all the above factors. Because of the many parameters that affect the scheduling of aircraft follows the task of automating this process, the solution of which will reduce labor costs, fuel costs, operating aircraft, the cost of loading.
4. Structure of the System
The mathematical model of the system can be divided into two related subsystems:
- load distribution between aircraft;
- chaining flights.
These subsystems are closely linked, in order to achieve this goal should be considered this relationship. Subtask of cargo distribution depends on the route, but rather a list of the cities which an aircraft will pass through. The opposite is true – aircraft routes depend on contracts for the transportation of cargo, ie aircraft must pass only the cities where cargo was expected to be transported either one of the destinations is this city. Priority will be given to those cities that have made just two of these conditions.
4.1 Sub–Tasks Overview The Cargo Distribution on the Aircrafts
Each airport has a cargo awaiting shipment. The amount of cargo, the weight, the size specified in the delivery note the shipping. Other than delivery note include the price of transportation, which is calculated in the shipping and receiving centers and depends on the type of cargo. Each is characterized by the capacity of aircraft and flight characteristics that determine the possible direct flights and fuel consumption.
Need to carry the goods to the specified destination for the given values required transportation of cargo (weight and price expended) by assigning it a specific type of aircraft , getting the best return on transportation.
The solution to this problem will allow efficient use of air resources, which, in turn, minimizes the cost of fuel and maintenance of aircraft.An example of which is placed in the most popular cargo aircraft can be seen in Figure 1.
Figure 1 – scheme which is placed cargo McDonnell Douglas MD–11
4.1.1 Mathematical model of the sub–task The Cargo Distribution on the Aircrafts
To solve the requested task, we need such data [4]:
А – Set of airports (index a);
L – the set of all flights (index l);
P – the set of all classes of goods (index p);
F – set of types of aircraft (index f);
T– set of times of departure and arrival flight schedule (index t);
CL(f) – Set of flights crossing the zero line
I(f,a,t) – set of arriving flights at the airport and at time t on the aircraft type f;
O(f,a,t) – set of flights departing from the airport and at time t on the aircraft type f;
The task parameters are:
– Income from delivery notes of cargo class p ∈ P
– the number of available aircraft type
– capacity of aircraft assigned to flight f ∈ F
– зthe cost of flying on flight i ∈ L сaircraft type f∈F
product demand p∈P
Unknowns to the task want to search:
– the number of aircraft types f∈ F airport immediately after the time t∈T
– the number of aircrafts of type Airport, a&isinA immediately before time t &isinT f&isin
– the weight of all cargo, a separate class of p∈P.
Target function:
The first term is the income from the carriage of cargo, ie the amount received for the transportation of play money. The second term of the objective function represents the total cost of all aircraft flights scheduled for this flight schedules.
Need to find 
,
in which target function is maximized subject to the restrictions:
Conditions for covering:
,wherein ∈i ∈L
Each flight must be assigned to only one the plane of one of the available types.
The condition of balance:
The number of aircraft in the airport directly to the time t, and landed at this point, is the number of aircraft that can take off from the airport after a time t, plus the aircraft that it will remain.
You cannot use more than you have:
(5)
For each type of aircraft side at the airport, but the initial moment, and counting the number of crossing the line shall not exceed the amount of this type of aircraft in the airline's fleet.
The condition of the limited capacity:
For any flight weight of all cargo, class p, which is assigned to the the plane type f, can not be greater than the capacity aircraft.
Additional restrictions:
To solve the optimization problem, you can use the following methods [5]:
- full search;
- branch and bound method;
- a method of dynamic programming;
- Genetic Algorithm.
4.2 Overview Sub–Task Chaining Flights
Task: Each flight can carry out a specific aircraft type or several types, depending on the flight characteristics of the aircraft and distance. Necessary to determine the board which will be performed a certain chain. this problem is very popular. Example of solving this probem you can see on Figure 2.
Figure 2 – Traveling salesman problem for the regional centers of Ukraine(animation: 11 frames, 5 cycles of repeating, 64 kB)
4.2.1 Mathematical Model of the Sub–Tasks Chaining Flights
The model uses the following variables and sets[6]:
– the number of available aircraft type f
– the cost of flying on flight i, aircraft type f,
income derived from the use aircraft f,on the flight i,
K – set of types of aircraft fleet, the index f.
Need to find a solution x,f,I (vector distribution for aircraft by the flights), in which a linear target function under the conditions and limitations will be maximized.
Constraints:
The condition partitioning – in the final set of chains
every flight, can be present in one and only one chain
:
where
L : set of flights with index i∈L.
Terms of fleet capacity – the number of chains
that are assigned to aircraft of this type should not exceed the number of available aircraft of this type:
where
current number of aircraft of type 
Balance condition – for any type of aircraft and any airport 
number of chains
, starting at a given airport must be equal to the number of chains terminating in it, provided that these chains designated the plane of type:
where
IS (f, a): a set of chains
of flights terminating at the airport in a ∈ A, which are assigned the plane type f ∈ F.
OS (f, a): The set of strings of flights at the airport starting a ∈ A, which are assigned the plane type f ∈ F.
This problem is a classic traveling salesman problem with additional constraints and can be solved using a modified genetic algorithm.[7]
Conclusion
As a result, developed a mathematical model consisting of a criterion function and constraints on the main parameters. In the future it is planned to research the characteristics and development of algorithms for solving the problem.
At the moment master's work is not complete yet. Final completion date: December 2013. The full text of the work and its materials can be obtained from the author or his scientific adviser after that date.
References
- Виноградов Л.В., Шебалов С.М. , Математическое моделирование в оптимизации планирования авиационных перевозок: формулы и методы расчетов типовых задач/
- Технология формирования сезонного расписания регулярных и стыковочных авиарейсов ИАТА [Электронный ресурс]. — Режим доступа: http://www.fly-jet.biz/tech.php.
- Федосин С.А., Есин Ю.Д. Прогнозирование спроса на рынок авиаперевозок, ГОУВПО Мордовский государственный университет им. Н. П. Огарева, г. Саранск.
- Зернова Н.А., Носова Е.В. , Фридман Г.М. Оперативная расстановка парка воздушных судов по рейсам, связанная с изменениями данных по спросу // Экономическая кибернетика: Сб. науч. тр. 2009. Вып. 19. с. 164–168.
- Задача о рюкзаке[Электронный ресурс]. — Режим доступа: http://ru.wikipedia.org/....
- Зернова Н.А, Фридман Г. М., Цепочки рейсов : определение, условий и алгоритмов построения
- Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки[Электронный ресурс]. — Режим доступа: http://econference.ru/.../.