Keywords: airport management, ground handling operations, CDM, multi-agent system

The increase of the world air traffic growth of the last decades has generated a permanent challenge for civil aviation authorities, airlines and airports to supply sufficient capacity to provide a safe transportation service with acceptable quality standards. New traffic management practices, such as A-CDM, based on multi-agent and collaborative decision making concepts have been introduced at airports. However, within the turnaround process of aircraft at airports, ground handling management of aircraft has not been developed specifically in the A-CDM approach, even if it has an important role in the fluidity of aircraft operations at airports.

The main objective of this thesis dissertation is to contribute to the organisation of the ground handling management at airports. It consists to provide a structure organize the ground handling management compatible with the A -CDM concept. The proposed structure introduces a ground handling coordinator (GHC) which is considered as an interface for communication between the partners of the A -CDM and the different ground handling managers (GHM). This hierarchical structure allows sharing information with partners in the A -CDM on the one side and on the other side, interacting with ground handling managers (GHM). Decision making processes based on heuristics have been developed at each level of the proposed organization and have been also evaluated in the case of nominal conditions and in the case of the presence of major disruptions.

Résumé

La croissance du trafic aérien a rendu critique l'opération de la gestion des plateformes aéroportuaires. Celle-ci fait appel à de nombreux acteurs (autorités aéroportuaires, compagnies aériennes, contrôle du trafic aérien, prestataires de services, …). Le concept d'Airport Collaborative Decision Making (A-CDM) développé depuis une dizaine d'années est basé sur un partage d'informations opérationnelles en temps réel entre les différents acteurs de la plate-forme, permettant de prendre des décisions en commun pour rechercher une utilisation optimale, en toutes conditions, des capacités de l'aéroport. L'objectif principal de cette thèse est de contribuer à l'organisation de la gestion des opérations d'escale dans une plateforme aéroportuaire. Il s'agit de proposer une structure d'organisation de cette opération qui soit compatible avec l'approche A-CDM. La structure proposée introduit un coordinateur des opérations d'escale (GHC) qui joue le rôle d'interface de communication entre les partenaires de l'A-CDM et les différents gestionnaires des opérations d'escale (GHM). Cette structure hiérarchique permet d'une part de partager des informations avec les partenaires de l'A-CDM et d'autre part d'interagir avec les gestionnaires des opérations d'escale (GHM).

Les processus de prise de décision basés sur des heuristiques ont été développés à chaque niveau de l'organisation proposée et sont évalués aussi bien dans le cas de conditions nominales que dans le cas de la présence de perturbations majeures.

GENERAL INTRODUCTION

Along the last decades of worldwide growth of air traffic, the air transportation system (ATS) has been developing new improved operational procedures based on the up to date available information processing technology. This started as early as 1962, with for example, the creation of the AGIFORS (Airlines Group of IFORS) by main airlines using the first mainframe computers available in that epoch. Today in the Internet era, the operations of the Air Transportation System involve directly global actors (airports, airlines, air traffic control (ATC), air traffic management (ATM)) as well as local actors (ground handlers, local suppliers…) through interconnected information networks.

The management of airports plays an important role within this complex system since demand for air transportation is airport referenced (they are at the same time origin and destination for the flights) and many effectiveness indexes are based on events occurring at the airport and the corresponding statistics. Besides safety and security which are a priority issues and they provide the operational environment at airports, aircraft traffic delays at airports and more particularly flight departure delays, are a also seen as permanent issues for airport management. Part from managing air traffic delays, safety and security, other main objectives of the traffic management at airports are the improvements of operational efficiency by reducing the aircraft delays, the optimization of airport resources to reduce costs and the increased predictability of effective flight departure times.

In fact, for many years now, flight delays are one of the most important problems in the air transportation sector. For instance, in 2007 19% of all European flights were late more than 15 minutes at departure [START_REF] Fricke | Delay impacts onto turnaround performance Optimal time buffering for minimizing delay propagation[END_REF]. These recurrent delays resulted in a lower quality of service to passengers while airlines and airports were also affected with a loss of efficiency and consequently with a loss of incomes and while the environmental performance of the ATS is downgraded (increases fuel consumption and emissions of particles). If delays resulting from bad weather are mostly unavoidable, delays resulting from insufficient performance of traffic management at airport may be reduced by searching for new operational approaches aims at improving the overall airport performance.

Airport Collaborative Decision Making (CDM) [Eurocontrol, 2013] is a recent concept which creates a common ground for the different components of the ATS. This concept is based on an improved communication between the different actors of the airport (Air Traffic Control, Airport Authorities, and Airlines). CDM has already been applied to some major European airports where it has improved their performances and has received a good acceptance by the different actors. However, within the turnaround process of aircraft at airports, ground handling management of aircraft has not been developed specifically in the CDM approach, even if it has an important role in the fluidity of the aircraft ground movements at airports.

The main objective of this PhD thesis is to contribute to the development of an efficient management organization of ground handling at airports which should be compatible with the CDM approach.

Ground handling addresses the many services required by a transportation aircraft while it is on the ground, parked at a terminal gate or a remote position in an airport, either at arrival from a last flight or at departure for a new flight. This includes the processing of boarding/de-boarding passengers, baggage and freight, as well as the aircraft itself (fuelling, cleaning, sanitation, etc).

This thesis is organized in six main chapters, conclusion and annexes.

In Chapter 1, the general ground handling process at the level of a particular flight is identified and described. Then each classical ground handling activity is detailed. Finally the time dimension of the ground handling attached to a particular flight is discussed.

In Chapter 2, the main managerial issues with respect to ground handling management at the airport are considered: ground handling management organization with the possible roles of the different stakeholders, ground handling costs and benefit issues and finally the different time scales adopted for ground handling management.

In Chapter 3, an overview of quantitative approaches to solve ground handling decision problems at the operations level is performed. Specific as well as global approaches making use of classical mathematical programming approaches or more recent computational approaches are considered.

In Chapter 4, a global organization of ground handling management at airports, including a ground handling coordinator and compatible with the CDM approach is developed, analyzed and discussed.

In Chapter 5, within the managerial framework proposed in the previous chapter, an heuristic based solution approach of the main operations problems encountered in ground handling at airports is proposed. Then a case study is developed.

In Chapter 6, also within the same managerial framework, the case of airport disruption is treated at the ground handling level.

Finally, the Conclusion Chapter provides a summary of the contributions of this work as well as the main perspectives for its application as well as subsequent developments in the same line.

The different annexes provide some theoretical and practical background with respect to the techniques used in this PhD report.

CHAPTER 1

2.

THE GROUND HANDLING PROCESS AT AIRPORTS 1.1. Introduction

This thesis focuses on the ground handling management at airports. From one airport to another, depending on their physical design, composition of traffic and many other factors, ground handling activities can appear to be performed very differently.

So, to clarify our field of study, in the first step of this chapter, the concept of ground handling adopted in this thesis is presented and discussed. It appears then that even if some traffic management related activities and airlines related crew and aircraft management issues are not included in this concept, the ground handling activities realized on a grounded aircraft would result in a very complex process.

Then, in the second step, in this chapter, a detailed description of the main ground handling activities performed on a transportation aircraft is proposed. These main activities cover: passenger de-boarding, passenger boarding, catering, cleaning, fuelling, push-back.

Finally the whole ground handling process performed on a grounded aircraft is considered through different examples of simulation while its time dimension is introduced and discussed.

Identification of ground handling

Aircraft ground handling is composed of a set of operations applied to an aircraft to make it ready for a new commercial flight or to finalize an arriving commercial flight. In general technical and commercial crew activities at arrival and departure are performed by the airlines and are not considered to be part of the ground processing activities. It is the same with the aircraft maintenance activities which are realized, in accordance with regulations, during the stopover of the aircraft, in parallel with the ground handling activities.

A typical ground handling process is composed of the following steps: De-boarding passengers, unloading baggage, fuelling, catering, cleaning, sanitation, potable water supply, boarding passengers, loading baggage, de-icing and pushing back the aircraft. Ground handling activities can be processed at different period of time and places in the airport.

Technical and commercial crew de-board the aircraft once all passengers have left the aircraft while other arrival ground handling activities can be performed. Depending of the turnaround characteristic (short turnaround) they may remain on board to perform the next flight. Otherwise, technical and commercial crew will board the aircraft before the start of departure ground handling activities.

At flight arrival, de-boarding passengers and unloading baggage must be performed as soon as safe conditions for it are established so that passengers suffer as little delay as possible. Then according to the tightness of the next departure schedule assigned to this aircraft and the need for free parking stands, the aircraft can be driven to a remote parking position. Unloading/loading of freight can be performed more or less quickly according to urgency and availability of unloading means at the arrival parking stand or at the remote position. Aircraft maintenance operations, which are in charge of the airline and which are not part of ground handling may take place, according to their nature, either at the parking stand or at a remote parking position.

Cleaning and sanitation must be performed without too much delay to get an aircraft as clean as possible. They can be done also either at the arrival/departing parking stand or at a remote parking position according to costless and delay free opportunities. It is also of interest to perform potable water supply once it is possible, so that if the aircraft is required out of schedule, only a minimum number of ground handling operations will remain to be performed.

When the scheduled departure time corresponding to the flight assigned to an aircraft approaches, the aircraft is driven if necessary to a departure parking stand. There the technical crew (pilot and co-pilot) and the commercial crew get on board the aircraft. In general fuelling is realized according to the airline demand at the departure parking stand. Luggage loading can start then until and during passenger boarding time. Once fuelling, luggage loading and passenger boarding are completed, the aircraft is ready to leave the parking stand and clearance is requested by the pilot to the ATC tower. Once clearance is granted by the ATC, push back is performed.

A major characteristic of airport ground handling is the divers involvement of activities, from equipment, vehicles and manpower skills. Another major characteristic of airport ground handling is the complexity of the whole process with parallel and sequential activities going on at parking stands, transportation links and ground handling vehicle bases.

Position of ground handling in airport system operations

Ground handling activities interact with aircraft traffic activities (taxiing and apron manoeuvres) and passenger/freight handling at terminals. Figure1.1provides a global view of ground handling within the turnaround process while Figure 1.2 illustrates in detail the position of the ground handling process within the airport system at the interface between passenger/freight processing and aircraft arrival/departure procedures. Figure 1.2 displays the sequencing of the main activities concerning with the passenger/freight on the left, the ground handling process as a generic module in the centre and on the right the main activities concerning with the aircraft arrivals and departures. Table1. 1: Scope of ground handling operations [START_REF] Ashford | Airport Operations[END_REF] The above representations (Figure 1.1, Figure 1.2 and Table 1;1) of the ground handling process put in evidence its critical role in the turnaround process at airports and subsequently in the capacity of airports to handle flows of aircraft and passengers.

Arrival traffic management activities

Ground handling activities

Detailed analysis of the main ground handling processes

Here the most current ground handling activities encountered at commercial airports are introduced and analysed by considering the corresponding equipment and fleets as well as the constraints applied to them.

The passenger boarding/de-boarding processes

At commercial airports, a boarding call on the public announcement system asks travellers to proceed to the exit gate and board the aircraft. "Boarding" here is the term to describe the entry of passengers into an aircraft. It starts with allowing the entrance of passengers into the aircraft and ends with the conclusion of the seating of all the passengers and closure of the doors. In contrast, for the de-boarding process operations are performed in the reverse order.

Nevertheless, for both processes, airstairs or airbridges are used. Small aircraft may carry their own stairs.

The boarding and de-boarding processes depend on the policy of the airlines (e.g. Low Cost Airlines, Flag Carrier Airlines) and resources available at a specific airport (principal or remote terminals).

By using airbridges, only the front left door of the aircraft depending on the model is used while by means of stairs (mobile stairs or integrated stairs), a second stair for the rear left door of the aircraft can be used in order to speed-up the process. Hence, the operation with airstairs is faster than the process with airbridges, particularly if they are carried by the aircraft.

However, this latter statement is true only when no buses are needed to move passengers between the aircraft stand and the passenger terminal building. Otherwise airbridges is more effective and faster.

These operations are supervised by ground personnel and cabin crew. Moreover, boarding and de-boarding can be performed simultaneously with luggage loading and unloading since these services do not need the same area around the aircraft (in general the left side is devoted to passengers while the right side is devoted to luggage).

The luggage loading/unloading processes

Checked-in luggage can be stowed in the aircraft in two different ways. Either the bags are stowed in bulks or in pre-packed containers. As the containers can be packed before the aircraft arrives to the airport, the ground handling process time for loading luggage will be shorter with container loading than with bulks if the number of bags is large.

The checked-in luggage on a flight has to be sorted, unless it is a charter flight (or other point-to-point flights) where all the bags have the same priority and destination. Otherwise, they might be divided into transferring bags, high-prioritized bags or odd size bags and so on.

The cleaning process

The airlines can request different types of aircraft cleaning services. During daytime the cleaning can take from five minutes (take garbage away) up to forty minutes (garbage evacuation, seat-pockets cleaning, belts placement, vacuum cleaning, etc.). The latter is only performed on aircraft with longer turnaround times. Longer and more careful cleaning is performed during night-time when the aircraft is on the ground and stay for a longer time.

On most aircraft, cleaning and catering can be performed at the same time, but for some small aircraft there is not enough space for both of them at the same time. In the latter case, it does not matter if cleaning or catering is performed first.

The cleaning teams can proceed directly from an aircraft to the next, but at breaks and when they need additional material (pillows and blankets) they have to go back to the base.

There is no significant difference between the cleaning activities at different aircraft types so all cleaning teams can be assigned to any aircraft type. Figure 1.5 shows a cleaning team in the parking stand of an aircraft.

The catering process

The catering involves the withdrawal of the leftover food and drinks from the previous flight and the supply of the aircraft with fresh food and drinks for the next flight. The catering can start when all passengers have left the aircraft. The catering companies use high-loaders to get the catering cabinets on and off the aircraft. High-loaders do not fit all aircraft types, so planning of the assignment of high-loaders to flights is required.

The catering process takes between five and seventy five minutes depending on how much food is needed and the way it is packaged. The catering teams need to go back to the depot between serving two aircraft in order to empty garbage and get new food.

The catering coordinator makes rough estimates of the necessary manpower to perform catering over weeks and the detailed planning, of who is serving each aircraft, are realized every day.

The fuelling process

Fuelling can be performed in two different ways. At some stands there is a hydrant system with fuel pipes in the ground that the dispenser trucks can connect to, in order to fill up the aircraft. At aircraft stands where the hydrant system is not available, fuelling is performed by tankers. There are different types of dispenser trucks: the larger types can serve all kinds of aircraft while the smaller types can only serve small aircraft. However, the small dispensers may be preferred when the area around the aircraft is tightly limited. Also, the tanks vary in size; in general their capacity varies from eight to forty cubic meters of fuel.

Fuelling cannot be performed simultaneously with loading and unloading luggage since these services need the same area beside the aircraft. Before the fuel company starts to fill up, they always check the water content in the fuel. The area around the aircraft has to be planned so that the dispenser truck or tanker has a free way for evacuation. There are also some airlines with specific rules about fuelling while passengers are on-board. Most airlines allow it, but only under certain conditions (e.g. there must be fire extinguisher ready in the immediate surroundings of the aircraft or there must be a two ways of communications between the apron and the aircraft).

The time it takes to fill up an aircraft depends on the capacity of the pipes in the aircraft and, of course, on the amount of fuel needed. The pilot decides how much fuel is needed and must report that to the fuelling company before they can start to fill up the aircraft.

Today, there is no pre-planned schedule for each truck. Not until a fuelling request arrives from the pilot, the fuelling company coordinator assigns a fuelling team to it. This is to say that once a fuelling service is requested, a fuelling team will be assigned to the request and perform refuelling. Figure 1.7 shows the different means used to perform the fuelling process.

Potable water supply and sanitation process

The aircraft has to be released from wasted water and re-supplied with fresh water for the next flight. This is performed by two different vehicles which most often operate at the aircraft opposite side of the luggage handling and fuelling side. This means that water and sanitation can be carried out simultaneously with luggage de-boarding/boarding and fuelling, but they must not be performed simultaneously for safety and space constraints. Figure 1.8 shows the sanitation process and Figure 1.9 displays the potable water supply process.

The de-icing process

Since even very thin layers of frost and ice on the aircraft have a negative effect on the lifting force and the control of an aircraft, de-icing is needed if any part of the aircraft is covered with snow or frost, or if there is a precipitation that could cause this to happen. The de-icing process is divided into two steps: during the first step, frost and ice are removed from the aircraft, usually by a warm, buoyant glycol mix (type 1 fluid). The next step is called antiicing and is performed to prevent new frost and ice from appearing on the aircraft before takeoff by a thicker fluid (Type 2 fluid). The time from anti-icing to take-off (called hold-over time) is limited, as the effect of the Type 2 fluid vanishes after a while. This means that it is not useful to de-ice an aircraft a long time before take-off. How long the hold-over time is dependent on the type of fluid, temperatures and type of precipitation. Therefore it is important to find a de-icing truck that can serve the aircraft at the right time. If the aircraft is served too late, the stopover time will increase with a possible late departure as a result. If the de-icing is performed too early, the procedure might have to be repeated. This result in a rather difficult planning problem, even if the right time windows were known in advance.

Today, the de-icing coordinator plans in general on a tactical basis considering the current weather conditions and the flight schedule, and operationally (when a truck is dispatched) based on a request from the pilot. At the moment the coordinator gets this request, he decides which truck should be assigned to the involved aircraft. In general, no pre-planned schedule is built and the truck-drivers do not know in advance which aircraft they are going to de-ice during the day. The request from the pilot usually arrives at the beginning of the stopover process, assuming that all activities will be performed on time. The de-icing truck will arrive at the aircraft some minutes (depending on the quantity of ice/snow/frost) before the scheduled departure time. Figure 1.10 shows how the trucks perform the de-icing operation.

Ground handling as a complex multi-activity process

Each of the activities that include ground handling process makes use of specialized equipment which must be made available at the aircraft parking place at the right time to avoid delays. Some of the ground handling activities must be performed as soon as possible after the arrival of the aircraft at their parking stand and others must be performed only at some time before departure from their parking stand.

Depending of aircraft operation these two sub sets of activities can be performed in immediate sequence or are separated by an idle period of variable duration according to arrival and departure schedules of a given aircraft. Figure 1.12 displays a standard situation for an aircraft undergoing a turnaround process where space is a rather limited resource and some tasks cannot be performed simultaneously mainly for safety reasons. It appears that the efficient operation of such complex process which repeats with each aircraft arrival or departure is very difficult to be achieved while it is a critical issue for airport operations performance. Then advanced management tools may be useful to cope in a satisfactory way with this problem.

Figure 1.12: Aircraft servicing arrangement -Typical handling operations Boeing 777-300ER [START_REF] Boeing | Boeing, BXXX airplane characteristics for airport planning[END_REF]

Examples of ground handling processes

The ground handling turnaround process may vary according to the servicing arrangement and the necessary tasks for different types of aircraft, different operators, specific needs for some fleets, the layout of the airport and also its airside management policy. Figure 1.13 displays the standard composition and sequencing of ground handling activities for a B737. Figure 1.14displays the composition and sequencing of ground handling activities for a medium haul aircraft at Belgrad International Airport while Figure 1.15 displays the composition and sequencing of ground handling activities for an A320 at Stockholm International Airport.

Figure 1.13: Ground handling process for a Boeing B737 [START_REF] Boeing | Boeing, BXXX airplane characteristics for airport planning[END_REF] Figure 1.14: Ground handling process at Belgrad International Airport [START_REF] Vidosavljević | Modeling of turnaround process using Petri Nets[END_REF]

The temporal dimension of Ground Handling

The turnaround (or block time) is the period of time that the aircraft is on the airport ramp, from the blocks on at aircraft arrival to the blocks off at aircraft departure. It includes the positioning of the pushback tractor and of the tow bar necessary for the push back process.

So, the turnaround period covers all the delays necessary to perform the ground handling activities as well as some idles times (Figure 1.16). In a tight commercial operation, minimum turnaround will be equal to the minimum period of time necessary to complete all the ground handling activities (Figure 1.17) organized in a serial/parallel process.

GH arrival activities

GH departure activities

Idle period

Turnaround time The duration of the turnaround with respect to ground handling, can take different values depending on:

 The size of the aircraft: bigger aircraft need longer turnaround times. For example, according to Airbus manuals the minimum turnaround time for an A320 is 23 minutes, while for an A340 it is 43 minutes. It can be noted that this minimum turnaround time is lower bounded by the time required for the brakes to cool down (about 20 minutes).

 The type of the flight: short-haul flights are operated with higher frequency than long-haul. The short-haul flights operate very often in tight conditions, while long-haul flights, which require longer pre-flight servicing time, dispose in general of larger time margins.

 The number of passengers or the size of the freight to be processed.

 The airline strategy: some airlines may decide to insert a buffer time when planning the turnarounds so that their arrival/departure schedules are more robust to ground handling unexpected delays.

Aircraft builder provide to their customers (the airlines) for each type of aircraft recommended ground handling procedures taking into account safety issues. They produce, for each ground handling activity directly related with the aircraft, nominal durations as well as minimum and maximum values. The data stored in these charts assume standard operational conditions. In fact, as it was mentioned before, they are also dependent on local regulations, on airlines procedures and on actual aircraft conditions.

GH arrival activities

GH departure activities

Minimum turnaround time [START_REF] Airbus | Airbus, AXXX airplane characteristics for airport planning[END_REF] The figure 1.18shows that the total turnaround time is about forty five minutes for the B777-200 and the figure 1.19 indicates that the total turnaround time is about sixty four minutes for the A330-300 aircraft.

The figures above are relative to two aircraft designed for long haul flights. Many tasks are performed simultaneously according to the operations sequencings displayed in the previous section. In the figures, assessments are based on passengers' mixed-class configuration. It is assumed that all the equipments are working properly and that weather conditions are normal. As the aircraft activities and conditions in which these operations are carried out are different in each airport and airline, different values can be produced with respect to the duration of these tasks.

Critical path analysis of ground handling process

It can be of interest for managers to know for each type of aircraft involved in a given air transport operation, what can be the best performance of ground handling with respect to delays. The critical path is the set of activities that are critical for the total duration of the considered process. Delaying a critical activity immediately prolongs the stopover time.

Statistical analyses causes [Frick and al, 2009] have identified these critical processes as consisting of de-boarding, then fuelling, catering or cleaning and finally boarding. According to the same statistical analyses, it appears that the frequency of occurrence of fuelling on the critical path is 57%, 35% for catering and 8% for cleaning.

Activities out of the critical path can be delayed somehow, according to their margins, without influencing the total duration of the process. This will depend on the respective total durations of these three paths.

In the next table (Table 1.2 These results display the large variability of ground handling delays in nominal operation.

Conclusion

The above study demonstrates the diversity and the complex nature of the ground handling activities performed on a grounded aircraft which are organized in a serial-parallel structure where any delay on a particular activity may have a strong impact on its overall performance.

Soon it appears that the diversity of activities to be performed as well as the need for a tight synchronization, not only on an aircraft but on a stream of arriving/departing aircraft introduce the need for an efficient management structure to maintain this whole process as story less as possible within the whole airport operations. The effectiveness of ground handling activities is critical for airports to provide acceptable levels of service and capacity for the processing of flows of aircraft and passengers.

In the following chapter the issue of the organization of ground handling management at airports as well as its main objectives will discussed. Table1. 2: Minimal and maximal value for the ground handling process

Aircraft

CHAPTER 2 ANALYSIS OF THE ORGANIZATION OF GROUND HANDLING MANAGEMENT AT MAJOR AIRPORTS

Introduction

According to the previous chapter, it appears that ground handling represents one of the critical activities which is related to the quality of service provided by airports in handling the flight traffic congestion there. Airport authorities, aware of this fact, have tried in general to find an appropriate solution to the ground handling management organization and operation. This has led to a large diversity of proposed solutions with respect to the organization of the ground handling management.

So, in this chapter the stakeholders involved with ground handling management at different airports are identified, while the pros and cons for their involvement with the ground handling activities are discussed.

The relative importance of ground handling with respect to the overall management of an airport is discussed in terms of expected costs and benefits.

Finally, the different ground handling management duties are classified according to different time scales, allowing defining strategic, tactical, operational and real time ground handling management functions.

The ground handling stakeholders

When considering different airports in the world, it appears that a large variety of stakeholders can be involved with ground handling management. For the distribution of ground handling functions between stakeholders, there is no general standard or rule that can be applied to airports. The ground handling operations can be carried out under the direct or indirect management of the following stakeholders: the airport authorities, the airlines and specialized ground handling companies. Therefore ground handling operations can be managed globally or partially:

 Directly by airport ground handling managers,  Directly by airlines ground handling managers,  Ground handling companies working for the airport  Ground handling companies working for airlines  Or by combinations of these four situations.

In all these situations specialized subcontractors can be called to perform specific ground handling activities.

The organization of ground handling management at large airports depends very often on their operational structure which may include besides common areas for secondary airlines, hub terminals for main operating airlines. With respect to airport authorities, they are primarily concerned with the management of the infrastructure of the airport (airside and groundside) to provide capacity to process aircraft traffic and passengers/freight flows.

Historically airports and airlines have been involved in ground handling activities, but with the development of air transportation and the need of more and more specialized ground handling services, these services have been delegated to specialized ground handling companies. However, in many airports, the involvement of airport authorities in ground handling activities remains important.

Airports, airlines and ground handling operators

The participation to ground handling activities of airports authorities, airlines and specialized ground handling companies present for each of them several advantages and disadvantages which can be determinant in many cases for the resulting ground handling organization at a specific airport.

In general, the ground handling business is not an area from which a considerable profit can be expected since ground handling staff and equipment costs are high while the operation is subject to large variations during a day (peak hours) and within the week, with seasonal effects which can be very pronounced. In the case of a direct management of ground handling activities by airports, revenues barely cover ground handling costs and in many cases, they can be smaller than related costs. For the airport, these losses can be covered by revenues from other areas, such as landing fees or diverse concession revenues. The same circumstances happen when an airline takes care of its own ground handling.

Here are presented pros and cons for the involvement of airport authorities, airlines and service companies in the ground handling sector:

The point of view of airport authorities:

 Advantages to participate in ground handling:

 Master globally all the transfer processes whether for passengers/ baggage or for freight to guarantee efficient connection and timeliness.

 Provide uniformly to customers the required quality of service by controlling and optimizing all the process flows and so improve competitiveness with respect to concurrent airports.

 Ensure global safety and security conditions by mastering simultaneously infrastructures and processes.

 Provide ground handling services when no other stakeholder is providing it (for example the de-icing which, being a seasonal activity is not attractive to investors).

 Disadvantages to participate in ground handling:

 Difficulty of attending efficiently the specific ground handling needs of the different airlines operating at the airport,  Difficulty to integrate and process efficiently the additional information flows generated by this activity.

 Depending on the commercial status of some airports (public owned), difficulty to enforce an efficient organization of ground handling activities.

The point of view of airlines:

 Advantages to participate to ground handling:

 Master globally the transfer processes involving their customers to ensure continuity and timeliness of passengers, luggage or freight flows.

 Control the quality of service (delays, lost luggage occurrences, catering, cleanness…) of ground handling provided to their customers to protect or improve the airline commercial image.

 Control ground handling operations costs which have an impact on air ticket pricing.

 Cover the unavailability of local ground handling operators or the inability of the airport to provide it with acceptable level of service.

 Disadvantages to participate to ground handling for airlines:

 This means to localize additional equipment and staff at an airport which can be a mere stopover in his commercial network.

 This means to be involved in complex logistics problems including the availability of ground handling products.

 Penalizing constraints with respect to the location and the size of their ground handling depots can be imposed by the airport authorities considering the available airside areas for other stakeholders.

 The lack of scale may turn the operation of ground handling by the airline less cost attractive than when provided by a larger ground handling operator at the airport. In some cases airlines (airlines alliances for example) can join together to provide a common ground handling service.

The point of view of independent ground handling providers  Advantages to participate to ground handling at a given airport:

 Opportunity of profit in a large airport with high levels of demand for ground handling services.

 Acquire a large share of the ground handling market in some important airports or in a network of airports.

 Acquire a sound position in airports with high development perspectives in the near future.

 Disadvantages to participate to ground handling at a given airport:

 Low profit perspectives in the near future.

 Strong competition of already established ground handling providers.

 Bad operational conditions offered by the airport authorities.

In theory, some scale advantages could be expected from centralized ground handling operations. A single company operating all over the airport may expect to cope with more regular activity levels during the day and should minimize duplication of facilities and fleets of service vehicles. However, it can be expected that the advantages will be balanced by the disadvantages that come from centralized operations and lack of competition. Anyway the dimensions and the organization in different areas of large airports turn in general unfeasible the idea of operating ground equipment from a unique base. In fact, for these large airports the ground handling function must be subdivided into a number of self-sufficient organizations attached to large terminals.

The current situation with respect to Ground Handling

At important airports such as Frankfurt, Hong Kong and Genoa, the airport authority is responsible for most of the ramp handling activities as well as for passenger/baggage handling. In that case, the airport authority is directly in charge of the ground handling sector.

In other airports which present major hubs for airlines, the main ground handling activities are carried out directly or monitored by these airlines. Even, some of these airlines can take care of the ground handling of other airlines through some agreement between them.

For example, USAir performs all its ground handling at Los Angeles International Airport and provides ground handling services to British Airways. At New York JFK, United Airlines handles not only its own traffic but also some others from the numbers of non-U.S carriers.

At some other airports, ground handling companies have replaced airlines to provide a service which was uneconomic for airlines. For example, at Manchester International Airport, Gatwick Handling performs all terminal and ramp handling functions for a number of airlines.

Another example is Allied at New York JFK Airport, which performs ground handling for a number of non-based foreign carriers. Table2. 1: Distribution of responsibilities for ground handling operations at 72 selected airports [START_REF] Ashford | Airport Operations[END_REF] The current situation in Europe has been influenced by the 96/67/EC Directive whose objective was to promote for Ground Handling efficiency, quality and prices reductions by enforcing competition between ground handling service providers. This directive has been implemented progressively in the EC states and to new coming states. The main results of this politic have been, although airport ground handlers still keep the majority of market shares, to decrease them. Also some airports have decided to sell their ground handling activities to airlines and/or to specialized ground handling providers.

The importance of managing ground handling

In this paragraph, the main reasons for researching an efficient and feasible organization of ground handling at airports are reviewed.

Ground handling costs

Ground handling costs are supported ultimately by passengers and freight through transport fares. However airlines have to pay for ground handling services which can be seen by them as fixed costs attached to a flight. In Annex II are displayed the ground handling fees applied at Tallinn Airport in 2012.

For airlines, turnaround costs at airports include all costs directly associated with the services that airlines must pay or cover at an airport from approach, taxiing, ground handling at arrival, parking, ground handling for departure, taxiing and take off. Then, airlines turnaround costs include air traffic control charges, landing charges, parking charges, ground handling charges, noise and emission charges, and passenger charges. They vary according to the type of aircraft and the airside organization of the airport.

The following figure ( It appears that the structure and amounts of airport charges present a large variability in Europe. Also, since the organization of ground handling is different in these airports, a variable part of these charges is destined to cover ground handling costs. Charges directly or indirectly connected to ground handling costs are: parking and bridge charges, passenger charges and security charges, although passenger charges are mainly involved with passenger processing at terminals. Then, it can be considered that in the average, no more than 15% of the turnaround charges are destined to cover ground handling costs. This share of turnaround charges is rather small but cannot be neglected from the point of view of airlines.

Costs of Ground Delays for Airlines

Delay can be defined as the period of time to add to the scheduled time at which an operation should be completed to get the actual completion time of the operation. Exact delay values turn available only once the operation has been executed but they can be estimated in advance from different probabilistic models when statistics are available. Of most interest are here the delays at departure and the delay at arrival of flights since ground handling can be a direct cause for departure delays, while ground handling may be expected to contribute to the compensation of delayed arrival of flights.

Ground Handling and Departure Delays for Airlines

Delay at departure can be the result of many factors and among them ground handling malfunction. Ground handling delayed completion time can result in additional delays when a time window for take-off, related or not with a time window for landing at arrival, is lost.

Departure delays can be seen as a quality index for many passengers when considering the service provided by the airline and the airport. In long haul flights, departure delays can be in many situations compensated by using favourable winds or at an additional fuel cost. In some other situations, to this initial delay, are added delays resulting from adverse wind conditions. Delays at arrival result in a rescheduling of airport activities around the considered aircraft. This is a perturbation to any planned schedule for ground handling which results either in the rescheduling of some assignments of staff and equipment or in the activation of ground handling reserve resources.

There are six main causes for flight departure delays: rotation (late arrivals), ATFM/ATC retaining the aircraft at parking stand until a traffic clearance is available, airport authorities specific decisions (for example additional person/luggage checking for some security reason) , ground handling operations, technical problems with aircraft systems needing extra maintenance/repair operations and adverse weather conditions. Observe here that rotation delays can be caused also by upstream traffic problems coped by ATFM/ATC. [START_REF] Fricke | Delay impacts onto turnaround performance Optimal time buffering for minimizing delay propagation[END_REF] A study performed at London Gatwick Airport in 1996 (European Civil Aviation Conference, 1996) showed that the delay due to ground handling was the second largest cause to flight delays after ATC: ATC-related delays were directly responsible for 30% of total departure delays, while aircraft/airline ground services accounted for 25% of these delays (Table 2.2).

Global studies have been performed more recently in Europe and USA. The figures bellow show results for the year 2004 where the proportion of departure delay causes are rather different but demonstrate the importance of ground delays. Ground operations delays here include airline control delays, maintenance operation and ground handling operations.

The differences in contribution proportions to departure delays can be explained by the rather different airspace structure and ATFM/ATC efficiency, airlines network structure and ground operations organization.

According to [START_REF] Ronchetto | The costs of delays and cancellations -Analysis and means for cost reductions, m2p Consulting, Presentation[END_REF], the majority of departure delays in the US airports are the ATC in the first place with 37.1% of the total of departure delays, the ground operations in the second place with 30.7% and which include the ground handling activities, the connection between flights comes in the second place with 28.3% and the weather and the airport authorities come in the lasts places with 3.6% and 0.2%. But it is not the case of the European airports in which, according to the same study, the ground operation comes in the first place with 58% which include the ground handling operations, the ATC in the second place with 25%, the airport authorities comes in the third place with 11%, and in the last places come the connection between flights and the weather with 4% and 2%.

Direct cost of ground delays for airlines

The evaluation of additional costs for airlines resulting from ground delays is a difficult issue and different figures have been produced. For example [START_REF] Janic | The flow management problem in air traffic control: a model of assigning priorities for landings at a congested airport[END_REF] estimated for European airlines the cost of a ground delay of an hour is equal to $1330 for a medium aircraft, $2007 for large a aircraft and $3022 for an heavy aircraft. For the US air transportation market, [START_REF] Richetta | Solving optimally the static ground holding policy problem in air traffic control[END_REF] estimated the cost of a ground delay of an hour equal to $430 for small an aircraft, $1300 for a medium aircraft and $2225 for a large aircraft. The significant variation between these figures can be related to the difference of structure between the European and the US domestic networks at that time.

Passengers related delay costs

Delays supported by passengers represent also a cost for the airline in two ways:

-Loss of image by offering a perturbed transportation service to passengers.

In general transportation is only a mean for passengers to achieve some class of activity (from professional to recreational activities) and transportation delays may have important consequences on these activities. There, complex calculations including passenger composition of flights, wage rate distribution and others, lead to different figures for the estimation of the mean value of the lost time per passenger and per hour. In general this value, like in other transport studies, is related with the mean wage. For example the FAA adopted in 1996 for the UK air transportation market a mean value of 64 $/hour [START_REF] Wu | Aircraft operational costs and turnaround efficiency at airports[END_REF]].

-Payment of penalties according to regulations to the passengers which produce a claim.

The delay is considered important, according to regulation n° 261/2004 about passengers rights of the European Parliament and Council and assistance must be proposed to the passengers, if the flight delay is of:

-two hours or more for flights of less than 1500km, -three hours or more for all (intra-community) domestic flights of more than 1500km and for others flights with distance between 1500km and 3500km, -four hours or more for other flights.

Then, when a flight has been delayed for an important period of time, the airlines have to provide assistance in different ways to the passengers:

-Refreshments and possibility of restoration depending on the waiting time.

-When the new expected departure time is delayed for the next day, an accommodation in hotel, the possibility to make two phone calls/ fax and the eventual transfer to an alternative airport have to be proposed to the passengers by the airline.

-Whatever the itinerary, if the delay is more than five hours, the passenger are entitled to ask for reimbursement without penalty of the cost of the ticket for the part of flight not made or to flight back to his initial point of departure as soon as possible.

Time Scales for Ground Handling Management

Depending on the organization of airport activities, ground handling management can be integrated to the overall management of the airport or can be performed by specific ground handling managers. Then, once the role of the different ground handling stakeholders has been defined, different time scales can be considered to set up ground handling management.

Figure 2.2 presents a classical timeline for the management of a generic system. In the next paragraph definitions for the contents of each of these management horizons in the case of ground handling is proposed.

Strategic planning for ground handling

The strategic planning time scale corresponds in general to long-term decision making relative to the definition of the general philosophy adopted for the planned system. In the case of airport ground handling it is performed by the airport authorities and covers decisions such as the choice of its main physical and managerial characteristics. For example the decision of subdividing ground handling by passenger terminals and some remote areas is a strategic planning decision. The distribution of ground handling management functions between airport, airlines and ground handler providers is another one. The structure of ground handling charges collection will be also established at this level (direct charging by the ground handling service providers to the airlines, indirect charging through airport charges, etc).

Strategic planning is based on long run predictions of traffic similar to those used for the airport design planning or upgrade. Strategic planning provides a working environment for ground handling which should remain roughly similar during some periods of operation (several seasons or years) to provide a stable perspective to its industrial stakeholders.

Tactical planning for ground handling

Ground handling tactical planning is concerned with the planning of the main resources necessary to face the demand during the next period of operations for ground handling service. This is done by the managers in charge of ground handling within the environment set up by the strategic planning decisions. At this level ground handling charges will be established in coordination with airport authorities and airlines. Tactical planning is

Operational planning for ground handling

Operational planning generates detailed execution plans for the next days of operation (a week, a fortnight). Within this time horizon, the level and composition of demand and available resources can be considered known with sufficient reliability to start assigning each available ground handling resource to different unitary ground handling demands (a flight arrival, a flight departure or both) over the period. The problem is then to assign the work to each individual resource as efficiently as possible under the conditions specified by the previous planning steps. This usually means, performing as many tasks as possible with the available personnel, while ensuring that all operational constraints are satisfied. Anyway a planning for the ground handling operations, amendable when necessary, is set up for the following days.

Real-time management for ground handling

Finally, real-time management of ground handling operations is concerned with adapting the current existing plan for the day of operation to handle disturbances which should occur during that day. Real-time (or dynamic) management reacts on line to unpredicted events by reassigning available resources to cover disturbed demand for ground handling services. Depending on the importance and extent of perturbations, this reaction can either be a limited adaptation of a nominal operational plan, termed as regulation, or a complete redefinition of it, termed as disruption management.

Conclusion

The analysis performed in this chapter shows that the concerned stakeholders ( airport authorities, airlines, specialized ground handling operators) are involved in very different degrees in the management of ground handling from an airport to another, in general according to specific circumstances.

When considering direct and indirect costs related to ground handling at airports, direct cost resulting from the execution of ground handling tasks represent a small amount with respect to potential over costs resulting from even limited turnaround dysfunctions. So, the EC recommendation to call for ground handling subcontractors to reduce ground handling costs by promoting competition seems to be inessential in this field of activity. What appears more important is the ability of the ground handling decision making process to prevent dysfunctions and to reduce their impact when they happen. This ability should operate either at the level of the management of a specific ground handling activity over an airport or at the level of the coordination between the different ground handling activities.

In the following chapter an overview of the optimization approaches developed to produce efficient ground handling decision processes at the operations level is developed and discussed.

CHAPTER 3 OPTIMIZATION APPROACHES FOR GROUND

HANDLING OPERATIONS: AN OVERVIEW

Introduction

The ground handling process has received less attention than other airport resources management problems in the Operations Research literature where a rather few number of published works can be found. Most of the published studies are focused only on one type of ground handling resource (passenger buses, catering vehicles, fuel trucks, etc) while the majority of the ground handling management literature copes with off-line situations. The offline approach assumes that aircraft and airlines meet perfectly their scheduled arrival times and departure times, it corresponds to a situation where each ground handling vehicle must be assigned to a list of successive tasks on different aircraft along the operations period. On the contrary, in the on-line approach a decision process must be set up to face successive or simultaneous delays on scheduled events and perturbations in real-time situations. Variants of the on-line approach are moving time window approaches and disruption management situations.

Works have been published with respect to:

-the management of passenger bus fleets, -the management of oil truck fleets, -the management of catering vehicles, -the management of aircraft cleaning manpower -the management of de-icing fleets.

All these problems present common characteristics between them and with other fleet or multi-fleet management problems found in other transportation areas such as industrial logistics, distributed service delivery and port operations. Many of these problems can be seen as off-line airside fleet routing problems which may be considered as variants of the classical Vehicle Routing Problem (VRP) [START_REF] Toth | [END_REF]. In Annex II, the main solution approaches to the classical VRP problem and its variants are briefly discussed.

In this chapter are introduced and analyzed some of these problems, including considered objectives and constraints, mathematical formulation of the problem, the proposed solution approaches and numerical applications if any. Then a global analysis of the state of the art in this field is performed.

Management of an airside passenger bus fleet

Problem definition

Here is considered the problem of managing a fleet of airside buses used to transport passengers from arriving aircraft to passengers terminals and from passengers terminals to departing aircraft where in general aircraft are in remote position and where the aircraft parking areas are linked to passengers terminals by a ground network of lanes used in general not only by busses but also by other ground handling vehicles. Permanent bus transportation between passenger terminals, with either scheduled or unscheduled operation with in general larger buses, is not considered here. The main objective is to assign buses to arriving or departing aircraft so that passengers arrive on time at destination (passengers terminals for destination passengers and departing aircraft for origin passengers) and flights are not delayed. Another permanent objective is to limit the operations costs generated by the bus fleet by minimizing total travelled distances.

Problem class

Many characteristics of this problem differentiate it from other VRP (vehicle routing problems) and make it someway harder to be tackled. With respect to its specific operations characteristics:

-The buses operate in a pendulum way between single aircraft and terminals.

-The followed routes are demand driven and are not repetitive (no frequency of operations).

-Parking space is very limited in the operating area of busy airport surfaces.

-The planned routes must consider possible varying delays at the parked aircraft or passengers terminals.

-The vehicles serve only one group of customers at a time.

With respect to the dynamic aspects of this problem, while it can be assumed a complete knowledge of which aircraft (flights) have to be serviced, there is uncertainty about when and where each aircraft will be requesting service or how long it will take.

Problem formulation

In [START_REF] Kuhn | Airport Service Vehicle Scheduling, Eighth USA/ Europe Air Traffic Management Research and Development Seminar[END_REF] the management of an airside passenger bus fleet which services aircraft after their arrival and departing aircraft before their departure has been considered recently. After analyzing current operations with the service vehicle dispatcher at Hamburg Airport, a moving time window approach was proposed by these authors where every ten minutes an assignment problem is solved using updated data about the current situation and short term predictions. To solve successively the resulting static scheduling problems, a mixed integer linear program has been formulated in order to get current local optimal solutions minimizing a mix of the total aircraft departure delays and of the service provider fuel costs. The following notations have been adopted:

Binary variable x ij a is equal to 1 if vehicle x serves aircraft j immediately after serving aircraft i, where i=0 at the start and j=0 at the end of the service, otherwise 0 

                X x I i I j x j i j i I i i a D b , , 1 Min   (3.1)
subject to the following constraints:

      X x I i x j i a 1 , , I j   (3.2)     I j x j a 1 , 0 , X x   (3.3)     I j x j a 1 0 , , X x   (3.4)        I k x k j I i x j i a a , , , I j   , X x   (3.5)   1 , 0 ,  x j i a ,    I j i, (3.6) i i T b  , I i   (3.7) x j j x x j a V D F b , 0 , .           , I j   , X x   (3.8)
The first constraint (equation (3.2)) ensures all aircraft receive service. Equations (3.3) and (3.4) impose that all service vehicles begin and end their service tours at location 0.

Equation 3.5) is a flow conservation constraint: a vehicle arriving at an aircraft must leave that aircraft later. Equation (3.7) ensures each possible task is either assigned or not.

Equations (3.8) provide earliest start time constraints for the service at an aircraft is ready.

Solution approaches and comparative results

[ [START_REF] Kuhn | Airport Service Vehicle Scheduling, Eighth USA/ Europe Air Traffic Management Research and Development Seminar[END_REF] considered first an exact solution approach based on a branch and bound technique, and they compared it to a genetic algorithm, to a greedy approach and to actual operations. These different approaches were applied to problems with 6 passenger buses serving 17 aircraft at Hamburg Airport during an hour and to problems with 25 vehicles serving 1000 aircraft at Dallas-Fort Worth Airport during 18 hours.

At the Dallas-Fort Worth Airport, the exact solution approach was not able to provide an optimal solution within an acceptable time. In that case, the genetic algorithm approach provided the best results over the different considered scenarios. In that case, it reduced the mean distance travelled by the busses of about 300 kilometres per day and the mean delay absorbed by aircraft by 25% relative to the greedy approach whose performance was close to actual operations. Then the varying time window approach, coupled with an efficient heuristic, appeared to be able to cope rather efficiently with this problem.

Management of fuelling trucks at airside

Problem definition

In many airports aircraft fuelling is performed by dedicated trucks. In large airports with underground fuelling facilities are available at deck parking positions but remote parking positions must be served independently by fuelling trucks. In low traffic airports, in general fuelling is only performed by fuelling trucks. In general fuelling is performed only some time before the scheduled departure time of an aircraft.

Problem classification

This problem is also close to the VRP (Vehicle Routing Problem) but differs from it by different aspects:

-The demand for fuel varies from one aircraft to another, making the servicing time different.

-For short turn around aircraft the time window to perform fuelling may be quite reduced.

-Late demands are frequent, their origin can be the result of new weather estimates on long haul flights or of late adjustments in airlines fleet operations.

-Fuelling trucks have a limited fuel capacity and in general only one vehicle is sent to perform this operation at a given aircraft.

-Fuelling trucks must return to a fuel station to recompose their fuel load.

All of this makes this problem to be a very special case of VRP problem.

Mathematical formulation

This problem has been tackled recently by [START_REF] Du | ACO-IH: An Improved Ant Colony Optimization Algorithm for Airport Ground Service Scheduling[END_REF]. They studied the fuel ramp operations and considered the scheduling problem of fuelling vehicles and proposed a solution approach based on the Vehicle Routing Problem with Tight Time Windows (VRPTTW) with multiple objectives. Here n flights are to be served by fuelling trucks at different gates in the airport. To each flight I is attached a fuel demand d i corresponding to a service time of duration p i and with a time window [ a i , b i ] with a i as earliest starting time and b i as latest starting time. The adopted notations are: where

1  ik x if truck k   m , , 1   is assigned to flight i f ,   n i , , 1   and 0  ik x otherwise. k y =1 if the k th truck comes into and k y =0 otherwise,   n i , , 1   . i s is the start time of the ground service for flight i f ,   n i , , 1   .
k k k B C t   if the k th truck is called into service, t k =0 otherwise, with     ik i i i k x p s C . max   and   ik i i k x s B . min  .

Solution approach

Once merging some of these objectives into a single one and transforming the others in level constraints, this problem can be formulated as a large Integer Linear Optimization Problem.

However it can be easily concluded that the complexity of this resulting problem is high, so that heuristic approaches should be designed to provide efficient solutions within an acceptable time.

Then, the authors in [START_REF] Du | ACO-IH: An Improved Ant Colony Optimization Algorithm for Airport Ground Service Scheduling[END_REF]] adopted a specialized Ant Colony Optimization (ACO) to try to solve efficiently this multi objective combinatorial optimization problem.

Ant colony Optimization has been developed by [START_REF] Dorigo | Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[END_REF] to solve at first the Travelling Salesman Problem (TSP) by adopting the collective behaviour of ant colonies with respect to food search which is based on the current pheromone levels on the candidate trails. The heart of this ACO algorithm is the updating rule of the path choice probabilities. There the probability for truck k to choose flight j after having chosen flight Iis given by:

                   ) ( ) , ( ) , ( / ) , ( ) , ( ) , ( i U u k k u i u i j i j i j i p         (3.9)
where the positive parameters  and  represent the relative importance of the pheromone and the impedance levels in the choice of destination,

) (i U k
is the set of flight which can be visited by truck k from flight I,

) , ( j i 
is the level of pheromone on arc (I, j) and ) , ( j i  is the impedance level between flights I and j. In this study they adopted the function:

  ) ( ) ( / 1 ) , ( i i j j j s b s s j i i             (3.10)
where in the denominator, the first term is the travelling time between flights I and j, π j is the service time for flight j and the last term denotes the slack before the latest start time of the service of flight j .

An Earliest Start Time heuristic has been proposed to provide an initial solution, and then from one iteration to the next, local and global updating rules have to be activated.

The local updating rule is such that:

max ) , ( ) 1 ( ) , (           j i j i (3.11) where   1 , 0  
is the pheromone decay parameter and

   / 0 max 
where 0

 is computed from the initial solution.

The global updating rule is such that:

r r R r w j i j i           1 ) , ( ) 1 ( ) , ( (3.12)
Where R is the set of the best solutions found at the previous iteration and where 0  r w if the r th best solution does not use link (i,j) and 0  r w otherwise.

Achieved performances

Numerical applications show that the exploration time of this Ant Colony algorithm was too excessive even for medium size problems. Then, to get better results they introduced an heuristic based on the Earliest Due Date. This heuristic h selects the flight according to the earliest due time to serve when the trucks are idle. They applied this algorithm to problems with 20 to 154 flights to be refuelled during a day period. They compared the solutions obtained with the above approach (limited to 20 iterations) and an Earliest Committed Service First which consists in choosing the first available truck each time a flight demands refuelling.

In terms of size of the necessary truck fleet, the proposed method was best by 15% for small size problems to 25% for larger problems, while the computation times were equivalent.

Management of a connecting baggage fleet

Problem definition

Here is considered the problem of managing the fleet of ground vehicles in charge of transporting baggage for connecting passengers between their arrival and departure flights in an airport. These passengers arrive to the airport on inbound flights and depart on outbound flights within a reduced period of time. Their baggages are not directed to the arrival halls like the baggage of destination passengers. They must be collected separately and transported to the departing flights. The process of collecting and redistributing the connecting baggage vary in general according to many factors: the structure of the airside including terminals, parking areas and airside circulation lanes, the regulations with emphasis on security issues and contracts between airlines and ground operators. The handling company is in general supposed to operate a fleet of homogeneous transportation vehicles which perform all the day round trips from/to the baggage dispatch facility while serving flights and/or baggage handling stations. Each vehicle returning to the baggage dispatch facility is assigned to a new trip which must be performed immediately or not, depending of the availability of the baggage.

Then the decision problem considered here is relative to the planning of the routes for the transportation vehicles such that each bag is delivered directly to the flight, or to the baggage station, respecting time windows constraints. The objective is in general to deliver in time to the departing aircraft the corresponding baggage and when this cannot be achieved with the available fleet of transportation vehicle, to minimize the number of bags which miss the departing flights within a day period.

Class of problem

The baggage delivery problem is a variant of the Vehicle Routing Problem (VRP) where each delivery must satisfy strict time windows since all bags for a flight must be on-board within a certain amount of time before take-off, while they cannot be delivered until the aircraft is ready for that. Deliveries to baggage handling stations obey to maximum delay constraints which can be framed also as time window constraints. These constraints are characteristic of a Vehicle Routing Problem with Time Windows (VRPTW). However, common characteristics to baggage delivery problems differentiate them from a classical Vehicle Routing Problem with Time Windows:

-The possibility of delivering a bag to one of two types of locations (aircraft or baggage handling stations) each having different time window types makes this problem be a special Generalized Vehicle Routing Problem (GVRP) as studied by Ghiana and Improta in [START_REF] Ghiana | An efficient transformation of the generalized vehicle routing problem[END_REF] -The planning of multiple trips for each delivery vehicle makes this problem be a special Vehicle Routing Problem with multiple trips (VRPM) as studied by [START_REF] Prins | Efficient heuristics for the heterogeous fleet multitrip vrp with application to a large-scale real case[END_REF].

-The possibility of splitting bags between different delivery vehicles for the same flight makes this problem to be a special case of the Multi Depot VRP (MDVRP), as studied in [START_REF] Nagy | Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[END_REF].

Although some general frameworks have been developed for large classes of Vehicle Routing Problems with additional constraints [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF], [START_REF] Ropke | A unified heuristic for a large class of vehicle routing problems with backhauls[END_REF], only the work by Clausen and Pissinger [Clausen and al, 2010] considers the whole set of the baggage delivery problem specific constraints. In the following, their adopted formulation for the offline optimization problem is presented as well as the main ideas of their proposed on-line greedy solution algorithm with some numerical results.

Mathematical formulation

In the case considered by Clausen and Pisinger, the baggage handling company operates a number of baggage sorting and dispatch terminals to process the connecting baggage. The company is in charge of transporting the baggage either directly to the departing flights or to the baggage handling stations where they are merged with the other luggage assigned to the same flight. Delivering to the handling stations is performed only if this can be done before the bags of origin passengers are taken from the station to the aircraft.

This problem has been formulated by Clausen and Pisinger as a cumbersome Integer

Programming problem where N baggage must be transported using K identical vehicles of capacity Q. Each vehicle is assigned to a maximum number of routes R and each times return to a depot to load new baggage to be delivered within given time windows either at a departing aircraft or at a handling station. A 2N+2 nodes graph is constructed where the first N nodes represent the flights, the next N nodes represent handling stations, node 0 represents the initial depot while node 2N+2 is the final depot. Let V be the set of nodes and E be the set of edges. Strong connectivity is assumed for this graph. An empty route connects directly the initial and the final depots. To each node is assigned a time window [a i , b i ]. The processing duration at node I is given by s i while the travel time between two nodes I and j in the graph is given by t ij and the arrival time of baggage i is written u i . The binary variable

1  ijkr x if vehicle k goes from i to j along the r th route, 0  ijkr x otherwise, 1  i z if baggage i is not delivered and 0  i z if it is delivered, ikr S
is the time at which service at node i is completed by vehicle k on route r. Then we get:

  N i i z 1 M in (3.13) Subject to 1 , , , , , ,     i r k j i n r k j i z x x ,    i , V j  , K k  , R r  (3.14) 1 , , , 0  r k j x ,  V j  , K k  , R r  (3.15) 1 , , 1 2 ,   r k n i x ,  V i  , K k  , R r  (3.16) Q x r k j i  , , , ,      j i, , 1 2   N j ,  K k  , R r  (3.17) 0 , , , , , ,   i r k i j r k j i x x ,  V i  , K k  , R r  (3.18) jkr ij i ikr r k j i S t s S x      1 , , , ,      j i, , K k  , R r  (3.19) i ikr i b S a   ,  V i  , K k  , R r  (3.20) 1 0 1 2    kr kr n S S ,  K k  (3.21) i kr r k i j u S x    0 , , , , 1 ,  V i  , K k  , R r  , V j  (3.22)   1 , 0 , , , ,  r k j i x ,      j i, , K k  , R r  (3.23)   1 , 0  i z ,    i (3.24) 0 , ,  r k i S ,  V i  , K k  , R r  (3.

Proposed solution approach

Considering the size of real life instances and the dynamic aspect of the problem, a greedy algorithm was proposed to solve approximately this problem. With this algorithm, each vehicle is scheduled individually and only for one trip at a time. The scheduling is performed once a vehicle arrives to the dispatch hall (at start of its operation or when it returns from a previous delivery trip). Then at that time a delivery task is generated and assigned to the driver of that vehicle. This task indicates which set of bags must be picked up at each location in the dispatch hall and the list of delivery destinations for each bag. The algorithm is designed so that "good" sets of tasks are generated. A good set of tasks has been defined as being such as flights with an imminent departure flights are treated with priority, the task assigned to a vehicle should handle as many bags as possible and the routes associated with the delivery tasks should be as short as possible. Then the proposed heuristic makes use of penalizations to handle these sub-objectives.

The algorithm considers all bags present in the dispatch hall at the time of calculation and the induced sub-graph containing only nodes and Edges belonging to the depot. For each edge (i, j) is computed a cost that should reflects the attractiveness of delivering the bag associated with node j:

D ij D R ij R L ij L ij c          (3.26)
where L ij  is the cost associated with the type of delivery , R ij  is the cost associated with the length of the route and D ij  is the cost associated with the departure time at location j, here

D R L    , ,
are real valued weights.

The edges with lowest cost are selected in a greedy way up to delivery time constraints or vehicle capacity constraints.

Obtained results

To test the algorithm, they used real data about transfer bags for a full week of operations.

The airport considered in their tests was composed of two dispatch facilities. The numerical results showed that the proposed algorithm is robust with regards to the stochastic aspect of the bag delivery times and the vehicle travel times.

Management of a de-icing fleet

Problem description

Aircraft de-icing becomes a necessary ground operation before aircraft departure when there is it has been parked for some time in icing conditions and there is a risk that a layer of ice forms on the aircraft critical surfaces. In that case the aircraft aerodynamic efficiency can be largely deteriorated and a take-off manoeuvre without de-icing can lead to a crash situation.

The de-icing operation is considered to be curative when ice has been already formed and the associated anti-icing operation is considered to be preventive since the effect of the anti-icing liquid remains for a time sufficient to taxi and take-off safely. De-icing is in general the last ground operation before taxiing for take-off.

The de-icing process can be centralized at de-icing stations or decentralized with the use of a de-icing fleet of vehicles. The need for de-icing is dependent on actual weather conditions and aircraft state. Conservative decisions are in general taken by considering meteorological forecast, but current conditions can turn this operation unnecessary for some flights. That means that the demand for de-icing cannot be established too much in advance since it presents can present a large degree of uncertainty. It is worth to observe that the duration of the de-icing operation will depend on the importance of the aircraft icing state. [START_REF] Norin | Integrating optimization and simulation to gain more efficient airport logistics[END_REF]] developed a simulation model for the assessment of the turn-around activities of a de-icing fleet at an airport. This model was validated using Stockholm Airport as reference airport. Then they proposed a mathematical formulation of the de-icing fleet scheduling problem where the objective is to minimize a mix of the total delay for the departing flights and of the total distance travelled by the de-icing vehicles. This modelling approach is detailed in the next paragraph.

Current studies

[ [START_REF] Mao | Agent-based scheduling for aircraft de-icing[END_REF], considered the case of an airport with de-icing stations to which aircraft have to go to be processed before departure. They viewed this problem as a special case of a Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP) [Bruker, 1999] where the objective is to minimize the total delay of aircraft at take-off. There the aircraft were taken as agents and the de-icing stations as resources. A pure First Come First Served-FCFS heuristic has been compared with a FCFS heuristic including penalties (decommitment penalties-DC) to promote the coordination between agents and make them reserve the de-icing trucks as close as possible to their take-off time. The results show that comparing the FCFS to the FCFS with DC, the second approach gives a lower delay regardless of the number of aircraft. [START_REF] Zhiwei | Research of algorithms for aircraft ground deicing operation scheduling model[END_REF] proposed another Multi-Agent based model for the scheduling of aircraft de-icing operations. They try to show that the multi-agent approach [START_REF] Feber | Les systèmes multi-agents : Vers une intelligence collective[END_REF] can be useful in managing this problem by allowing to take better into account the uncertainty and flexibility of the problem and to preserve the interest of all the concerned actors (the airport, the airlines and the ground service company). They proposed a decision making algorithm based on the negotiation between agents which proved superior to a mere FCFS strategy in terms number of de-iced aircraft per period and in the aircraft de-icing delays.

Mathematical formulation

Here we consider the mathematical formulation proposed by [START_REF] Norin | Integrating optimization and simulation to gain more efficient airport logistics[END_REF] for the deicing fleet scheduling problem. It is as follows:

            N 0 i N j i 0, j 1 1 . . . Min K k R r kr ij ij i x w b l a (3.27) subject to 0 1 1       N j kr hj N i kr ih x x ,   N h , , 0   ,   K k , , 1   ,   R r , , 1   (3.28) 1 0 1 1        N j K k R r kr ij x ,   N i , , 0   (3.29) k N i N j kr ij i q x d      1 1 . ,   K k , , 1   ,   R r , , 1   (3.30)   j kr ij ij i i t x M w f s t       1 ,   N j i , , 1 ,   ,   K k , , 1   ,   R r , , 1   (3.31) i i i f s t p    ,   N i , , 1   (3.32) i i STD p  ,   N i , , 1   (3.33) i i i i STD f s t l     ,   N i , , 1   (3.34)   start n k mn stop m t z M f t     1 0 ,   R n m , , 1 ,   ,   K k , , 1   (3.35) 1 0 0    kn j km i k mn x x z , m n  ,   N j i , , 0 ,   ,   K k , , 1   (3.36)   kr j j j stop r x M w p t 0 0 1    ,   N j , , 1   ,   K k , , 1   ,   R r , , 1   (3.37)   kr i i i start r x M w t t 0 0 1 0      ,   N i , , 1   ,   K k , , 1   ,   R r , , 1   (3.38) 0  i t , 0  i p , 0  i l ,   N i , , 1   (3.39)
Here K is the number of available de-icing trucks; N is the number of assignments during the considered time period. M is an arbitrary large constant. Assignment 0 is to the truck fuel station where also all routes start and end; R is the total number of routes performed by the trucks. A route is a feasible sequence of assignments for a fuel truck. R is chosen large enough to accommodate all the routes that the fleet can perform in a day ( N R  ), note that some of these routes may be empty. Here k q is the capacity of truck k, ij w is the travelling time for fuel trucks between assignments i and j, i f is the mean de-icing duration time, 0 f is the truck refill time at the fuel station, i STD is the scheduled departure time of aircraft i and s is the de-icing set up time at aircraft, t i is the start time of fuelling at assignment i, sta rt r t is the start time for the route r , sto p rt r t is the stop time for the route r , i p is the end of the time assignment i, i l is the delay for the aircraft corresponding to the assignment i .

a and b are the weights of the objective function (total service delay at aircraft and total truck , travelling time, respectively).

With respect to decision variables, the adopted notations were such as:

1  kr ij x
if there is an arc from i to j on route r for the truck k, otherwise 0

 kr ij x ; 1  k mn z
if the truck k performs the route

m before the route n , otherwise 0  k mn z .
Then, equation (3.27) is the objective function which corresponds to the minimization of a weighted mix of the delay of aircraft resulting from the fuelling service and of the total travelling time of the fuel trucks. Equation (3.28) ensures that the same trucks arrives to and leaves each assignment on its route. Equation (3.29) defines that every assignment is performed exactly once. Equation (3.30) makes sure that a de-icing truck is going to the refill station before it runs out of fluid. Equation (3.31) specifies that a truck cannot arrive to an assignment before the previous one is completed and the truck has travelled between the assignments. The time an assignment is finished is calculated in equation (3.32) and (3.33).

The possible flight delay is defined in equation (3.34). Equation (3.35) defines that the next route with the same truck cannot start before it is re-equipped with de-icing fluid. Equation (3.36) guarantees that if an arc exists (i.e. if the x-value for an arc is 1) the z-value for the corresponding route is also 1. Equation (3.37) and (3.38) specifies the start and stop times for a route.

Solution approach and results

The above problem is a mixed linear optimization problem (binary variables kr ij x and k mn z , real variables (t i , p i ) whose solution, even for small size instances, requires a large computational effort. Then, to get working solutions to this problem in an acceptable computation time, different GRASP (Greedy Randomized Adaptive Search Procedure) heuristics [START_REF] Feo | Greedy Randomized Adaptive Search Procedures[END_REF] were developed. These techniques generate during the search process a set of concurrent solutions from which dominating solutions with respect to the two main objectives are retained. A simulation model was used to compare in the case of Stockholm Airport the de-icing operations performances resulting from a GRASP based management and from current scheduling rules. They used data from Stockholm Airport before and after the integration of the concept of Collaborative Decision Making and in both cases the GRASP approach proved superior to current scheduling rules.

Management of catering fleets

Problem description

A more sophisticated solution was proposed by [START_REF] Ho | Solving a manpower scheduling problem for airline catering using metaheuristics[END_REF] to tackle the airline catering operations including the staff workload. They considered the problem as a manpower allocation problem with time window and job-skill constraints. The optimization objective consists in the maximization of the total number of assigned jobs. They presented a comparison between Tabu Search and Simulated Annealing approaches to solve the problem.

To test these approaches, they used real-life instance provided form an airline catering company. The results show that the Tabu Search gives better solutions than the Simulated Annealing approaches. They studied also the impact of the team formation and they found that the extension of allowing jobs to be shared between two teams is a good mode of operations. [START_REF] Ho | Solving a manpower scheduling problem for airline catering using metaheuristics[END_REF] . All workers must travel in teams when leaving the depot, denoted by 0 , when visiting job location  , the team returns to the depot, denoted by 1  n (although physically located the same as 0 ).

Mathematical formulation

Teams are formed by grouping driver i and loader j together, where

j i t t  and j i e e  , D i  , L j  .
It is assumed that the number of loaders in a shift is at most the number of drivers in the same shift. Loader j must be in a team with a driver i , whereas, driver i might be in a team with driver h , where

h i t t  and h i e e  , D h i  ,
. Hence, there are m teams, denoted by

  m V , , 1   , where              nSh q q q q L D L m 1 2
. Here, nSh denotes the number of shifts in a day. q L denotes the set of loaders in shift q , q D denotes the set of divers in shift q . Job v can be served by team V k  (with members i and j ) if The set    

j i S S f    (i.
j i j i e e t t L j i L     , /
for D i  , is defined as the set of loaders who are in the same shift as driver D i  . The following sets are defined in similar manner:

    j i j i L e e t t D i j D     , / for L j  and     j i j i D e e t t j i D j i D      , , / for D i  . For each worker D i 
and worker

     i i D i L j D   
, and for each team

V k  , the decision variable k ij x is defined as:        otherwise , 0 team to belong worker and worker if , 1 k j i x k ij (3.40)
For each pair of job locations u and v , where

  v u n J v u     , 1 , 0 ,
, and for each team k , the decision variable k uv y is defined as:

       otherwise , 0 job after y" immediatel " job does team if , 1 u v k y k uv (3.41)
Note that job 0 refers to the initial departure from the depot and job 1  n refers to the final arrival at the depot.

To model the job-skills compatibility constraints, an indicator parameter vi  is defined for each job J v  and each worker

W i  as:        otherwise , 0 worker of set - skill in is job if , 1 i v vi  (3.42)
The decision variable u s is defined for each job u and denotes the start of service of job u (by some team k ). The basic manpower scheduling problem can be started mathematically as:

         V k J u J v k uv y 0 Max (3.43) Subject to:   1      V k j D i k ij L x , L  j (3.44)     1                V k i D i L j k ii k ij D x x , D i   (3.45)     1 2 1                            D i i D j k ij D i i L j k ij k ii D x x x , V k   (3.46) k ji k ij x x  , D j i    , V k   (3.47)   1 1 0      n J v k v y , V k   (3.48)     1 1 0          n J v k hv J u k uh y y , V k   , J h   (3.49)   1 0 1 ,      J u k n u y , V k   (3.50)   1 0       V k J u k uv y , J v   (3.51)             W j D i k ij vj vi J u k uv x y , 0   , V k   , J v   (3.52) v v v b s a   , J v   (3.53)   1 1 M y s x t k uv v k ij i    , V k   ,   J u    0 , J v   , D i   ,      i i D i L j D     (3.54)     2 1 1 1 M x e M y p s k ij i k uv v v       V k   ,   J u    0 , J v   , D i   ,      i i D i L j D     (3.55)   1 1 M y s p s k uv v u u     , V k   , J v u   , (3.56) 0  u s , J u   (3.57)   1 , 0  k ij x , V k   , D i   ,      i i D i L j D     (3.58)   1 , 0  k uv y , V k   , 1 , 0 ,     n J v u (3.59)
Constraint (3.44) restricts the team assignment with a loader to driver of the same shift, while constraint (3.45) states that a driver might be grouped with either a loader or a driver of the same shift. Constraint (3.46) ensures that no more than two workers are assigned to each team (index). Constraints (3.48)-(3.50) guarantee that for each trip the team leaves the depot, after servicing job in sequence, it finally returns to the depot. Constraint (3.51) states that each job is assigned to at most one team. Constraint (3.52) states that job v could only be served by team k if job v is either in the skill-set of worker i or in the skill-set of worker j . Time

Global approaches

Recently, some authors have considered the global airport ground handling scheduling and assignment problem. The global approach has been tackled in two main ways: a fully centralized approach and a fully decentralized approach.

The work by [START_REF] Dohn | Optimizing manpower allocation for ground handling tasks in airports using column generation[END_REF] has concentrated on the management of ground handling manpower by considering that ground handling is managed by a central entity responsible to build up dynamically the teams with the different involved skills, which will be in charge of each arriving or departing aircraft.

The decentralized solution approach of the global ground handling assignment problem has been coped in two ways:

-by considering that the global ground handling scheduling problem is an instance of a multi-project scheduling problem, -by considering that it is a distributed decision making problem.

A Centralized Approach for the Ground Handling

Assignment Problem

Problem description

Here it is considered that each ground handling demand (arrival, departure or both) is processed by units composed of equipment/vehicle and specialized manpower. Service delivery at arriving or departing aircraft obeys to time constraints which can be expressed as time window constraints. Then when following a particular ground handling team, it is successively assigned to different services at different locations and performs a tour which covers some of the parking stands with grounded aircraft. Then it can be considered that each ground handling unit performs a sub tour while it is expected that the whole grounded aircraft will be visited by the required teams of ground handling operators. [START_REF] Dohn | Optimizing manpower allocation for ground handling tasks in airports using column generation[END_REF] proposed a formulation of the scheduling problem of personnel at airports where the objective is to minimize the total number of unassigned tasks and minimize the operating cost of each team. So they introduced the Manpower Allocation Problem with Time Windows whose formulation is as follows:

Mathematical formulation

Let   n C
, , 1   be a set of n tasks and consider a set V of inhomogeneous teams of workers.

To each task is associated a duration, a time window, a set of skills and a location. It is supposed that each task C i  has to be performed in a time window  

 

   V k C i N j ijk x Max (3.60) Subject to: i V k N j ijk r x      , C i   (3.61) ik ijk g x  , C i   , C j   , V k   (3.62) 1 0   N j jk x , V k   (3.63) 0       N j hjk N i ihk x x , N h   , V k   (3.64)   j jk oj k s x M t e     0 1 , C j   , V k   (3.65)   k k i i i f x M t s     0 0 1 , C i   , V k   (3.66)   j iijk ij i s x M t s     1 , C i   , C j   , V k   (3.67) i i i b s a   , C i   (3.68)   1 , 0  ijk x , N i   , N j   , V k   (3.69)   0     i s , C i   (3.70)
The objective (3.60) is to maximize the number of assigned tasks. A task is counted multiple

times if it is processed by more than one team ( 2  i r
). The constraints (3.61) guarantee that to each task is assigned at most the right number of teams or possibly less, if some of its split tasks are left unassigned. Only teams with the required skill can be assigned to a specific task [START_REF] Dohn | Optimizing manpower allocation for ground handling tasks in airports using column generation[END_REF] considered that this problem is close to the vehicle routing problem with time windows. So they adopted a Column Generation technique associated with a Branch and Bound technique, resulting in a Branch and Pricing approach [START_REF] Desaulniers | Column Generation Spring-Verlag[END_REF].

Solution approach

Here the solution approach is based on the consideration of feasible paths, where a feasible path is a shift starting and ending at the manpower base. An integer master problem has been introduced to assign to each team a feasible path so that the total number of assigned tasks is maximized, but the synchronization between the tasks cannot be directly tackled. The selected objective is here to minimize the total number of unassigned tasks while assigning to each team feasible sequences of activities along paths. Such feasible paths are shifts starting and ending at location 0 and obeying at time windows and skill requirements constraints. They are defined by the sequence of tasks they visit.

When an optimal solution is not obtained (solution is not integer or task synchronization constraints are not met) a branching is performed according to the solution of a pricing problem. Here the pricing problem results in elementary shortest path problem with time windows for each team which are solved using a label setting algorithm.

Application to the management of cleaning manpower

Aircraft cleaning is essential in order to maintain the high quality standards of service delivered on-board aircraft by the airlines to the passengers. Depending of the way the aircraft is operated (long haul flights, fast connections for domestic/regional aircraft) the required service can either be tightly constrained by time slots or not and these time constraints can either be known with a large anticipation or not. In general cleaning (and toilet refurbishing) is performed once arriving passengers have left the aircraft and before departing passengers arrive. In general at the gate the ground personnel of the airline check that cleaning is completed before allowing passengers to board the aircraft. Depending on the parking position of aircraft (at gate or remote) ground vehicles are necessary to transport the cleaning teams to the aircraft.

[ [START_REF] Dohn | Optimizing manpower allocation for ground handling tasks in airports using column generation[END_REF] illustrated their approach to optimize manpower allocation for ground handling with the case of the aircraft cleaning manpower at an airport. To evaluate for that application the of effectiveness this approach, test data sets taken from real-life situations faced by airline cleaning companies in two European major airports have been used. The test data set has been organized in four different problem types and each type has been composed

of three problem instances covering 24-hour periods. From 10 teams and 100 tasks up to 20 teams with 300 tasks have been considered. The authors reported that the above exact solution approach has provided effective results for the smallest instances after computation times spanning from seconds to hours while time out or memory out situations have been obtained

with larger instances. Then this exact solution approach, which leads to numerical difficulties in the off-line situation, will not be of interest in the on-line context unless heuristic procedures are introduced to replace its exact search processes.

Decentralized Approaches of the Global Ground Handling

Assignment Problem

Multi-project scheduling approach

A representative work for this approach is the one of [START_REF] Mao | Agent-based scheduling for aircraft de-icing[END_REF] which proposed a solution to solve the airport ground handling scheduling problem under uncertainty by considering that the global ground handling scheduling problem is an instance of a multiproject scheduling problem (MPSP), so, they considered the aircraft as a project agent which is composed by a set of activities, and the ground handling providers as resource agents, each one is responsible of a resource which performed a specific type of activity. As a first step, they provided a formal description of this instance taking into account the uncertainty at the level of the execution time of the operations. The second step, and in order to cope with the uncertainty, they proposed an online multi-agent scheduling approach. In this approach, they presented an online schedule based on a cooperative scheme. It has been noted that this approach could only handles the uncertainty at the level of the release time and it was difficult to apply it in the case of the presence of disruption in the processing duration. That why, in the third step, in order to deal with the different kind of disruptions, they proposed to use the same structure (MPSP) to insert slack time between the activities. This slack time would guarantee, in case of the appearance of any incident that the resources still work as planned.

The first approach was applied in a deterministic environment, using 10 type of aircraft turnaround procedures, for each procedure there were 10 identical aircraft instance. The results obtained by the application of the two multi-agent scheduling approaches: noncooperative and cooperative, were been compared with 3 centralized heuristics methods: First Come, First Served (FCFS), Maximum Total Travel Work Content First and Shortest Activity from the Shortest Project. The results showed that for the five scheduling approaches the total project delay (turnaround time) decreases with the increase of the delay cost per time unit.

From computing time point of view, the Maximum Total Travel Work Content First and the Shortest Activity from Shortest Project heuristics methods had the shortest computing time.

Concerning the resource levelling measures, it has been observed that the multi-agent scheduling with the cooperative scheme used to carry out the ground handling processes the lowest resource levelling. So, according to the results, the cooperative online scheduling scheme was the one of the best centralized scheduling heuristics. For the second proposed approach, in order to calculate the adequate slack time to insert in the end of each activity, a genetic learning algorithm was employed. This approach was applied for dynamics problems (resources inefficiency). The results showed this approach was able to absorb the delays at the level of the executing time of activities, to converge to a stable situation and to avoid rescheduling the resources.

Distributed decision making approach

Following this approach, [START_REF] Garcia | Agent-based decision-making process in airport ground handling management[END_REF] considered the ground handling processes as a distributed decision support system. To deal with this problem, they created a new theoretical and experimental Multi-Agent System called MAS-DUO. The architecture of this new MAS was based on a combinations of many existing methodologies. The MAS-DUO is a division of the organization model in two platforms: system of information model and physical model.

Each platform was treated independently to better understand the system and to facilitate the design and the development of the MAS. This division allowed strategic policies to be reflected on the physical decisions and informed to the upper information system about physical distribution as well. The communication between the two platforms was assured by using of an interaction protocol based on sharing parameters of the Markov reward function.

This new organisation was tested to manage the ground handling operations on the Ciudad Real Central Airport. The ground handling operations taking into account corresponded to the set of operation performed on a Boeing B737 during a standard 45 minutes scale.

Analysis and conclusion

The considered applications of Operational Research to solve ground handling operations problems at the operations level, treat in general a nominal problem with no perturbation to the aircraft arrival schedule or to the operations of the different ground fleets.

Even in this nominal case, the corresponding mathematical programming problems are of hard complexity class with big difficulties to get exact solutions for real size problems. Then, some heuristics have been built to provide a solution to these nominal problems. In general heuristics of the greedy type can be adopted to cope with on line perturbations since they treat in sequence the different decisions to be taken. However few works report some experiments

where the heuristic applied to ground handling scheduling are assessed in perturbed environments.

With respect to the multi-agent approaches, they focuses mainly on the minimization of the costs supported by each ground handling agent which are considered at the same level than delays supported by passengers.

In the first class of studies an activity-based decentralized organization of ground handling is adopted implicitly but no coordination scheme is proposed. In the second class of studies, the intensity of information flows necessary to process market-based mechanisms or perform multi-agent based decision making is such that a centralized approach appears preferable.

Then it appears that the majority of these studies missed two cornerstones of the considered global ground handling operations problem:

The cost dimension, which has been considered in the previous chapter and where it is clear that the direct cost resulting from ground handling activities are secondary with respect to the economic consequences of delays at servicing arriving and departing aircraft.

The management dimension where an organization able to cope with routine situations as well as perturbed conditions or even disrupted situations, must be designed.

In reference to this last point, in the following chapter, the design of an efficient organization of ground handling management compatible with global approaches to cope with nominal, perturbed and disrupted situations at airports is developed.

CHAPTER 4

A GLOBAL ORGANIZATION OF GROUND HANDLING MANAGEMENT

Introduction

In this chapter the problem of the organization of ground handling management within an Airport -Collaborative Decision Making (A-CDM) environment is explored. First the main A-CDM principles are recalled and the level of interaction of ground handling information with the whole airport management through A-CDM is discussed. Since ground handling activities generate very large flows of differentiated information and according to the A-CDM milestone approach, a two level structure for the management of ground handling, where the upper level interacts directly with the other A-CDM partners, is investigated. Then the functions to be developed by a ground handling coordinator (GHC) at the first level and the specialized ground handling managers (GHMs) at the second level are discussed. Petri nets are introduced to represent and analyze the logical structure of these functions as well as the coordination processes adopted between them.

A-CDM and ground handling management

The A-CDM concept

The objective of the concept of A-CDM, initiated by the European Commission in 2008, is to enhance the overall efficiency of the European Air Transport System. This overall efficiency is considered achievable if the air and the ground segments of this system operate in harmony. Then, according to traffic estimates provided by the air traffic services (ATFM, ATM, ATC), airports operations should present a high degree of predictability. This is achieved by performing airport activities within accurate time tables.

The airport partners involved in the A-CDM are then: Air Traffic Control (ATC), aircraft operators (mainly airlines), ground handling management, air traffic network management and airport operations managers. Figure 4.1 displays all the A-CDM partners and the interaction between them. The concept of A-CDM is mainly based on the following general principles:

-Share at the right time of relevant data between the different partners.

-The quality of the exchanged data must contribute to the predictability of events and the planning capability of decision makers.

-Interface decisions are assigned to one of the involved partners.

-All partners are informed on-line of the adopted decisions.

The application of these principles should improve the effectiveness of decisions of each decision maker, where objectives and constraints of other decision makers are considered together with their actual and predicted situations.

These principles are the base of the main functions of the A-CDM which could be summarized in these four points:

-Milestone approach -Aircraft process execution assessment -Trend analysis of the pre-departure sequence -Aircraft process status

The Airport CDM is supported by an information sharing system composed of computer networks, databases and user interfaces. The structure and scope of this information sharing system depend on the organization of the airport and its stakeholders.

Operational principles of CDM

The operation of A-CDM is based on two main operational principles:

- -The adoption of a milestone approach which describes the progress of a flight from the initial planning to the take-off by defining significant events to be closely monitored. Block-off and take-off are among the most significant events. The adoption of this approach should enhance the time predictability of the following events for each flight.

To produce accurate and effective predictions about departing traffic, airport ATC should provide aircraft ground traffic information to all CDM partners:

-First, taxi-in and taxi-out delays are computed (variable taxi time) to improve the estimation of the bock-in and take-off times, increasing then the ground traffic predictability.

-Second a pre-departure sequencing providing the order in which aircraft are planned to depart from their stands (block-off, push back) is communicated to the other partners. This sequence must integrate constraints and objectives of the other partners to insure feasibility and improve slot adherence.

The adoption of these operational principles should enable the airport to cope as efficiently as possible either in normal situations (good weather conditions, no capacity limitation) or in adverse conditions.

Ground handling and A-CDM

As a result of the improved predictability of aircraft arrival times at parking stands, ground handling management can expect to achieve:

-An enhanced punctuality of ground handling operations.

-The agreement with required ground handling service levels.

-The minimization of ground handling operations costs.

The improved predictability should allow the ground handling managers to anticipate the necessary resources needed by an arriving aircraft and mobilize at the right time the right ground handling resources. Here, block-in information will be provided on the medium range by the air traffic network management and on the short run by the airport ATC tower, while the aircraft operator will inform about the specific ground handling services required by the arriving or departing aircraft.

However, the ground handling process presents some important specific characteristics within the airport operation:

-It is a process involving different resources (equipment and manpower) managed in general separately.

-The ground handling process may vary in composition according to the characteristics of its operation.

-The duration of the different ground handling tasks may vary even for the same type of aircraft according to its occupancy.

Then, the ground handling process is a potential generator of an enormous flow of information of which only a small part is relevant to the global objective of improving traffic fluidity and safety within the air transportation system. It does not appear convenient to communicate all this information to all airport partners (too much information kills information). In the next paragraph, according to an adopted overall organization of airport ground handling, milestones will be proposed for the following up of this activity.

Introducing an Airport Ground Handling Coordinator

When considering ground handling organization in different airports, it appears that this organization depends strongly on the size and the physical organization of the airside as well as on the volume and composition of traffic. Then, as shown in chapter 2, a large diversity of actual ground handling organizations is found in major and medium size airports.

Then it does not appear desirable to propose a general paradigm to organize airport ground handling since the resulting efficiency can be quite unequal from an airport to the next.

However, when some key characteristics are met, delimiting a specific class of ground handling situations, common organizing principles can be of interest.

Here some assumptions with respect to airport ground handling characteristics, which are frequently encountered in medium to large airports, are adopted. They are the following:

-Here is considered the case of airports in which ground handling is performed by a set of specialized operators working in parallel under the management of the airport authorities.

-The ground handling process is supposed to follow pre-established sequencings and to be performed at the parking stands.

-It is supposed that the parking stands are assigned to arriving flights by the airport and communicated through ATC, while the status of the parking stands is monitored by ATC which is in charge of driving the aircraft out of the parking position.

-It is also supposed that the arriving parking position is its departure parking position for the next flight. This last assumption introduces constraints on the ground handling activities.

From the considerations developed in the previous paragraph, it appears interesting to consider that the airport ground handling operators do not interact directly within the A-CDM framework, but through a ground handling coordinator (see figure 4.2).

This coordinator will interface the other airport partners with the ground handling operators:

-The coordinator will provide each ground handling operator of ground traffic predictions and required ground handling resources for each flight.

-The coordinator will provide the other airport partners with predictions of ground handling delays and milestones completion information.

In this situation, the GHC should directly exchange data with the following A-CDM partners:

-ATC/ATM: to get predicted times of arrival of aircraft at parking position. It is supposed that the choice of the parking position has been solved and informed through a direct exchange between ATC/ATM and the corresponding airline.

-Airlines: to get information about the effective ground handling needs of arriving/departing aircraft. The GHC will be able to provide to the airline a prediction of completion time of ground handling activities at aircraft arrival/departure. Then the airline will be able to communicate with ATC/ATM and negotiate departure time if necessary.

Ground handling milestones monitoring by GHC

The ground handling activities around an aircraft can be divided in two set of operation:

-The set of arrival ground handling operations, gh i A , which includes all the ground handling activities which must be performed to conclude properly the current -The set of departure ground handling operations, gh i D , which gathers the ground handling activities which must be performed to prepare the next commercial flight.

The main departure activities are passengers boarding, baggage loading, fuelling, catering. Stockholm airport and how those activities are divided in two sets.

To limit the flow of information sent to the other A-CDM partners, it appears that the information about the starting and end times (planned and effective) for arrival and departure

Ground Handling Coordination

In this approach, besides monitoring milestones for the benefit of the other A-CDM partners, the Ground Handling Coordinator (GHC) coordinates the different ground handling fleets which operate simultaneously at different places of the airport.

This central manager receives through the A-CDM updated information about predicted flight arrivals and flight departures and distributes this information to the different ground handling managers. These specialized ground handling managers provide him in return with effective start and completion times, so that he can produce completion milestones information (on-line estimations and finally effective values) to the A-CDM partners.

Observe here that the A-CDM approach can be of interest to organize the flows of information between the specialized ground handling managers and the ground handling coordinator, but also between them. This will lead to the concept of GH-CDM as a sub information network dedicated to improve ground handling efficiency (Figure 4.4).

In chapter 2 it was demonstrated that efficiency in ground handling activities is characterized mainly by the timeliness of the process (arrival or departure ground handling, arrival and departure for short turnovers) , while the costs resulting from ground handling investment (fixed and mobile equipment) and operations costs (staff, fuel) present a much lower importance. To achieve timeliness in an environment such as the airside of an airport characterized by important uncertainties inherent to air transportation, the ground handling process should be able in some circumstances to speed up, perform the whole arriving and/or departure ground handling in minimum time, according to some critical path technique [Clarke and al, 2004],

and then recover some of the initial delay. Critical path techniques assume implicitly that the necessary resources to perform the different activities (either on the critical path or not) are on the spot ready to be used. Then, the search for an efficient ground handling supposes the availability of the corresponding resources (equipment and staff).

Here it is proposed that the ground handling coordinator is in charge of the global planning of ground handling resources while ground handling operations are performed in a decentralized way by each specialized ground handling manager or GHFM (ground handling fleet manager) according to this resource requirement by the GHC. It appears of interest to perform globally the estimation of ground handling resources since in this way, synchronization between different ground handling activities is directly taken into account in the computation and the adopted resources margins follows a single approach. The presence of these planned margins for the ground handling resources will prevent from delay propagation over long periods of time. These ground handling resources should be computed once the schedule of arrivals and departures is available for the next day.

Also, when a major disruption occurs at the airport with needs for fast recovery towards regular operation, temporary capacity problems may appear as the result of an unexpected out of proportions increased level of demand, including for ground handling processing. In that case it is expected that the ground handling coordinator will take over ground handling activities by enforcing priorities decided at the A-CDM level.

Global planning of ground handling resources

The planning of ground handling resources should be performed at start for a whole day of operation by considering as basic input information:

-the time schedule of arriving and departure flight, -the operational characteristics of these flights. This information will be provided respectively by the airport authorities and the airlines. Also a pre-assignment of aircraft to the different parking areas of the airport is supposed to be available. This pre-assignment can be produced periodically by the airport authorities in agreement with the involved airlines.

When large air traffic perturbations happen, the ground handling coordinator will decide to update the planning of ground handling resources by considering the predicted demand for ground handling services during a shorter period of time. This shorter planning period will be taken long enough to allow the return to nominal conditions.

This approach can be extended to the management of major disruptions by taking into account explicitly, as initial constraints, the current ground handling situation.

The solution of the global ground handling planning problem will allow him to perform a prediction of the necessary amount of ground handling resources (vehicles and work force) need at each time period. This prediction will be achieved in three steps:

-At the first step, a global ground handling assignment (GGHA) problem is solved for a nominal schedule of flights.

Here the objective is to minimize the sum of the delays for the completion milestones of the ground handling of each flight. This problem will be considered in detail in the next chapter and a fast heuristic solution will be proposed. This solution will produce with respect to each ground handling operator a set of nominal feasible routes from one aircraft to the next so that each foreseen ground handling task will be covered by a vehicle from the corresponding fleet at the right time. This information can be forwarded to some ground handling fleet in some circumstances, but in general it will have a lack of robustness with respect to perturbations and may soon turn unfeasible.

-At the second step, totalization of necessary resources is performed.

It is considered that the whole operating period is composed of discrete time periods. A unit time period equal to the maximum between 5 min and the smallest duration of a ground handling operation, including travel times between parking stands and depot, can be adopted.

Then considering the feasible routes produced by the solution of the GGHA problem during a given period for a specific ground handling fleet, summing provides the nominal estimation of the necessary resources of this type during that period of time.

90

-At the third step, margins are added to the estimation of necessary resources.

Here, to the previous estimation, margins are added to improve the availability of ground handling resources in front of perturbations. There is no exact method to compute these margins to provide some probability of success since the distribution and composition of perturbations is not in general characterized in probabilistic grounds. However some basic principles can be considered. Need for extra resources are the result of unexpected peaks of demand. Since in general no anticipation is allowed in normal operations conditions, this peak of demand for ground handling services at a given period can only be created by the accumulation of delays (either arrival or departure delays) in the near precedent time periods.

Based on available delay statistics for arrivals and departures the formulation of a stochastic global ground handling assignment problem, where the objective would be to minimize the mean value of total delays resulting from ground handling while limiting the size of the involved ground handling teams at each time period, will be extremely complex.

A possible deterministic way could be to modify the nominal schedule before a given time t k by introducing delays just before this time, for example a 20 minutes delay at arrival or departure for aircraft scheduled to arrive or to depart within the previous half an hour. Then the global assignment problem will be solved with this modified schedule leading to an estimation of necessary resources at time t k .

This process should be repeated all over the different time periods composing a day (24  12=288 times). This approach is too cumbersome, even if, as it will be decided in chapter V, the global ground handling assignment problem will be solved using a greedy heuristic.

Then a simpler approach than the above approach can be to consider at a given time the resources necessary to meet the nominal arrival and departure schedule and, considering the nominal traffic during the previous half, add accordingly some margin. A simple rule could be such as:

For arrival ground handling activities: p is the probability that an arrival scheduled within half an hour before period k is delayed and should be processed at period k.

k i k A k i k i A p n r  
For departure ground handling activities: p is the probability that a departure scheduled within half an hour before period k is delayed and should be processed at period k.

k i k D k i k i D p n r  
For arrival and departure ground handling activities:

k i k D k i k A k i k i D p A p n r    (4.7)
where:

k i n is the nominal number of teams (vehicle and staff) of type i necessary at period k to process arrival and departures.

-

k i
r is the computed required number of teams of type i necessary at period kto process arrivals and departures, included reserve.

Observe that the computation of these ground handling resources does not include the spare vehicle stock which should be dimensioned, according to statistics, by the ground handling manager, to guarantee a given reliability level. The ground handling coordinator will choose the values of probabilities k A p and k D p according to the availability level he targets and according to other factors such as weather and season.

In the Figure 4.5, a simple description of how the planning of a safe level for ground handling resources for each ground handling manager is presented.

Decentralized ground handling management

Decentralized ground handling management works at two complementary levels: the local level and the coordination level.

Local ground handling management

Each ground handling manager GHM i , i=1 to T, where T is the total number of ground handling activities, has to manage fleets of vehicle and people to make them available once they are necessary to perform the ground handling activities they are in charge.

Then to make that possible at lower costs (investment, operational costs), each ground handling manager has to manage different background activities. Some of these background activities are planning activities performed on the long-medium run and related with fleet and

A k-1 A k n k-1 n k Figure 4
.5 : Planning of a safe level for ground handling resources manpower dimensioning and acquisition/recruiting. Other background activities, performed on the medium run, insure fleet maintenance and acquisition of supplies necessary for the ground handling activity (chemicals, water, industrial food, etc) as well as vehicle fuelling.

Considering that air transportation at an airport is not present during a week an overall periodicity, to achieve its ground handling mission, a GHM i has to solve on a daily basis the assignment of his resources to the ground handling tasks which are affected in a temporal basis to him by the ground handling coordinator. Instead of solving an integral assignment of manpower individuals and specific vehicles, this problem is split into two assignment subproblems.

At the upper level a pairing problem is considered by the GHM i where the objective is to assign the available ground handling units ( k i GHU ) to ground handling tasks of type i with the objective to minimize ground handling service delays while minimizing direct operations costs. These ground handling units or teams, are in general composed of an equipped and supplied vehicle and a team of operators. These direct operations costs are related to the intensity of use of ground handling units and to the total distance travelled by the corresponding ground handling vehicle. This problem will be referred as the ground handling fleet assignment (GHFAi, i=1 to T) in the next chapter.

At the lower level, ground handling units are built up from the stock of working vehicles and available manpower. A ground handling unit can be in the following states:

-deactivated: either the equipment is not ready (under repair or maintenance) or the operators are not available, -waiting for assignment: the unit is enabled but has not been assigned to flights, -assigned: the unit has been assigned to one or more flights, but the realization of the activity on the first of these flights is planned far in the time horizon, -made ready to perform its next activity: this happens when the planned time to perform a ground handling activity is near. This corresponds either to the time necessary to adapt the resource to the flight to be served or to a minimum time delay to inform the operators of the next operation, -operating: the unit is performing the activity (transfer operations and processing at aircraft or terminal).

With respect to manpower, once the pairing problem has been solved, individual assignment can be performed in two steps:

-The first step is performed on a time basis, where to each particular employee is assigned, or not, an activity period. During this period the employee is either working effectively within a ground handling team at ground handling tasks or he is ready to start a new task. Then, personalized ground handling teams are built up.

-In the second step, these personalized ground handling teams are assigned to the ground handling tasks through the solution of the pairing problem.

At both steps, regulations with respect to working conditions must be met. One of the main objectives of these regulations is to enforce safe working conditions to avoid accidents.

In this thesis only the pairing problem will be considered explicitly since from the efficiency of its solution will depend directly the performance of the airport while the constitution of the ground handling units should remain transparent to the A-CDM partners.

Coordination level of ground handling management

To be at least feasible, a decentralized approach, nominal or on-line, must be coordinated in some way since each ground handling tasks must be solved according to a sequence compatible with the need of ground handling activities for a particular arriving or departing aircraft.

In the nominal case where aircraft arrive at and leave from the parking stands on schedule, situation which happens scarcely, the planned sequence of activities at the parking stand could be adopted to solve successively and in parallel the different GHFA i problems, the solutions of the upstream GHFA i problems providing earliest starting time constraints for the downstream GHFA i problems. However, any perturbation will impair the efficiency of the whole ground handling performance.

In general aircraft at arrival use to be either in advance, on time or delayed depending on traffic and wind conditions. Here, to cover all these situations, it will be supposed that ground handling resources assigned to an arriving aircraft should be ready to start operation from their respective base with some antecedence with respect to scheduled arrival time at the gate.

Depending if the flight is a short, medium or long haul, this anticipation will be smaller or larger. In the case of departing aircraft in commercial operation, in general there will be no

GHM j GHM i GHC GHU ii' GHU ij' GHU ji' GHU ji'
anticipated departure, so the effective departure schedule with eventually some delay, will be the basis for ground handling operations at aircraft departure.

The central manager which receives through the A-CDM updated information about predicted flight arrivals and flight departures will be able to provide on-line to the different ground handling managers the start time information associated with each upcoming flight.

Petri Net representation of proposed ground handling organization and operation

One aim of this part is to develop a model of the proposed ground handling organization in order to investigate its sensitivity to the occurrence of different types of disruptions as: changes of available resources (aircraft stands-gates, equipment, personnel, etc.), aircraft arrival delays, as well as different gate assignment strategies. Considering the concurrence, precedence constraints and synchronization aspects of ground handling activities, Petri nets appear to be of interest to model this situation since Petri Nets are known to be a powerful tool to model and simulate discrete systems involving all the aspects of the ground handling process. Also, since time plays an important role in the performance of ground handling systems, Timed Petri Nets appear of special interest here.

The ground handling organization can be modeled by considering the three operation and management levels as shown in figure 4.6:

1-Ground handling units 2-Ground handling manager 3-Ground handling coordinator

Ground handling units

The Ground handling units belonging to a specialized ground handling provider have to communicate with other agents which are a part of the ground handling system:

-It has to be able to communicate with its ground handling manager to provide him the state of the processing of the task (start time, completion time, on time, occurrence of any disruption, equipment failure).

-It will also receive from its ground handling manager new assignments at other parking positions or passenger or luggage stations in the airport.

-It has to alert the waiting ground handling units of the completion of its task at the aircraft.

The following RdP ( Figure 4.7) represents the different operational states of the GHUs with the information which is exchanged during the processing of their ground handling task. Here the interpreted places and transitions are as follows :

-P0: the GHM i assigns the ground handling unit j (GHU j ) to perform the ground handling taski at location k, or task i-k.

-P1: the GHU j is assigned to perform a ground handling task i-k and is ready to start it.

-P6'up: is a data sent by the GHU j , which performs the upstream ground handling tasks at the same station, to the GHU j representing the following state: the upstream ground handling tasks to i-k have been already completed on time, according to the scheduled completion time, by the GHUs in charge of them.

-P9'up: is a data sent by the GHU j , which performs the upstream ground handling tasks at the same station, to the GHU j representing the following state: the upstream ground handling tasks to i-k have been already completed on time with a delay according to the scheduled completion , by the GHUs in charge of them.

-P2: the GHU j starts to perform the ground handling task i-k.

-P3': is a data sent by the GHU j to his GHM i representing the following state: the GHU j starts to perform the ground handling task i-k with a delay according to the scheduled start time.

-P4': is a data sent by the GHU j to his GHM i representing the following state: the GHU j starts to perform the ground handling task i-k on time according to the scheduled start time.

-P5: an incident has happened during the execution of the ground handling task i-k; it results in a delay for its completion time.

-P6': is a data sent by the GHU j to his GHM i representing the following state: the GHU j has completed on time the ground handling task i-k (according to the scheduled completion time).

-P9': is a data sent by the GHU j to his GHM i representing the following state: the GHU j has completed with a delay the ground handling task i-k.

-P7: the GHU j equipment is in a failed state and the GHU j operators are unable to complete the ground handling task i-k, it has to be replaced by another one.

-P8: a new equipment is ready to replace the failed one and to perform until completion the ground handling task i-k.

-P10: the GHU j has already finished performing the ground handling task i-k and he is available to be assigned to perform another ground handling task.

-P7': is a data sent by the GHU j to his GHM i representing the state P7.

-P6'down: is a data sent by the GHU j to the GHUjwhich perform the downstream ground handling tasks at the same station representing the following state: the GHU j has completed on time the ground handling task i-k (according to the scheduled completion time).

-P9'down: is a data sent by the GHU j to the GHU j which perform the downstream ground handling tasks at the same station representing the following state: the GH Uj has completed with delay the ground handling task i-k.

-T0: this transition allows the GHU j to pass from the state available to assigned to perform the ground handling task i-k due to the decision made by the GHM i .

-T1: this transition allows the GHU j to start performingthe ground handling task i-k since they are ready and the upstream ground handling tasks are completed with a delay according to the scheduled start time.

-T2: this transition allows the GHU j to start performing the ground handling task i-k since they are ready and the upstream ground handling tasks are completed on time delay according to the scheduled start time.

-T3: it is a timed transition, the time represent the end of the task. The completion time of the ground handling task, in this case, is represented by an interval in which it was considered the earliest completion time and the latest completion time.

-T4 : if the GHU j has not finished the ground handling task yet ( T3 has not been fired) , in this case, the GHU j is not on time , and a delay appears at the level of this task -T5 : it represents the end of performing the ground handling task after the occurrence of the delay 99 -T6: it represents the event that the delay is caused by the failure of the GHU j equipment.

-T7: the failure GHU j equipment has been replaced by the reserved one and the GHU j can continue to perform the ground handling task.

The places P0, P3', P4', P6', P9' , P8 and P7' represent a communication interface between the GHU j and his GHM i .

The places P6'up and P9'up represent a communication interface between the GHU j and the upstream GHUjwhich perform the upstream ground handling tasks at the same station.

The places P6'down and P9'down represent a communication interface between the downstream GHUjwhich perform the downstream ground handling tasks at the same station and the GHU j .

The places P1, P2, P5, P7 and P10 are the different states of GHU j during the processing of the ground handling task, that is why they have been sent to the GHM i to have an overview of what happens for each GHU j.

Ground handling manager

The ground handling manager must have a detailed view of what happens at the level of each of his ground handling units. Also, he has to communicate data to the ground handling coordinator.

The following RdP (Figure 4.8) represents the different operational states of the GHUs with the information flow sent to the GHM i during the processing of their ground handling task and how the GHM i uses it to assign each GHU to each ground handling task. It represents also how the GHM intervenes in case of a GHU's equipment failure.

Here the interpreted places and transitions are as follows :

the places P0, P3', P4', P6', P9' , P8 and P7' represent, as mentionned before, a communication interface between the GHU j and his GHM i .

P3', P4', P6', P7' and P9' are the image of what happens realy during the processing of the ground handling tasks. The GHMi takes into account these states to assign each GHUi to each ground handling task.

T7i: if a GHUi equipment is in failure and the GHMi has spare equipment, in this case this transition can be fired.

Ground handling coordinator

The ground handling coordinator must have a global and detailed view of what happens at the level of each of his ground handling manager. Also, he has to communicate data to the A-CDM. The following RdP (Figure 4.9) represents the communication between the GHC and the GHMs on one side and the other partners of A-CDM on the other side. The data sent to the GHC by the GHMi:

-P3': is a data sent by the GHU j to his GHM i representing the following state: the GHU j starts to perform the ground handling task i-k with a delay according to the scheduled start time.

-P4': is a data sent by the GHU j to his GHM i representing the following state: the GHU j starts to perform the ground handling task i-k on time according to the scheduled start time.

102

-P6': is a data sent by the GHU j to his GHM i representing the following state: the GHU j has completed on time the ground handling task i-k (according to the scheduled completion time).

-P9': is a data sent by the GHU j to his GHM i representing the following state: the GHU j has completed with a delay the ground handling task i-k (according to the scheduled completion time).

Conclusion

In this chapter it has been shown that adopting a hierarchical approach, it is possible to organize ground handling management in accordance with the A-CDM approach where a ground handling coordinator operates as an active interface between the air transportation operators (airport authorities, ATC and airlines) and the specialized ground handling managers in charge of the ground handling units. In this organization the ground handling coordinator generates to the other A-CDM partners the milestones associated with ground handling and provide to each ground handling managers safe values for the ground handling resources necessary to face not only nominal situations as well as perturbed ones. According to this approach, either the ground handling coordinator as each specialized ground handling manager faces decision problems. In the next chapter, the solution of these decision problems will be considered through the consideration of the corresponding optimization problems.

103

CHAPTER 5 DECISION MAKING PROCESSES FOR THE PROPOSED GLOBAL APPROACH

Introduction

In this chapter the main decision making processes in charge of the managerial units composing the proposed ground handling management organization in the previous chapter, are considered. The adopted approach is here to formulate a corresponding optimization problem, to propose eventually an exact solution approach and check its practical feasibility and then to propose a possible heuristic approach.

The objectives adopted for these optimization problems concentrate on the respect of global or local time deadlines with some consideration for the corresponding operating costs, according to the analysis performed in chapter II. The constraints introduced in the respective formulations insure that the resulting solutions are physically feasible when considering the involved discrete resources and the spatial and temporal dimensions of these problems.

The generated optimization problems are at least partially combinatory, this implies in general long processing times. Then, the heuristics approaches are of particular interest since it is of utmost importance to be able to get practically online updated feasible solutions when perturbations occur.

In this study it is considered that every time an aircraft operating a flight directed towards a given airport takes-off, that airport is informed of its departure as well as its predicted landing time. The predicted landing times can be updated during the flight.

The Central Planner Problem

The first decision problem considered here is relative to the sizing of resources performed by the ground handling coordinator (GHC) to be sure that during daily operations, the different ground handling managers (GHMs) will have the necessary resources in equipment, vehicle and people to cope with nominal operations as well as perturbed situations. This problem, which tackles globally the different ground handling activities, is supposed to be solved independently by the GHC. Considering the difficulties pointed out in the previous chapter to solve in some optimal way this problem which has also some stochastic characteristics, it has been proposed to solve it in two steps: while in a first step an overall nominal assignment problem is solved, in a second step, capacity margins are added to its solution.

Assumptions:

- -Each ground handling unit can only perform one task at one time.

Adopted notations

Let us define the considered variables and parameters:

-K :the set of aircraft involved in ground handling activities during the considered time period ( K is their number).

-F N : the number of different service fleets involved in ground handling.

-i n ,   F N i ,..., 2 , 1  : the amount of available vehicles of type i . -i m ,   F N i ,...,



( tot h is their total number).

ih j

 : task duration, the time delay it takes to perform task j on aircraft type h using vehicle type i . k T :departure date of the aircraft k from parking stand scheduled at The tasks to load and unload luggage are supposed here to be performed by the same type of vehicle. Then for routes with vehicle type 1:

- 1 0 1 '  l jkk Z
if the route l type 1carries out the task j on aircraft k after covering unloading luggage task on aircraft ' k and 0 otherwise.

-

1 1 1 '  l jkk Z
if the vehicle number type l performs the task j on the plane k after completing loading luggage onto aircraft ' k and 0 otherwise.

Tentative problem formulation

The above assumptions led to the formulation of a nominal overall optimization problem. Here the adopted objective function considers the minimization of a convex mix of the sum of the aircraft departure delays and of the total distance traveled by ground handling vehicles:

               F i N i n l l i K k D k k L d T 1 1 1 1 min   (5.1) where 1 0 1       
Constraints (5.2) and ( 5.3), shown below verify that each ground handling task is assigned to a single route.

       1 1 1 1 0 ' 1 ' 1 n l r K k lr jkk k Z 2 , 1  j ; K k   (5.2)      i i k n l K k il kk Z 1 ' ' 1 1 5 , 4 , 3 , 2  i ; K k  
(5.3) Constraints (5.4) and (5.5) are route continuity constraints: each vehicle after executing the task assigned to it is supposed to leave the parking stand.

         1 0 ' ' 1 ' ' 1 0 ' 1 ' 1 1 r K k lr k jk r K k lr jkk k k Z Z   1 ,..., 2 , 1 n l  ; 2 , 1  j ; K k   (5.4)      i k i k K k il k jk K k il jkk Z Z ' ' ' ' ' '   i n l ,..., 2 , 1  ; 5 , 4 , 3 , 2  i ; K k   (5.5)
The set of inequalities presented below describes the precedence constraints of operations and the availability dates of service vehicles. Indeed, for the constraint (5.6), the first inequality guarantees that a given task performed by a specific vehicle on a given aircraft cannot start before the previous task carried out by this same vehicle has completely been performed on a previous aircraft and the vehicle has travelled between the two parking stands and the second inequality, specifies that a task following another one cannot start before the end of this previous task (in this case, it is the arrival of the aircraft to the parking stand).

     K k Z C d C Z r r C C n l lr k r S k A k k n l lr kk r K k S S S S k r k r k k k k k k k                                1 1 1 ' ' 1 1 0 1 1 0 1 1 1 1 1 1 1 ' 1 1 0 ' 1 1 1 ' 1 1 1 . 2 1 . . 1  (5.6)
In this case, it is imposed that

1 1 0 1 0 1 0 1 l k l k Z Z  .
The operation of disembarking passengers does not require the intervention of a service vehicle and can be carried out after the arrival of the aircraft k to the parking area, so the only constraints to be considered are:

A k k d C  6 1 K k  
(5.7)

109

The constraints related to the remaining operations are established similarly.

For the sanitation process, we get:

  K k Z C d C Z C C n l l k S k A k k n l K k l kk S S k k k k k k k                       3 3 3 ' 1 3 0 1 3 3 1 3 1 1 ' 3 ' 1 3 1 ' 3 1 3 1 . .  (5.8)
Regarding the cleaning operation, we have:

k k k C C 6 1 6 1 6 2    K k  
(5.9)

For the catering operation, constraints are written as:

  K k Z C C C Z C C n l l k S k k k k n l K k l kk S S k k k k k k k                        2 2 2 ' 1 2 0 1 2 2 1 6 1 6 1 2 1 1 ' 2 ' 1 2 1 ' 2 1 2 1 . .   (5.10)
As for the water process, constraints are:

  K k Z C C C Z C C n l l k S k k k k n l K k l kk S S k k k k k k k                        4 4 4 ' 1 4 0 1 4 4 1 3 1 3 1 4 1 1 ' 4 ' 1 4 1 ' 4 1 4 1 . .   (5.11)
With respect to refueling, the constraints are written as:

k k k C C 1 1 1 1 6 3    K k  
(5.12)

Then, for loading baggage:

     K k Z C C C Z r r C C n l lr k r S k k k k n l lr kk r K k S S S S k r k r k k k k k k k                                 1 1 1 ' ' 1 1 0 2 1 0 1 1 2 6 3 6 3 1 2 1 1 ' 2 1 0 ' 1 1 1 ' 1 1 2 . 2 1 . . 1   (5.13)
Here, also it was supposed that:

1 1 0 2 0 1 0 2 l k l k Z Z  Chapter 5 Decision Making Processes for the Proposed Global Approach 110 K k C C C C k k k k k k            2 1 2 1 6 4 6 2 6 2 6 4   (5.14)
and for the push back operation, we write:

  K k Z C C C C C C C Z C C n l l k S k k k k k k k k k k n l K k l kk S S k k k k k k k                                5 4 4 ' 1 5 0 1 5 5 1 4 1 4 1 5 1 6 4 6 4 5 1 1 2 1 2 5 1 1 ' 5 ' 1 5 1 ' 5 1 5 1 .     (5.15)
The departure of aircraft k from its parking stand can only be started after the completion of the push back operation (inequality (5.16)) and it is not performed before the planned departure time (inequality (5.17)).

k k k C T 5 1 5 1    K k   (5.16) D k k d T  K k  
(5.17)

At beginning and ending of operations for vehicle type 1, we have the constraints:

       K k r j lr jk Z 1 0 2 1 1 0 1   1 ,..., 2 , 1 n l   (5.18)        K k r j lr k j Z 1 0 2 1 1 0 1   1 ,..., 2 , 1 n l   (5.19)
For vehicles types 2, 3, 4 and 5 these constraints are written:

1 0    i k K k il jk Z   i n l ,..., 2 , 1   ;   5 , 4 , 3 , 2  i (5.20) 1 0    i k K k il k j Z   i n l ,..., 2 , 1   ;   5 , 4 , 3 , 2  i (5.21)
The travelled distances by service vehicles are given by:

     1 2 1 1 0 1 1 0 ' 1 0 1 ' 1 1 ' 1 2 1 1 0 1 1 0 1 . . 2 1 . . 1 . 2 1 ' V Z Z r r Z L K k j r S lr k j K k K k r lr kk S S S S K k j r S lr jk l k k k k k k                                                1 ,..., 2 , 1 n l   (5.22)   i K k il k i S K k K k il kk i S i S K k il k i S l i V Z Z Z L k k k k . . . 10 ' ' 1 ' 0 1                               i n l ,..., 2 , 1     5 , 4 , 3 , 2  i
(5.23)

Analysis and solution process

The optimization problem developed above is a mixed integer problem. Variables * * Z are -the number of linear equality constraints: (

Boolean decision variables and variables

 K n n n n i i i i . 2 6 2 2 5 2 1 5 2 1        
).

Note that each nonlinear inequality constraint:

     n i m j j i y x z 1 1   1 , 0  i x ,   j j Y y , 0  ,   R z (5.24)
Where j Y is an upper bound of j y , is equivalent to:

j i y x z  , 1 n i   , 1 m j     1 , 0  i x ,   j j Y y , 0  ,   R z For all   1 , 0  i x ,   i i Y y , 0  and   R z
, where

j i y x z . 
if, and only if the constraints below are satisfied:

                             m j n i z m j n i x Y y z m j n i y z n i x z i j j j i 1 , 1 0 1 , 1 1 . 1 , 1 1 (5.25)
the nonlinear inequality constraints (5.24) can be replaced only by the 3 th linear inequality of the system (5.25) [Billonnet, 2007].

Then the whole optimization problem becomes a mixed integer linear problem which can theoretically be solved using techniques such as the Branch-and -Bound algorithm [START_REF] Land | An automatic method of solving discrete programming problems[END_REF].Clearly, this approach even for small instances of the problem (e.g. 10  K aircraft), it leads to a significant computation time when searching for the exact solution, for example using a solver such as LP-Solve or CPLEX.

Numerical application

For example, a case with 5 aircraft involved in 10 flights with 3 different ground handling operators performing 4 different ground handling activities, has been considered numerically.

In this case, the objective function to minimize reduced to the sum of the delays which are generated by the assignments of the ground handling units to the ground handling tasks.

In figure 5.1 is represented the structure and duration assumed for the ground handling activities. Then table 5.2 provides the nominal arrival and departure schedules as well as the assigned parking positions. This problem has been solved using the library LP-Solve which has been run on a personal computer. An exact assignment of the ground handling units to the ground handling tasks has been computed. The sum of the delays at departure for the aircraft according to this solution is equal to 138 minutes which tends to indicate that ground handling resources were in this case insufficient to tackle efficiently the nominal arrival/departure schedule.

The solution for this very small problem was obtained after 1.37 minutes of computation.

When considering slightly larger instances of this problem, the computation time increases very sharply to excessive values (tens of minutes and soon, hours of computation). Then this exact solution approach does not look suitable to treat real size assignment problems (with for instance no less than 7736625 variables and 46996 constraints for an instance involving 690 flights. It is expected that this situation will remain even if specialized versions of the resolution software were developed or if a faster computer was employed. This constitutes a strong limitation for this approach.

So it appears of interest to consider the development of a heuristic approach which can be able to produce feasible solutions in a very short computation time. This will allow the manager, here the GHC, to restart the solution of this problem when the current operational conditions become rather different from the predicted ones.

The proposed GHC heuristic

Let us consider during a period of operations, with a set K of arriving and departing aircraft to/from the stands. Here we develop a greedy centralized heuristic which will ensure the feasibility of all ground handling operations. The idea of the centralized heuristic is to rank arriving and departing aircraft according to their planned start time of the corresponding ground operations (either arrival ground handling tasks or departure grand handling tasks).

Then the central planner will process in this order each aircraft ground handling activity by linking each task to a route to build a ground handling duty:

-To cover task j at aircraft k it will search between the already created routes of type j , which one can cope with it, within the planned interval and at lower transportation cost.

-If none of the existing route provides a feasible solution 1. and there are remaining capacity of type j at the corresponding base, a new route of type j starting at this base is created with first stop at aircraft k.

2. and there are no remaining transport capacity at base of type j, add this task at the route of type j which minimizes the mix of resulting delay for aircraft k and of distance travelled to reach it with the weight .

Then repeat with all the expected ground handling tasks j at an arriving or departing aircraft.

This will produce feasible sets of duties (routes) to be performed by the different ground handling fleets and workforce. Then this data will be used by the ground handling coordinator to compute, according to the process proposed in the previous chapter, the level of resources that each ground handling manager must provide at each time period. These resources will be afterwards either effectively used to process aircraft and passengers or will remain as a warm reserve to face perturbations and incidents.

Decentralized fleet management

Classes of fleet management problems

The fleet management problems considered here correspond to the pairing problems that have to be solved by the ground handling managers between planned demand of specialized ground handling services and the corresponding available ground handling resources. Taking into account that some service providers must perform two different tasks, it appears necessary to separate ground provider fleet services into two categories: the first, 1 C , includes the providers who perform two different and non-consecutive tasks as: the service providers who take care of both the loading and unloading luggage, and the service providers who take care of both the boarding and de-boarding of passengers. The second category, 2 C , gathers the providers who carry a single type of task either on an arriving or departing aircraft.

Adopted notations

The formulations of the considered to classes of fleet management problems adopt the following notations:

Each task of the turnaround process I the set of aircraft that will require service in the near future;

t t t k f k p k I I I  
Each service provider operates a fleet of homogeneous vehicles; Each task t has a non-preemptive processing duration t S ; j i D , is the distance to drive from an aircraft parking stand i and to an aircraft parking stand j;  t T is the set of task that will be performed on the aircraft once the agent t k completes the execution of its task t;  t T is the set of task that were performed on the aircraft before the task that will be carried out by the agent t k ;

  t k X x ,..., 1  t x j i a , , equal 1 if vehicle x ,   t k X x ,..., 1  which performed the task t ,   T t ,..., 1  serves aircraft j ,   t k I j ,..., 1  , immediately after serving aircraft i ,   t k I i ,..., 1  Each aircraft i ,

Formulation of the GHFAS problem (C1 case)

The optimization objective is a mix of the sum of generated delay at the unloading stages and at the loading stages with the total travelled distance by the corresponding fleet.

(5.26) where under the following constraints including the assignment covering constraints:

       1 0 , , , 1 r X x I i r t x j i t k p a kt f I j   , 1 T t   (5.27)        1 0 , , , 1 r I i I j r t x j i t k p t k f a kt X x   , 1 T t   (5.28)          1 0 , , , 1 0 , , , r I
i r t x j i r I i r t x j i t k f t k p a a kt f I j   , kt X x   , 1 T t   (5.29)   1 , 0 , , ,  r t x j i a kt p I i   , kt f I j   , kt X x   , 1 T t   ,   1 , 0  r (5.30) A j t j d b  kt f I j   , 1 T t   (5.31)   r t x j i x j k k i r t i t i x j i r t i t i t j a V D D S b r V D S b r b t t , , , , , , , , ' 1 
                               kt f I j   , kt X x   ,   1 , 0  r , 1 T t   (5.32) 0 , 0 , t j t t j S b f j   kt f I j   , 1 T t   (5.33)       T t t j D j t j t S d S b j ' ' 0 , kt f I j   , 1 T t   (5.34) 1 , 0 , 0 2 1 2 1                                                     X x I i I j r r t x j i j k k i j i T t t j D j t j T t t j D j t j t k p t k f t t a D D r D r S d f S d f 1 0 , , , , , , 2 1 '
' 2 ' ' 1 1 . 1 ' min     T S b b t j t j t j     0 , ' kt f I j   , 1 T t   (5.35)   r t x j i x j k k i r t i t i x j i r t i t i t j a V D D S b r V D S b r b t t , , , , , , , , ' 1 '
                                kt f I j   , kt X x   , 1 T t   ,   1 , 0  r (5.36)       T t t j D j t j t S d S b j ' ' 1 , ' kt f I j   , 1 T t   (5.37) 1 , 1 , ' t j t t j S b f j   kt f I j   , 1 T t   (5.38) j t j E b  ' kt f I j  
(5.39)

Here the decision variables are relative to the assignment of vehicles to aircraft (Boolean) and the scheduled start time of each elementary ground handling task (real).

Formulation of the GHFAS problem (C2 case)

For each single task ground handling fleet we get the following formulation of the GHFAS problem:

(5.40)

where  is a positive parameter and with the following constraints:

     X x I i t x j i t k p a 1 , , kt f I j   , 2 T t   (5.41)      t k p t k f I i I j t x j i a 1 , , kt X x   , 2 T t   (5.42)      t k f t k p I k t x k j I i t x j i a a , , , , kt f I j   , kt X x   , 2 T t   (5.43)   1 , 0 , ,  t x j i a kt p I i   , kt f I j   , kt X x   , 2 T t   (5.44) A j t j d b  kt f I j  
(5.45)

t x j i x j i t i t i t j a V D S b b , , ,            kt f I j   , kt X x   , 2 T t   (5.46) t j t t j S b f j   kt f I j   , 2 T t   (5.47)                     X x I i I j t x j i j i T t t j D j t j t k p t k f a D S d f , , , ' ' 1 min         T t t j D j t j t S d S b j ' ' kt f I j   , 2 T t  
(5.48)

The equation (5.27) and (5.41) ensure all aircraft receive service. Equations (5.28) and (5.42) impose that all the vehicles can begin and end their service tour at any position. Equation (5.29) and (5.43) are flow conservation constraints: a vehicle arriving at an aircraft must leave that aircraft later. Equations (5.30) and (5.44) ensure each possible task is either assigned or not. The inequality (5.32), (5.36) and (5.46) provide earliest start time constraints for the service at a ready aircraft taking into account the travelling time between aircraft. The inequality (5.31), (5.39), (5.45)specify that a task following another one cannot start before the end of this previous task (precedence constraints). The inequality (5.34), (5.37) and (5.48) define the latest start time for each service taking into account the activities that would be performed after. The equations (5.33), (5.38) and (5.47) represent the ending time of each task considering the starting time which has been already computed and the task duration.

On line Ground Handling Fleet Assignment (GHFA) problem at the level of each GHM

Ground Handling Fleet Coordination

To perform the ground handling activities for each aircraft within the allocated time, these different ground handling fleet services have to coordinate between each other while respecting the constraints of scheduling tasks for each aircraft and the constraints related to the use of ground handling unit: equipment, manpower, vehicle, etc according to the he organization presented in the Chapter 4.

Proposed heuristics for on-line GHFA

In a nominal situation, the ground handler fleet managers will assign a vehicle and a work team to each route. This vehicle may be changed by another to pursue the duty in accordance with operational considerations (refueling need, mechanical failure, etc) while work teams will be shifted according to labor and safety regulations. Here it is supposed that there are enough spare vehicles and work teams to meet operational perturbations:

When an arriving aircraft is delayed while his predicted arrival time is available, the ground handler feet manager can take, independently of the other ground handling fleet managers, one of the three following decisions:

-maintain the corresponding ground handling task in the duty at the same place in the sequence. In that case the resulting delays should be integrated into the scheduling of the duty.

-maintain the corresponding ground handling task in the duty but at another place in the sequence.

-delete the corresponding ground handling task from the duty and assign it to another duty or to a spare vehicle and team (local duty) to perform the task when the aircraft will be available.

When a departing aircraft is delayed for some external reason (airport, airline, ATC), one of the three following decisions must be taken by each ground handler fleet manager:

-maintain the corresponding ground handling task in the duty at the same place in the sequence. In that case the resulting delays should be integrated into the scheduling of the duty.

-maintain the corresponding ground handling task in the duty but at another place in the sequence.

-delete the corresponding ground handling task from the duty and assign it to another duty or to a spare vehicle and team (local duty) to perform the task when the aircraft will be available to start departure ground handling activities.

From the solutions of the assignment problems solved by each ground handling manager , the ground handling coordinator forward the milestones corresponding to the completion of ground handling activities to the airlines and the ATC to produce if necessary new estimates for the departure schedule of the aircraft.

Case study

Airport and ground handling characteristics

To the best of our knowledge, no benchmark instances exist for this problem. Then, a real traffic data from Palma de Mallorca Airport has been considered. Palma de Mallorca Airport is, with respect to aircraft and passengers traffic, the third largest Spanish airport.

During the summer period it is one of the busiest airports in Europe, with 22.7 million of passengers in 2011. The airport is the main base for the Spanish carrier Air Europa and also a focus airport for German carrier Air Berlin. It occupies an area of 6.3 km2 (2.4 sq mi). Due to rapid growth of aircraft traffic and passenger flows along the last decades, additional c) Tasks information: using the specifications of the aircraft manufacturers [START_REF] Airbus | Airbus, AXXX airplane characteristics for airport planning[END_REF]Boeing 200, ATR 1999), three types of aircraft with different sizes were modeled. For each operation included in the problem and according to the type of aircraft, the duration, the precedence restrictions regarding the other tasks, and the type of vehicle used have been considered.

Implementing the global planning of ground handling resources

The developed heuristics have been implemented in Java. As it has been mentioned on the chapter 4, this approach is proposed to calculate the nominal number of resources required for each ground handling manager during a day of traffic.

The heuristic proposed is a greedy heuristic.

The solution of this approach is given in the Using this solution, only 12 aircraft will have a delay at the level of the departure times with a maximum delay of 14 minutes.

The 14 aircraft that would leave their parking stand later that which it had been predicted their departure times match with busiest flight traffic period. The proposed global planning heuristics of ground handling resources has been calculated using the dataset presented in the precedent paragraph. This global planning of ground handling resources as it has been described in the chapter 4 is composed of three steps.

For the first step, it has been supposed that the nominal number of each ground handling resources is presented in the figure. In the second step, the unit time period which has been considered has been taken equal to the maximum between 5 minutes and the smallest duration of a ground handling operation, including transfer time: Cleaning 5

Boarding passengers 5

Unloading baggage 5

Fuelling 5

Loading baggage 5

Sanitation 5

Potable water supply 5

Push-back 5

Table5.4:The unit time period of each ground handling operation results

The third step of the estimation of the necessary resources at a given time for all ground handling managers is performed by adding margins to the nominal level of demand of scheduled arrival and departure flights. This is done according to formula (4.5), (4.6) and (4.7).

The figures presented below provide the size of the resources required for each ground handling manager to perform their corresponding ground handling tasks in case of perturbations that can occur during the day. As it can be seen, the number of reserved resources increases in the busiest flight traffic period (arrival/departure aircraft) according to the figure 5.6.

Implementing the heuristics for on-line GHFA

To test the efficiency of this approach, the accurate arrival times of each considered flights are supposed to be communicated to the ground handling managers thirty minutes before the effective landing. Here, this allows the ground handling managers to reassign the ground handling resources by considering the updated arrival times at the parking stands of where compared with the ones obtained through the proposed heuristic approach. The considered ground handling resources were the ones effectively existing at that airport.

The application of the proposed heuristic approach to the nominal schedule of arrivals during the considered reference day provided a feasible assignment for each ground handling manager in at most 0.3 seconds. These solutions led to delays with respect to scheduled departure schedule involving only 36 aircraft, with a maximum delay of 16 minutes. The average delay among delayed aircraft has been of 7 minutes. Figure 5.7 displays the hourly distribution of delayed aircraft at departure resulting from the application of the proposed decentralized approach. Clearly, the occurrence of these delays corresponds to the busiest aircraft traffic periods at the airport where ground handling resources become short. The proposed heuristic could be restarted using higher ground handling resource levels provided by the ground handling coordinator to improve the expected delay performance of the system. Historical data from 01/08/2007 at Palma de Mallorca Airport indicate that about 244 aircraft departures where delayed for multiple reasons, including one of the main reasons, ground handling delays. The maximum observed delay is about 520 minutes and the average delay among delayed aircraft has been of 30 minutes. There is information about the use of a particular system to manage ground handling at that airport. It is clear, that in theory, the proposed heuristic approach provide significantly improved results with respect to departure delays. Then it can be expected for this particular airport that, even if the implementation of the proposed heuristic approach is not perfectly performed, some noticeable improvement with respect to the current practice will take effect. This is quite noteworthy since the proposed heuristic has not been particularly improved with respect to a basic greedy approach.

Conclusion

In this chapter the solution of the different assignment problems solved by the ground handling coordinator and ground handling managers has been considered. An exact approach has been adopted at first to solve the global assignment problem considered in the proposed framework by the ground handling coordinator. Numerical results using LP-Solve show that beyond the case of very small problems (10 to 12 flights), the exact approach is not able to produce the optimal solution in an acceptable time. So a greedy heuristic has been developed in that case. In the case of the pairing problems faced by the ground handling managers, even if the corresponding optimization problems are of smaller size that the one faced by the ground handling coordinator, only the heuristic approach has been developed.

The whole process has been illustrated by considering a case study with real traffic where it has been assumed that flight arrival times are perfectly known half an hour in advance. Even if scheduled and effective arrival times are different, the adopted traffic situation can be considered as normal. In the next chapter, the proposed framework for ground handling management will be discussed in the case of huge traffic perturbations characterizing an airport disruption.

CHAPTER 6

GROUND HANDLING MANAGEMENT UNDER DISRUPTION

Introduction

In this chapter is considered the case in which an airport is subject to a large perturbation which in general affects all its sub-systems: runway operation, airside taxiing operation, ground handling operations, passenger terminals and groundside land traffic. This drastic situation termed airport disruption has been defined in qualitative terms and very few specific studies to cope systematically with it are available. In this chapter, after trying to better identify this situation, a new formalism is introduced to cope with the uncertainty associated to the duration of many activities in this situation. Then a tentative approach to design a decision process for the ground handling coordinator to better cope with this situation is proposed. This adapted decision process is based on the assessment of the criticality of each arriving or departing aircraft in the reduction of the disruption situation, irrespective of direct ground handling operations costs.

Airport Disruption

Definition of airport disruption

To our knowledge there exists no specific definition for airport disruption while some recent works refer to this situation [START_REF] Ploog | Disruption Management in Operation Control, m2p Consulting, Presentation[END_REF] and [START_REF] Tanger | Booz & company's London and Kuala Lumpur offices. Managing Airport Disruption: Achieving Resilience through Collaboration[END_REF] without providing any definition. According to the British Standards Institute [Business continuity management, 2006], "a disruption is an event which causes an unplanned, negative deviation from the expected delivery according to the organization's objectives". According to this definition, the term disruption could be perceived as equivalent to the term perturbation. The ground handling services are delivered in a changing environment with many operational uncertainties. For example, the expected arrival times for flights are subject to frequent delays, the duration of ground handling tasks is sensitive to unexpected events such as additional travel time due to traffic congestion on airside service ways or machine breakdowns. Then it could be considered that ground handling management tackles in permanence disrupted situations.

In the Air Transport management literature, the issue of airline disruption management has been considered more early [START_REF] Kohl | Airline disruption management-Perspectives, experiences and outlook[END_REF], [START_REF] Clausen | Disruption management in the airline industry -Concepts, models and methods[END_REF] and has been associated with the airlines recovery problem [Batu and al, 2006], [START_REF] Lettovsky | Airline operations recovery: An optimization approach[END_REF]. In fact, for these authors a disrupted situation occurs when a succession of unexpected events leads the system state out of range of the current operation practice which is no more able to compensate deviations and make the system state to return near a nominal situation. In that case, recovery actions must be taken to avoid a cumulative degradation of the performance of the system.

In this chapter, this later understanding of a disrupted situation will be transposed to the case of airport management where disruption management should also cope with some crisis situations.

Consequences of airport disruption

Here the operational situation which is considered is the one in which, as a consequence of some event or succession of events, the whole airport operation is perturbed and presents at the same time important delays and large uncertainties with respect to effective arrival and departure times.

Possible consequences of an airport disruption situation can be [START_REF] Ploog | Disruption Management in Operation Control, m2p Consulting, Presentation[END_REF]:

-for passengers: canceled departing flights or loss of connection flights by passengers (delayed arrival at stand of previous flight, delayed transfer of passengers and luggage towards the following flight), passengers who are obliged to wait for long periods without precise information at boarding gates or in the aircraft once boarded.

-for crews: impossibility for a crew member to continue its scheduled flight pairing, difficulties for airlines to constitute technical and commercial crews for departing flights.

-for aircraft: unavailability of an aircraft to perform a scheduled departing flight, difficulty to perform scheduled side activities such as maintenance activities.

Sources of airport disruption

Causes for the airport disruption situation can be related with incoming traffic, the airport itself and exogenous events.

With respect to incoming traffic, airport disruption can be generated when a large share of the incoming traffic during a period of time, for example a peak hour for the airport, arrives late with large delays. This can be the result of bad weather conditions, of a temporary lack of capacity of the air traffic system caused by an excess of traffic demand, or by the reduction of effective ATC capacity as a result of some social or technical problem. While the ATFM system [START_REF] Gwiggner | Implicit relation between time slots, capacity and real demand in ATFM[END_REF] makes the excess of demand situation very unlikely, the ATC system presents in general high levels of reliability and availability.

With respect to the airport itself, airport disruption situations can be produced by a temporary lack of capacity caused for example by the closure of a runway, bad weather conditions (fog, snow, strong rain), the lack of sufficient ground installations and equipment to cope with a peak of traffic, social problems (strike of some category of airport employees), occurrence of hazards at the airport (crash of landing or departing aircraft, huge fire).

Exogenous causes which can result in airport disruption are transient situations associated to the recovery from the effect of natural hazards (volcano ashes, tsunami, nuclear alerts) or from overfly restrictions in conflictive areas.

Ground Handling Management Objectives and

Operation under Airport Disruption

Here it is considered that the management of ground handling during an airport disruption should contribute to its reduction and elimination. This implies eventually the definition of new objectives and new decision processes to be adopted during this transient situation. In such a situation, it can be expected that the proposed decentralized ground handling management should be more strongly driven by the ground handling coordinator to tackle with priority the overall airport objectives.

Ground handling management objectives under airport disruption

In this situation, the whole operations planning performed by ground handlers must be revised with temporary new objectives:

-Contribute to the return of airport operations to a near nominal situation as soon as possible since the disrupted situations reduce the overall airport performance and service offered to the passengers. This can be done through the adoption of more costly ground handling solutions.

-Limit as much as possible the maximum flight delays instead of the mean passenger delay adopted in regular airport operations.

-Minimize the number of missed passenger connections. This has an important contribution onto the performance of the airport. In general, the most of passenger missed their connection because of either the ground handling operators which they did not taken into account the impact of delaying the performing the ground handling activities of this flight or of the bad manner of sharing information between the A-CDM partners.

A proposal for ground handling management under airport disruption

Here it is proposed, with the objective to handle the overall airport objectives, at the ground handling coordinator takes over the direction of the ground handling management by imposing to the ground handling managers, priority lists of flights to be processed. The reordering of the scheduled arrivals and departures into priority lists with respect to ground handling by the ground handling coordinator can be the result of:

-a negotiation with the other A-CDM partners about special demands from them, -the assessment of the current and near future ground handling situation according to current and predicted traffic of aircraft, -the occurrence of some ground handling incident (equipment failure).

The ground handling coordinator will provide online to the ground handling managers two frequently updated priority lists:

-one is relative to arriving aircraft, -the other one is relative to departing aircraft.

An arriving aircraft will enter these two priority lists when itspredicted arrival time at the parking stand becomes smaller than the ground management operational horizon. An arriving or departing aircraft will leave the corresponding list when its ground handling processing is ready to start. An aircraft can be at the same time in these two priority lists, so these lists are not independent.

Here, ground handling resources are also separated between those which are dedicated to arriving aircraft and those which are dedicated to departing aircraft. Then ground handling managers will assign their respective resources according to these priority lists.

This will make that many arriving or departing aircraft will not be necessarily processed according to their rank in the arriving or departing time schedules. Since in this situation demand levels may overpass available ground handling capacity, the ground handling coordinator establishes these priority lists for ground handling managers with the objective to reduce or avoid cumulative effects which will otherwise contribute to prolong the disrupted situation of the airport.

In this case, taking into account the uncertainty about the completion of many events at the airport airside, the ground handling coordinator will require from some ground handling managers to put into alert all their effective ground handling resources. For example this could be the case with the de-icing capacity of an airport. For others ground handling activities, the ground handling coordinator can adopt a time-of-the-day policy based on pre computed reserves to make ready ground handling extra resources.

In that case, it is considered that the pool of ground handling resources necessary to perform arriving or departing ground handling activities are required to be available at the parking place as soon as possible and start their activities according to the ground handling sequence associated to this aircraft.

For example, one of the objectives with respect to flight arrivals is to minimize the waiting time for de-boarding passengers and luggage, another one is to make sure that passengers embark in the aircraft with a minimum delay, if any, with respect to the rescheduled flight departure time. So, they will be in charge of mobilising in due time the necessary ground handling resources for flight arrival or flight departure processing.

Airport air traffic control services update the predicted arrival times which are forwarded to airport services, including airlines and ground handling. This starts the process of updating the assignment and scheduling of tasks for each ground handling fleet. In the case in which repeated aircraft arrival schedule perturbations are occurred or are expected, according for instance to meteorology conditions, the horizon of the different ground handling fleet management problems can be commonly limited to no more than two hours ahead.

Each ground handling manager will solve the new instance of each GHFA problem by applying some kind of the heuristic such as the one described in the previous chapter but modified with respect to one point:

Instead of treating each flight according to its position in the arrival or departure schedules, each flight will be treated according to its updated priority rank in the corresponding arrival or departure list.

Operational uncertainty during airport disruption

In general in an airport disruption situation, which is generated in general, as discussed above, by a succession of unexpected perturbations, many parts of the airport start behaving out of nominal conditions generating increased travel and service times as well as a higher distribution of them. Although ground traffic is always performed in compliance of priority rules between vehicles of the same type and between vehicles of different types along the different ground tracks of the airport, multiple queues of aircraft and ground service vehicles may grow and interact.

To be reactive to the disruption situation, ground handling resources must be ready to enter into action once a high priority flight arrives at the parking stand or when a high priority flight has to prepare for departure. Then, the ground handling management should work out decisions based on some prediction of arrivals or departures times from the parking stands and by adopting some estimates for service vehicle travel times as well as for ground handling activities durations. Considering the high degree of uncertainty with respect to timing and delays, a deterministic approach, such as through deterministic optimization, to tackle this situation appears ineffective [START_REF] Ravi | Hedging uncertainty: approximation algorithms for stochastic optimization problems[END_REF]. On the other side, the adoption of a probabilistic approach will be unfeasible by lack of statistical data on one side and by the resulting cumbersome computation needs [START_REF] Dyer | Computaional complexity of stochastic programming problems[END_REF]. Then, is the following subparagraph, an intermediate approach where uncertainty is displayed but treated through rough processes will be proposed. In the considered case, the ground handling coordinator is supposed to generate the priority lists according to the current and predicted ground handling situations. These lists, as it has been mentioned before, will be provided on line to the different ground handling managers who will make a copy of them. Figure 6.1 describes the ground handling management under disruption by generation the priority lists at the level of the GHC.

Since these priority lists can be modified at the ground handling coordinator level according to the occurrence of unexpected events, this could imply that the assignments of ground handling units to flights should be changed in accordance. To provide some stability to the assignments performed by the ground handling managers, it has considered that once a ground handling unit starts to turn ready to perform an activity at a given flight, this assignment is definitive and the corresponding flight is deleted from the list of the 138 corresponding ground handling manager. This will happen only with flights which are close to be processed.

Figure 6.2 represents the process of the ground handling management under uncertainty at the two level of the proposed ground handling management organisation structure: GHC and GHMs.

Adopted representation of uncertainty

In the following, to represent uncertainty with respect to the time occurrence of events or the duration of activities, durations will be represented by fuzzy dual numbers [START_REF] Cosenza | Nombres et ensembles duaux flous et applications[END_REF], [START_REF] Cosenza | Fuzzy sets and dual numbers: an integrated approach[END_REF].

F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 Operational Horizon F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 GHM i GHC i GHU 1 i GHU 2 i k GHU i X

GHU

Operating made ready to perform its next activity where a is the primal part and b is the dual part of the fuzzy dual number.

Observe that a crisp fuzzy dual number will be such as b is equal to zero, loses both its dual and its fuzzy attributes. To each fuzzy dual number is attached a fuzzy symmetrical number whose graphical representation is given below where μ is a symmetrical membership function defined over R:

Here we recall some basic operations with fuzzy dual numbers.

The fuzzy dual addition of fuzzy dual numbers, written  ~, is identical to that of dual numbers and is given by:

        2 1 2 1 2 2 1 1 . . . y y x x y x y x           (6.1) Its neutral element is    . 0 0 
, written 0 ~. The fuzzy dual product of two fuzzy dual numbers, written  , is given by:

        1 2 2 1 2 1 2 2 1 1 . . . . . y x y x x x y x y x          (6.2)
The fuzzy product has been chosen in that way to preserve the fuzzy interpretation of the dual part of the fuzzy dual numbers but it makes a difference with classical dual calculus.

The neutral element of fuzzy dual multiplication is  

 . 0 1 
, written 1 ~ and only non-zero crisp numbers have an inverse. Both internal operations, fuzzy dual multiplication, are commutative and associative, while the fuzzy dual multiplication is distributive with respect to the fuzzy dual addition. Observe that the nilpotent property of operator  is maintained:

0 2      
. It appears also that fuzzy dual calculus is quite simpler than common fuzzy calculus ([Kosinsky, 2006], [Nasseri, 2006]). The pseudo (  ~is not a vector space) norm of a dual fuzzy number is given by:

      . b a b a   (6.3)
where 0   is a shape parameter. The shape parameter can be defined as:

 dy

y b y . 2 1       
(6.4) Figure 6.3 displays standard fuzzy symmetrical numbers with different shape parameters. The following properties are met by this pseudo norm whatever the values of the shape parameters: (6.8) Partial orders between fuzzy dual numbers can be introduced using the above pseudo norm.

0 . : .       b a b a   (6.5)      R b R a , 0 0 .      b a b a  (6.6)             . . . .        b a b a      R b R a   , , , (6.7)   b a b a . . . .             R b R a  , ,
First a strong partial order written   can be defined over  ~ by:

2 2 1 1 2 2 1 1 2 2 1 1 . . . . : . , . b a b a b a b a b a b a                    (6.9)
Then a weak partial order written   can be also be defined over  ~ by:

2 1 1 1 1 2 2 2 2 1 1 2 2 1 1 . . : . , . a b a and b a b a b a b a b a b a                       ( 6
2 1 1 . . b a b a      
More, a fuzzy equality written  can be defined between two fuzzy dual numbers by:

    2 2 2 2 1 1 1 1 1 2 2 2 1 1 2 2 1 1 . , . and . , . . . : . , . b a b a a b a b a a b a b a b a b a                        (6.11)
Then any two fuzzy dual numbers can be ranked as either strongly different, weakly different or rather equal and a fuzzy ranking can be established between them as well as max and min operators over subsets of  ~ . That means that if at time t the considered event requires the availability of some equipment or team, an equipment or team of this type should be planned to be available at time min t to be sure to avoid delay and cannot be reassigned in the planning with certainty to any other task before time max t . Here min d and max d will be associated respectively with the minimum and the maximum difference between the finishing and the starting times of the corresponding task.

Fuzzy dual delays and durations

d d d D   (6.13) 1 2 u R 1 2 u R 2 2 1 1 . . b a b a       2 2 1 1 . . b a b a       1 2 u 1 1 2 2 . . b a b a      R 1 2 u 1 1 2 2 . . b a b a      R
This fuzzy dual formalism is here adopted since it provides a simple way to take into account operations uncertainty compared to probabilistic approaches and allow straightforward calculations and interpretation.

Ranking Flight under Disruption with Uncertainty

The following notations are adopted: each task of a ground handling process   Then, the fuzzy margin of arriving aircraft i is given by:

a ij i C j a i m m i min ~) (     (6.17)
The amended arrival time for flight i is then given by:

a i a i a i m t t   (6.18)
To each departing flight iI D , can be assigned the difference In the case in which the ground handling tasks are relative to a departing flight j, the amended predicted time to start ground handling activities at the corresponding parking position is now given by: Let the integer r a (i) and r d (i) be the amended rank of arriving or departing flight i.

a ij j i and C j i d j d j m t t i min ~) ( 1       (6.19)

Ground Handling Fleets assignment to flights

Then arriving and departure flights are processed in the corresponding produced orders r a (i) and r d (i), where ground handling units are assigned to the corresponding aircraft. In the case of an arriving flight, ground handling arrival tasks (unloading luggage, de-boarding, cleaning and sanitation) are coped with by assigning the corresponding ground handling units in accordance to their previous assigned tasks with other aircraft, their current availability, and their current distance to the considered aircraft. Here the common reference time schedule for the ground handling arrival tasks is

A a i I i t  , ˆ.
In the case of a departing flight, ground handling departure tasks (fuelling, catering, luggage loading, boarding, water and push back) are also coped with by assigning the corresponding ground handling units in accordance to their previous assigned tasks with other aircraft, their current availability, and their current distance to the considered aircraft. Here the common reference time schedule for the ground handling departure tasks is

D d i low I i t B  ), ( .
In both cases it is considered that the whole set of different ground handling units necessary at arrival or departure is assigned by considering the common reference time schedule. This assignment of ground handling units to flights either arriving or departing is performed on a greedy base by considering the closest vehicle available to perform the required task. This will make that at the start of ground handling activities for an arrival or departure flight, all necessary resources will be nearby the parking place and that scheduling constraints between elementary ground handling tasks will be coped with locally without need of communication between the different ground handling managers. This is a rather simple greedy heuristic which provides for each fleet facing the current service demand a complete solution through a reduced computational effort. So there is no limitation in calling back this solution process any time a significant perturbation occurs.

Illustration of the proposed approach

To evaluate the proposed approach, the data used on the study case of the Chapter 5 has been modified to create artificially a disruption situation. Here it has been considered that for any external reason, for exemple some severe weather conditions, a part of earlier scheduled arriving flights in the morning have been delayed and the airport operates under a concentrated arriving traffic at capacity between 11a.m. and 1 p.m.. Then, the effective arrivals and scheduled departures are those of In the case of this airport, there are no connections between the flights since in general this airport is a final destination for most of the passengers, so the arrival and the departure priority lists coincide. The priority list is calculated here by taking into account the predicted departure date of the flight j, which is the flight serviced by the same aircraft than for flight i.

Here ij D ~ is the minimum fuzzy dual duration of ground handling around arrival of flight i and departure of flight j and the real arrival date of the flight i respecting the considering degree of uncertainty. This duration ij  ~, which is a fuzzy dual number, can be expressed by:

  d j a i ij ij t t D     ˆ (6.22)
This application provided a feasible assignment for each ground handling manager in at most 0.4 seconds each updating of the priority lists.

Conclusion

In this chapter, the proposed framework for ground handling management has been considered in the case of a huge traffic perturbation characterizing an airport disruption.

In a first step the concept of airport disruption has been analyzed as well as the main sources of airport disruption, and a definition has been proposed for it. Then the operations planning procedures performed within the proposed management structure of ground handling have been revised by adopting temporary new objectives and taking into account the uncertainty with respect to activity delays in this situation. During the disruption period, the ground handling coordinator takes over the direction of the ground handling management by imposing to the ground handling managers, priority lists of flights to be processed. The computation of these priority lists makes use of fuzzy dual calculus to take into account delays uncertainty. The feasibility of the proposed approach is displayed by considering the case of a disruption at Palma de Mallorca airport.

The sustained global economic growth of the last decades has been made feasible by the development of improved means of communication and of transportation of people and goods. It has been particularly the case with air transportation where, during the last forty years, the number of passengers has been multiplied by seven. This increase of passenger volume has been possible by a corresponding increase of aircraft traffic which a permanent challenge for civil aviation authorities and airports to supply sufficient capacity to provide a safe transportation service with acceptable quality standards. Then, in the last decade, new traffic management practices, such as A-CDM, based on multi-agent and collaborative decision making concepts have been introduced. Among the many activities which contribute to the safety and efficiency of air transportation, airport ground handling plays an important role even if it has not been too much mediatised relatively to pilots and ATC issues.

In this thesis airport ground handling has been first described and analyzed, demonstrating the diversity and the complexity of the ground handling activities performed on a grounded aircraft which are organized in a serial-parallel structure where any delay on a particular activity may have a strong impact on its overall performance.

It has appeared that to avoid delays generated by ground handling activities, there is a need for a tight synchronization to process the stream of arriving/departing aircraft.

Then this introduces the need for an efficient management structure to maintain this whole process in efficiency grounds and contribute positively to the airport performance. Considered the actual practice it has been found that the concerned stakeholders (airport authorities, airlines, specialized ground handling operators) are today involved in variable degrees in the management of ground handling at different large airports. Also, it has been observed that when considering direct and indirect costs related to ground handling at airports, direct cost resulting from the execution of ground handling tasks are relatively very small with respect to potential over costs resulting from even limited dysfunctions of ground handling operations. Then it has appeared crucial to promote the ability of the ground handling management to be able to prevent disruptions and to reduce the impact of traffic perturbations when they happen. This supposes the availability of the right decision processed within the right management organization. An overview of the main decision processes developed in the field of Operations Research, in general formulated as optimization problems, has been performed, showing the difficulty to adopt in that case exact solution approaches either for the management of a particular ground handling activity or for an overall optimization of the ground handling resource assignment and scheduling. Next, different heuristics have been built to provide a solution to these nominal problems, however few works had been done in report some experiments where the heuristic applied to ground handling scheduling are assessed in perturbed environments. Either using exact or approximate methods, it appeared that the many of these studies miss to consider the cost dimension where the direct cost resulting from ground handling activities is secondary with respect to the economic consequences of delays at servicing arriving and departing aircraft and the management dimension where an organization able to cope with routine situations as well as perturbed conditions or even disrupted situations, must be designed. Then, it has been shown that adopting a hierarchical approach, it is possible to organize ground handling management in accordance with the A-CDM approach where a ground handling coordinator operates as an active interface between the air transport operators and the specialized ground handling managers in charge of the ground handling units. The information flows associated with the different levels of management and operations have been described using the Petri net formalism. Then, the different assignment problems solved by the ground handling coordinator and ground handling managers have been considered. Considering the complexity of the respective problems, greedy heuristics have been chosen to illustrate the proposed approach. The whole process has been illustrated first by considering a case study with real traffic presenting rather limited perturbations. Then in a second step, the proposed framework for ground handling management has been considered in the case of a huge traffic perturbation characterizing an airport disruption.

The main objective of this PhD thesis has been to contribute to the design of a general efficient management organization for ground handling at airports. Many perspectives of research and development aimed at improving the airport performance when considering the ground handling sector, arise in different fields to complete the present study:

The collaborative decision making process used by the A-CDM partners should integrate the proposed organization of the ground handling management function with the ground handling coordinator as interface.

The capability of the ground handling coordinator to perform his tasks should be based on improved decision processes covering issues such as:

-Evaluation of the impact of operational perturbations and the effectiveness of ground handling to cope with them, -Processing of information with a variable degree of uncertainty, -Monitoring and diagnostic of the overall ground handling process by detecting abnormal operational situations up to disruption, -Adapting operational objectives according to situation diagnostic and priority ranking of flight to be processed by ground handling, -Dynamic sizing of reserve ground handling resources, -Generation of overall back-up solutions for ground handling resource assignment, -Prediction of milestones to be communicated to the other A-CDM partners.

The capability of each ground handling manager to assign efficiently, according to the directives of the ground handling coordinator, either at the pairing level or the roaster level, his assignment of available resources to the different ground handling tasks should be based on improved decision processes.

The present study has made some general assumptions about the airport and the traffic considered, while each airport has its own characteristics. Thus any general framework to manage the whole or a part of ground handling management e, should be particularized at the development level.

This annex provides the typical times for ramp activities during aircraft turn-round for different transportation aircraft. Actual times may vary due to specific practices and operating conditions.

I. A320-

Theoretical background

The Vehicle Routing Problem (VRP) is one of the most popular combinatorial optimization problems. It is aimed at determining an optimal set of routes for an available fleet of vehicles in order to service a set of customers, subject to different constraints. With many other related problems, it is NP-Hard (Lenstra & Kan, 1981)and beside exact methods, many heuristics approaches have been developed.. The Vehicle Routing Problem with Time Windows (VRPTW) and Vehicle Routing and Scheduling Problem (VRSP) are extensions of the VRP to turn it more realistic. In the case of the VRPTW each customer has a time window within which the vehicle has to begin the service and for the VRSP there are precedence constraints between the costumers.

Mathematical formulation:

The VRPTW can be formally stated as follows: given the graph

) , ( A V G  , where   n V ,..., 0 
denotes the set of all vertices in the graph representing the cities with the depot located at the vertex 0, K is the set of available vehicles that can be used and A is the set of arcs. Each arc

  j i j i  , is associated a non-negative distance matrix   ij c C 
which can be interpreted as a travel cost or as a travel time. Given K the set of available vehicles to be routed and

 

   K k N i k ij x 1 N j   (1)    N j k j x 1 0 K k   (2)    N i k i x 1 0 K k   (3)      N j k hj N i k ih x x N h   K k   (4) i i i l b e   N i   (5)   k ij ij i i j x t s b b .    N i   , N j   , K k   (6)
Constraint (1) states that each costumer has to be visited exactly once, the constraint (2) and (3) state that the service of each vehicle starts and ends at the depot, the constraint ( 4) is a flow-balance constraint; if a vehicle arrives at a costumer, it must leave that costumer next.

The window time is showed in the constraint (5) and the constraint (6) described the fact that the vehicle cannot start serving a costumer since it has not finished servicing the precedent one.

The VRPTW as it has been said before it is a generalization of the VRP. It can be considered also as a combination between the VRP and the scheduling problem or as it known as the Vehicle Routing and Scheduling Problem which take place in many real world applications.

Solution approaches

The VRPTW has been extensively studied and several formulations, exact algorithms, heuristics and metaheuristics have been proposed in the past decades.

Exact methods for the VRPTW

The exact approaches can be classified to:  Lagrange Decomposition based methods:

Various Lagrangian decomposition schemes have been applied to the VRPTW in order to find lower bounds. Jornsten and al (1986), Madsen (1988, 1990) and Hales (1992) were the most interest works which treat this subject with this approach. According Marshall and al (1995) they can currently find the optimal solution of 100 customer problems using a combination of Lagrangian decomposition and branch-and -bound.

 K-tree based methods Fisher andal (1997), Holland (1975) and Kolh and al (1997) used the k-tree approach followed by Lagrangian relaxation to solve this problem. [START_REF] Fisher | Vehicle routing with time windows: two optimization algorithms[END_REF] proposed an algorithm to solve the VRPTW optimally by formulating the problem as a K-tree problem with degree 2K on the depot. They considered that a K-tree for a graph containing n+1 vertices could be presented as a set of n+K edges spanning the graph. So, the problem was solved as finding a K-tree with degree 2K on the depot, degree 2 on the customers and subject to time and capacity constraints. A K-tree with degree 2K on the depot in this context is proportional to K routes.

 Approaches based on Column Generation Desrrosiers and al (1984) is the first study that has used the column generation to solve the VRPTW. They ameliorated it and in 1992 they presented an exact method able to solve 100costumers problems. This method is a combination of linear programming relaxed set covering and column generation.

 Approaches based on Dynamic Programming

The dynamic programming approach has been used to solve the VRPTW for the first time by [START_REF] Kolen | Vehicle routing problem with time windows[END_REF], and they were based, in their study, on the work of Christofides and al (1984) who used the dynamic programming approach to solve the VRP. The problems up to 15 customers are solved to optimality.

Heuristic algorithms

 Route-building heuristics [Baker and al, 1989] was the first paper that proposed a route-building heuristics for the VRPTW. The proposed algorithm consists, firstly, to define all possible single-costumer routes, and secondly, to determine for each iterationthe two routes whose combination provides the maximum saving. There the saving is defined as the sum of the time at which the vehicle quits the customer i to arrive at the depot and the time at which the vehicle quits the depot to arrives to customer j and the route form factor. On the basis this algorithm [Baker and al, 1980]elaborated a time oriented nearest-neighbourhood algorithm. The considered saving was defined as a combination of distance, time and time until feasibility.

Another approach presented in [Antes and al, 1995] built upon the insertion idea where each unserved customer asked to be served. Each vehicles in the schedule and which received from these unserved costumers a saving for insertion. Then these customers propose to the vehicles their best offer which will be accepted by the vehicles if are the best according their routes considering the number of alternatives. The customers van be removed from the vehicles 'routes if they violate the threshold of vehicles 'routes is violated a certain number of customers are removed and the process is initiated again.

 Neighborhood based heuristics

The r-Opt is a heuristic which is based on the neighbors to solve the routing and scheduling problems. This heuristic consists in removing r arcs from their current solution and replacing them by other r arcs. The optimal solution r-Optimal is obtained when the r-Opt neighborhood have been used and it cannot be improved more. In general, r is at most 3, but it is has been proved that it was difficult to use this number to solve the VRPTW problem since it leads to a violation of the time windows [START_REF] Potvin | An exchange heuristic for routing problems with time windows[END_REF]. [START_REF] Potvin | An exchange heuristic for routing problems with time windows[END_REF], to solve the VRPTW, used the 2-Opt*. [Christofides and al, 1984] solved the VRP using the knode interchange. This work has been a reference to solve the VRPTW by many others researchers. The λ-interchange has been proposed by [START_REF] Osman | Metastrategy simulated annealing and tabu search heuristic algorithms for the vehicle routing problem[END_REF] to solve the VRP which considered as a base to solve the VRPTW by other authors [ref]. Finally, [START_REF] Schulze | A parallel algorithm for the vehicle routing problem with time windows constraints[END_REF] adopted the shift-sequence neighborhood operator to find a solution for the VRPTW.

Metaheuristics

 Simulated annealing

In [Chiang and al, 1996] three different simulated annealing have been considered to solve the VRPTW: the first using the k-node interchange neighborhood operator, the second using the λ-interchange neighborhood operator presented in [START_REF] Osman | Metastrategy simulated annealing and tabu search heuristic algorithms for the vehicle routing problem[END_REF] and the third using an algorithm which adopted the concept of the tabu list (tabu search metaheuristic). The results showed that the second and the third converged faster than the first one. The three of these methods gave a solution in which the distances travelled were between 7% and 11% from the optimum. [START_REF] Thamgiah | Metaheuristics for the Vehicle Routing Problem with Time Windows[END_REF] used a non-monotone probability function and the λ-interchange neighborhood operator with decreasing the temperature in each iteration. The solutions obtained in this work had the same quality as those obtained in [Chiang and al, 1996].

 Tabu search

The parallelization of the tabu search has been used to solve the VRPTW by many authors. In [Garcia and al, 1994], to find the first solution, the authors used the Solomon heuristic and the 2-opt* and Or-opt as neighborhood operators. Here, the neighborhood was restricted to arcs close in distance. [Badeau a,d al, 1995] used the same heuristic to find the initial solution but combined with the cross neighborhood operator. [Cordeau and al, 2001] adopted the modification of Sweep heuristic to find the initial solution and the relocate and GENI as neighborhood operator, in this work the infeasibilities were allowed during the search. [Gehring and al, 2001] solve the problem by considering the savings heuristic for the initial solution, the Or-opt, 2-opt* and the λ-interchange as neighborhood operators, the tabu search had been hybridized with an evolutionary algorithm. Generally , and according to many works, the tabu search have been considered as best heuristics for the VRPTW. One of the conclusions in [Badeau and al, 1995] is that diversification/ intensification is just as important in obtaining good solutions as variable length tabu list.

 Genetic algorithm [Thagiah and al, 1991] was the first paper using the genetic algorithm to solve the VRPTW. In this work, the genetic algorithm was adopted to find good clusters of customers, according to a "cluster-first and a route-second" problem-solving strategy. Since the appearance of the first paper, many other works have been adopted this metaheuristic to solve the VRPTW and which provided good solutions. Generally, the most of these works used a hybrid presentation of the genetic algorithm by considering:

-different heuristic construction as [Blanton and al, 1993], [Berger and al, 1998]), -local search ([Thangiah, 1995a, b], [Thangiah and al, 1995], [Potvin and al, 1996]; [Jung and al, 2002]), -tabu search [Kit and al, 2001] -ant colony systems [Berger and al, 2003]. [ Badeau and al, 1995] :Badeau, P., Gendreau, M., Guertin, F., Potvin, J., Taillard, E., 1995

ANNEX IV PETRI NETS

I. Petri Net: Definitions

Petri nets are a graphical and mathematical modelling tool used to describe and analyse different kinds of real systems. Petri nets were first introduced by Carl Adam Petri in 1962 in Germany, and evolved as a suitable tool for the study of systems that are concurrent, asynchronous, distributed, parallel and/or stochastic. Performance evaluation has been a very successful application area of Petri nets. In addition, Petri nets have been successfully used in several areas for the modelling and analysis of distributed-software systems, distributeddatabase systems, flexible manufacturing systems, concurrent and parallel programs and discrete-event dynamic systems (DEDS) to mention just a few. A multi-agent system is a kind of DEDS that is concurrent, asynchronous, stochastic and distributed. From the DEDS point of view, multi-agent systems lack analysis and design methodologies. Petri net methods are used in this work to develop analytical methodologies for multi-agent systems. Petri nets are often used in the modelling and analysis of DEDS. They include explicit conditions under which an event can occur; capturing also the relations between concurrent and asynchronous events. As a result, Petri nets are suitable for studying complex and general DEDS. This section presents an introduction to Petri nets. Petri nets are defined followed by important properties and analysis methodologies. Finally, an example of a manufacturing application is presented.

Definition1:

The following is the formal definition of a Petri. A Petri net is a five tuple: The meanings of places and transitions in Petri nets depend directly on the modelling approach. When modelling, several interpretations can be assigned to places and transitions.

For a DEDS a transition is regarded as an event and the places are interpreted as a condition for an event to occur. A place p is said to be an input place to a transition t if an arc is directed from p to t . Similarly, an output place of t is any place in the net with an incoming arc from transition t . In the example (figure 1) 1 p is an input place of 1 t and 2 p is an output place of 1 t .

Transition firing: A transition can fire only if it is enabled. For a transition t to be enabled, all the input places of t must contain at least one token (in this case, it was assumed that the weights W of the Petri net are equal to one. When the weights are not indicated they are assumed to be one. The weight on an arc coming to a transition from one of the incoming places indicates the minimum number of tokens needed in the incoming place in order for that transition to be enabled. When the transition fires, it will remove from the incoming place the amount of tokens indicated by the weight of the arc). When a transition is fired, a token is removed from each input place, and one token is added to each output place. In this way the tokens travel through the net depending on the transitions fired. In the example of figure 1 only transition 1 t is enabled. When 1 t fires, one token is removed from place 1 p and one token is added to place 2 p . Figure 2 shows the evolution of the Petri net in the previous example. The marking of the Petri net represents the state of the net. As described above, thetransitions change the state of the Petri net in the same way an event changes the state of a DEDS.

II. Properties of Petri net:

This section covers some of the most important properties of Petri nets such as Reachability, Liveness, Boundedness and Reversibility. These properties are essential for the analysis of Petrinet models. Furthermore, they are required characteristics for the use of Petri nets inperformance evaluation.

These are properties that could be applied to multi-agent systems models. Examples of these properties are boundedness and liveness since they are related to deadlock avoidance in DEDS. Other properties are going to be relevant to multi-agent systems particularly to the communication, interaction, and single agent architectures.

Reachability:

A marking j M is said to be reachable from marking i M if there exist a sequence of transitions that takes the Petri Net from state i M to j M .

The set of all possible markings that are reachable from 0 M is called the reachability set and is defined by   0 M R . The reachability set can be obtained from the reachability graph (figure 3).

Liveness:

A Petri Net is said to be live for a making 0 M if for any marking in   0 M R it is possible to fire a transition.

The liveness property guaranties the absence of dead lock in a Petri Net. This property can also be observed from the reachability graph: if the reachability graph contains an absorbent state the Petri Net is not live at that state and it is said to have a dead lock. If the net is not live for marking 0

M then at least one marking from   0 M R will not have any enabled outgoing transitions. If the reachability graph is considered as the state graph of the net, then an absorbent state is that from which the marking it is representing does not have any outgoing transitions enabled. As a result, when the net reaches an absorbent state, it will remain in it indefinitely.

Boundedness:

A Perti Net is said to be bounded or k-bounded if the number of tokens in each place does not exceed a finite number k for any marking in   0 M R Furthermore, a Petri Net is structurally bounded if it is bounded for any finite initial making 0 M . A Petri Net is said to be safe if it is 1-bounded.

Reversibility:

A Petri Net is reversible if for any making in   0 M R is reachable. This means that the Petri Net can always return to the initial marking 0 M .

For the example in figure, the reashability set:

              2 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 2 , 0 , 0 , 1 , 1 5 4 3 2 1 0       M M M M M M R
.

The Petri net is live, reversible and 2-bounded for the marking

  0 , 0 , 2 0  M .

III. Structural analyses

This section considers the structural analysis of Petri nets by using invariant analysis.

Basically, the liveness and boundedness of the net will be assessed by using P-invariants and T-invariants. These invariants are obtained from the incidence matrix of the net and they give The example presented in figure 1 shows an ordinary Petri net (all the weights are equal to 1) and the following is its corresponding incidence matrix.

Boundedness assessment

The P-invariants of the incidence matrix are used in Theorem 1 to make an assessment of the boundedness of the Petri net. A Petri net model is covered by P-invariants if and only if, for each place s in the net, there exists a positive P-invariant x such that   0  s x . Theorem 1 A Petri net is structurally bounded if it is covered by P-invariants and the initial marking 0 M is finite.

Liveness assessment

The Theorem 2 A Petri net that is finite is live and bounded if it is covered by T-invariants.

Fuzzy logic and fuzzy set was introduced by Zadeh Lotfi as an extension of classical set theory, and is built around the central concept of a fuzzy set membership function. Its concept is based on trading off between significance and precision. Fuzzy Logic is a convenient way to map an input space to an output space. This concept is used due to its many advantages, such as, its naturalness of its approach and not its far-reaching complexity, its flexibility, it is a very powerful tool for dealing quickly and efficiently with imprecision and non-linearity, it is also tolerant of imprecise data as Fuzzy Reasoning builds this understanding into the process rather than taking it onto the end. As fuzzy logic is known to deal with linguistic, vague, and uncertain data, its use in many applications was utilized to fulfill this task.

It was cited from the literature (Martin Hellmann, 2001), fuzzy set theory enables the processing of imprecise information by means of membership function. In contrast to Boolean Characteristics Mapping of a classical set (called crisp set) takes only two values: one, when an element belongs to the set; and zero, when it doesn't. In fuzzy set theory, an element can belong to a fuzzy set with its membership degree ranging from zero set to one. Fuzzy sets are usually identified with these membership functions as presented in figure V.1. Fuzzy set theory has also entered a vast domain of application tools, such as fuzzy arithmetic, approximate reasoning, control, and modeling paradigms. Moreover, in fuzzy rule-based systems, knowledge is represented by "IF -THEN" rules. Fuzzy rules consist of two parts, an antecedent part stating conditions on the input variable, and a consequent part describing the corresponding values of the output variable. In Mandani type models both antecedent and consequent part consist of fuzzy statements concerning the value of the involved variables.

Fuzzy rules could be derived from both experts reasoning and linguistic, and from relationships between the system variables.

There are several defuzzification methods, but the centre-of-gravity formula as illustrated in figure V.7 is the most frequently used. Also, in order to improve the model's performance, its variables and parameters can be adjusted, and the best combination can be found by means of simulation tests.

1 Figure 1

 11 Figure 1. 1: Localization of ground handling within the turnaround process ..........................

Figure 1 . 2 :

 12 Figure 1. 2: Aircraft related operations at airports ...................................................................

Figure 1 . 3 :

 13 Figure 1. 3: Different devices to handle passengers boarding and de-boarding processes ......

Figure 1 . 4 :

 14 Figure 1. 4: Luggage loading/unloading processes ..................................................................

Figure 1 . 5 :

 15 Figure 1. 5: Luggage loading/unloading processes ..................................................................

Figure 1 . 6 :

 16 Figure 1. 6: Catering process....................................................................................................

Figure 1 . 7 :

 17 Figure 1. 7: Different aircraft fuelling processes .....................................................................

Figure 1

 1 Figure 1. 8: Sanitation process .................................................................................................

Figure 1

 1 Figure 1. 9: Potable water supply process ................................................................................

Figure 1 .

 1 Figure 1. 10: On-going de-icing process ..................................................................................

Figure 1 .

 1 Figure 1. 11:Push-back process ...............................................................................................

Figure 1 .

 1 Figure 1. 12: Aircraft servicing arrangement -Typical handling operations Boeing 777-300ER [Boeing manual] ...........................................................................................................

Figure 1 .

 1 Figure 1. 13: Ground handling process for a Boeing B737 [Boeing 737 Manuel] ..................

Figure 1 .

 1 Figure 1. 14: Ground handling process at Belgrad International Airport [Vidosavljević and al, 2010]………………………………………………………………………………………….22 Figure 1. 15: Ground handling process at Stockholm Airport [Norin and al 2008] ................

Figure 1 .

 1 Figure 1. 16: Turnaround with loose ground handling activities .............................................

Figure 1 .

 1 Figure 1. 17: Turnaround with tight ground handling activities ..............................................

Figure 1 .

 1 Figure 1. 18: Typical durations of handling operations Boeing 777-200 [Boeing B777 manual] .....................................................................................................................................

Figure 1 .

 1 Figure 1. 19: Typical durations of handling operations Airbus 330-300 [Airbus A330 manual] ..................................................................................................................................................

Figure 1 . 2 Figure 2

 122 Figure 1. 20: Candidate critical paths for ground handling process .........................................

Figure 2 4 Figure 4

 244 Figure 2. 2: Management timeline ...........................................................................................

Figure 4 . 2 :

 42 Figure 4. 2 : Connection of A-CDM with Ground Handling ...................................................

Figure 4 . 3 :

 43 Figure 4. 3 : Example of the set of ground handling activities for an A320 at Stockholm airport .......................................................................................................................................

Figure 4 . 4 :

 44 Figure 4. 4: Introducing a Ground Handling CDM ..................................................................

Figure 4 . 5 :

 45 Figure 4. 5 : Planning of a safe level for ground handling resources .......................................

Figure 4

 4 Figure 4. 6 : Three-levels organization of ground handling management ...............................

Figure 4 . 7 :

 47 Figure 4. 7 : RdP representation of GHUi's operations ...........................................................

Figure 4 . 8 :

 48 Figure 4. 8 : RdP representation of operations by a GHMj ....................................................

Figure 4

 4 Figure 4. 9 : RdP representation of operations by a GHC ......................................................

Figure 5 . 1 :

 51 Figure 5. 1 : Structure and duration of the ground handling activities ...................................

Figure 5

 5 Figure 5. 3 : 01 /08/2007 Palma de Mallorca Airport Aircraft hourly traffic ........................

Figure 5 . 4 :

 54 Figure 5. 4 : Hourly delays distribution resulting from the proposed heuristic ....................

Figure 5 . 5 :

 55 Figure 5. 5 : Nominal composition of ground handling fleets ...............................................

Figure 5 . 6 :

 56 Figure 5. 6: Number of the resources required for each ground handling activities each of period of time .........................................................................................................................

Figure 5 . 7 :Figure 6

 576 Figure 5. 7 : Hourly delays distribution resulting from the proposed heuristic ....................

Figure 6 . 2 :

 62 Figure 6. 2 : Operational uncertainty during airport disruption .............................................

Figure 6 . 3 :

 63 Figure 6. 3 : Representation of a fuzzy dual number .............................................................

Figure 6 . 4 :

 64 Figure 6. 4 : Examples of shapes fro fuzzy dual numbers .....................................................

Figure 6 . 5 :

 65 Figure 6. 5 : Example of inequalities (weak and strong) between fuzzy dual numbers .........

Figure 6 . 6 :

 66 Figure 6. 6 : Examples of fuzzy equality between fuzzy dual numbers .................................

Figure 6 . 7 :

 67 Figure 6. 7 : Example of ground handling activities' sequencing ..........................................

Figure 6 . 8 :

 68 Figure 6. 8 : Illustration of the duration ij  ~ ............................................................................

Figure 6 . 9 :

 69 Figure 6. 9 : The hourly distribution of delayed aircraft at departure (Scenario 1) ...............

Figure 6 .

 6 Figure 6. 10 : The hourly distribution of delayed aircraft at departure (Scenario 2) .............

  Figure 1.1: Localization of ground handling within the turnaround process

Figure 1 .

 1 Figure 1.3 displays examples of the different means to board/de-board passengers.

Figure 1 . 3 :

 13 Figure 1.3: Different devices to handle passengers boarding and de-boarding processes

Figure 1 .

 1 Figure 1.4 shows the luggage loading/unloading processes.

Figure 1 . 4 :

 14 Figure 1.4: Luggage loading/unloading processes

Figure 1

 1 Figure 1.5: Luggage loading/unloading processes

Figure 1 .

 1 Figure 1.6 represents two examples of the catering process.

Figure

  Figure 1.6: Catering process

Figure 1

 1 Figure 1.7: Different aircraft fuelling processes

Figure

  Figure 1.8: Sanitation process

Figure 1 .

 1 Figure 1.10: On-going de-icing process

Figure 1 .

 1 Figure 1.11:Push-back process

Figure 1 .

 1 Figure 1.16: Turnaround with loose ground handling activities

  The critical path of the ground handling process varies from a flight to another since it depends on the duration and sequencing of the operations. Considering the sequencing of the ground handling operations on the figure 1.20, a critical path could correspond to the following sequences: baggage unloading -fuelling -baggage loading or to the following sequence: passengers de-boarding -catering/cleaning -passengers boarding or finally to the following sequence: sanitation-potable water supply

  ), minimal and maximal values for the ground handling process are produced for different types of aircraft. The assumptions leading at these values are mentioned in Annex I.

Figure 1 .

 1 Figure 1.20: Candidate critical paths for ground handling process

  Figure 2.1) shows the turnaround charges supported at different European airports (London (Heathrow Airport)-LHR, Frankfurt-FRA, Vienne-VIE, Munich (Fraizjosef Strauss)-MUC, Madrid Barajas-MAD, Milan Malpensa-MXP, Zurich-ZRH, Charles De Gaulle (Airport de Paris)-CDG) by an Airbus A320 aircraft.

Figure2. 1 :

 1 Figure2. 1: Turnaround charges for an Airbus 320 at different airports 2013[Zurich Airport, 2013]

  travel after servicing aircraft i to be ready to service aircraft j and xi D is the distance that vehicle x must travel from its current position to the position of aircraft i. i T is the time at which the aircraft i expect the service. i b is the time at which the service begins on aircraft i. The assumed fixed travel speed of the service vehicle is V and x F is the time at which, according to the current scheduling, vehicle x becomes available. Here

kt

  is the flow time of the truck k , it denotes its busy time.The objectives were in order of importance to minimize: time of the service performed by the oil tuck on each flight in order to be able to deal with perturbations (accident, flight arrival delays …):

For

  example in a major European airport this problem is handled with two dispatch facilities which are run independently on each side of the airport (north N and south S) with separate fleets of identical vehicles with a capacity of 20 bags. Facility N handles approximately 4000 short transfer bags every day with 40 vehicles while facility S handles about 7000 bag transfers with 45 vehicles. There are 7 baggage handling stations. Statistics show that 50% of the connecting bags at facility N are directly delivered to the flights while 62% of the connecting bags are directly delivered to the flights at facility S. Statistics shown also that with the current operation the company has about 230 undelivered bags/day for the north facility and about 240 undelivered bags/day for the south facility.

  e. at least one of the two team members has the required skill), of service for job . The overall manpower scheduling problem consists of constructing a set of team, teams-to-jobs assignment and job start-times such that a balanced schedule which minimizes the number of unassigned jobs is made.M 1 and M 2 are arbitraries large constant matrices.

  windows constraints for job v are specified by (3.53). Inequalities (3.54) and (3.55) specify that if team k is visiting job location v , its service duration must fall within the shift hours of team k . Constraint (3.56) ensures that service periods between trips of team k are ordered sequentially. (3.58) and (3.59) are the internality constraints. The objective (3.43) is to maximize the number of assigned jobs (in reality, it is also important a balanced schedule, and it has been addressed in the solution methodology).

  i a and i b correspond to the earliest and the latest starting times for a task i . Each task i is divided into i r split tasks. Time ij t is the transportation time between each pair of tasks   j i, and the service time at task i . If team k has the required qualifications for performing task i , then 1 V k  operates within a working time window   k k f e , from a unique service centre at location 0 , common to all teams. The selected objective is here to minimize the total number of unassigned tasks while assigning to each team feasible sequences of activities along paths. Such feasible paths are shifts starting and ending at location 0 and obeying at time windows and skill requirements constraints. They are defined by the sequence of tasks they visit. Let 1  ijk x if task j is performed directly after task i by the team k and 0  ijk x otherwise. i s is an integer variable and defines the start time of the cleaning on the aircraft i .

  (3.62). Furthermore, constraint (3.63) is used to ensure that all shifts start in the service center. Constraints (3.64) ensure that no shifts are segmented. Any task visited by a team must be left again. The next four constraints deal with the time windows. First, a team can only be assigned to a task during their working hours (3.65)-(3.66). Next, the time needed for travelling between tasks is available (3.67). If a customer i is not visited, the scalar M , which has been chosen arbitrarily large, makes the corresponding constraints non-binding. Constraints (3.68) enforce the task time windows. Finally, constraints (3.69)-(3.70) are the integrality constraints. The introduction of a service start time removes the need for sub-tour elimination constraints, since each customer can only be serviced once during the scheduling horizon because ij t is positive. The formulated problem is NP-Hard.

Figure 4

 4 Figure 4.1 :The airport partners involved in the A-CDM

  Fight plan/ other data

  The collaborative management of flight updates: the flight arrival information is provided by the air traffic network management to the CDM airport which provides simultaneously flight departure information to the air traffic network management. The coordination between Air Traffic Flow and Capacity Management and airport operations of a CDM Airport should improve the efficiency of the ATFM slot management process for departing flights.

Figure

  Figure 4.2 : Connection of A-CDM with Ground Handling

Figure 4 . 3 :

 43 Figure 4.3 : Example of the set of ground handling activities for an A320 at Stockholm airportFigure 4.3 represents an example of ground handling activities sequence for an A320 at

  is sufficient to manage predictability of operations at the overall airport level. Then the possible milestones monitored by the ground handling coordinator are for an arriving flight operated by aircraft i: -time of start of arrival ground handling activities agh i start time of ground handling activity k on arriving aircraft i, agh ik d is the duration of ground handling activity k on aircraft i. In the same way, the possible milestones monitored by the ground handling coordinator are for a departing flight operated by aircraft i: -time of start of departure ground handling activities dgh i start time of ground handling activity k on departing aircraft i, dgh ik d is the duration of the ground handling activity k on aircraft i. All these time related variables and parameter adopt two values: their estimated value which can evolve and their effective value at completion.

Figure 4 . 4 :

 44 Figure 4.4:Introducing a Ground Handling CDM

  nominal number of teams (vehicle and staff) of type i necessary at period k to process scheduled arrivals. -k i r is the computed required number of teams of type i necessary at period k, to process schedules arrivals, included reserve, -k i A is the number of teams of type i necessary to handle flight arrivals at parking stands during the previous half an hour which are supposed to be processed before period k and k A

  nominal number of teams (vehicle and staff) of type i necessary at period k to process departures. -k i r is the computed required number of teams of type i necessary at period kto process departures, included reserve. -k i D is the number of teams of type i necessary to handle flight departures at parking stands during the previous half an hour which are supposed to be processed before period k and k D

Figure 4

 4 Figure 4.6 : Three-levels organization of ground handling management

Figure 4

 4 Figure 4.7 : RdP representation of GHUi's operations

Figure 4 . 8 :

 48 Figure 4.8 : RdP representation of operations by a GHMj

Figure 4 . 9 :

 49 Figure 4.9 : RdP representation of operations by a GHC

  flight arrivals occur according to nominal schedules, -the ground handling activities of all arriving or departing aircraft are only performed at parking gates, -the ground handling activities follow the same sequences for every considered aircraft -the GHC knows the technical characteristics of the different equipment and fleets, -the GHC has reference values for travel times and elementary ground handling delays, -It is assumed by the GHC that all routes for each type of vehicle start and end at the corresponding base.

  end time of ground handling activities for aircraft k at its parking stand.

  of route l travelled by a vehicle of type i .k S :parking stand of aircraft k . of aircraft in competition with aircraft k to use vehicle type i .i pq  : average travel time, i.e. the time it takes to drive with vehicle of type i from aircraft parking stand p and to aircraft parking stand q .i p  : average travel time it takes to drive from the aircraft parking stand p to the base of the vehicle of type i date of task j performed by a vehicle of type i on aircraft k .

  number l with vehicle type i covers task j on aircraft k right after performing it on aircraft'

  ik j C and k T are positive real decision variables. The first variables correspond to the covering of aircraft ground handling needs by service routes and the second variables correspond to the time scheduling of activities along the service routes. Each service route is a duty to be performed by a corresponding service team composed of a service vehicle and a service team.The size of the problem is given by:-the number of decision variables composed of

  The nominal arrival and departure schedules and the parking positions of aircraft

  task t has a release time t i b from which it can be started and a completion time t j f . t i b is the time at which the aircraft i , t k I i  , is expected to request service.

  for the Proposed Global Approach 117

  for the Proposed Global Approach 120

Figure 5

 5 Figure 5.3 : 01 /08/2007 Palma de Mallorca Airport Aircraft hourly traffic

Figure 5 .

 5 Figure 5.4 represents the hourly distribution of aircraft the departure delays resulting from the proposed heuristic.

Figure 5 . 4 :

 54 Figure 5. 4 : Hourly delays distribution resulting from the proposed heuristic

Figure 5 . 5 :

 55 Figure 5.5 : Nominal composition of ground handling fleets

Figure 5

 5 Figure 5.6: Number of the resources required for each ground handling activities each of period of time

  the flights announced to land within the next half hour. Aircraft within five minutes to land have been supposed to maintain the previous assignment solution. No flight directed towards the considered airport has duration less than forty minutes. Then the real departure times

Figure 5 . 7 :

 57 Figure 5. 7 : Hourly delays distribution resulting from the proposed heuristic

Figure 6 . 1 :

 61 Figure 6.1 : Ground handling management under disruption

Figure 6 . 2 :

 62 Figure 6.2 : Operational uncertainty during airport disruption

  Figure 6.3 : Representation of a fuzzy dual number

Figure 6 . 4 :

 64 Figure 6.4 : Examples of shapes fro fuzzy dual numbers

  Figures 6.4 and 6.5 display different partial orders between pairs of dual fuzzy numbers and inequalities between fuzzy dual numbers are quite different from those used with classical fuzzy numbers.

  2

Figure 6 . 5 :

 65 Figure 6.5 : Example of inequalities (weak and strong) between fuzzy dual numbers

  an aircraft a(i) associated to a flight i, iI, (I=I A I D , I A is the set of scheduled arriving flights during the next management horizon flights and I D is the set of scheduled departing flights during the same period) by a specific ground handling service provider of the proposed heuristic consists in performing an initial ordering of the flights scheduled to arrive within the next ground handling management horizon in accordance with their current predicted arrival time a i t ˆat their assigned parking amended by considering their criticality. To each arriving flight iI A , can be assigned the difference either real numbers or fuzzy dual numbers, where a i t ˆis provided by the ATC. In the second case, this corresponds practically to a time window. Each arriving flight will cope with two types of operational constraints: -Connection constraints when arriving passengers must reach without delay others departing flights. -Departure schedule when the arriving aircraft must be ready to start a new flight with a tight schedule.

Figure 6 . 7 :

 67 Figure 6.7 : Example of ground handling activities' sequencing When considering connection constraints, let i C be the set of departing flights connected to arriving flight i. The time margin between flight i and each flight j in C i is given by:  i ij

  or fuzzy dual numbers. Symmetrically, each departing flight must cope with operational constraints related with successive flights by the same aircraft and flight connections for passengers and cargo.

  each flight i, either arriving or departing, is assigned a time parameter i  such as: fuzzy dual pseudo norm defined in the appendix. Then the flights, either arriving or departing, present in the considered period of operation can be ranked according

Figure 6 .

 6 Figure6.9and 6.10 displays the hourly distribution of delayed aircraft at departure resulting from the application of the proposed approach for the two scenarios. It appears that the impact

Figure 6 . 9 :

 69 Figure 6.9 : The hourly distribution of delayed aircraft at departure (Scenario 1)

II

  Figure I. 1: Full Servicing Turnaround Charts for an A320-100/ A320-200

  start are associated to each costumer C i  . i e is the earliest service time and i l is the latest service time allowed to serve the costumer i . Each arc has a cost ij C and a travel time ij t . At each costumer, the service start time must be within the time window. Each vehicle must leave and return to the depot after servicing all its customers. k j ix , Equal 1 if vehicle k served the costumer j after serving the costumer i, and 0 otherwise. k i b is the start time at which the vehicle k begin to serve the costumer i. so the VRPTW consists to find a route with a least cost and respecting the following constraints:1. Each costumer is served exactly once by exacting one vehicle respecting the time window.2. All vehicle routes start and end at the depot.

[

  Antes and al, 1995] :Antes, J., Derigs, U., 1995. A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows. Technical Report, Lehrstuhl fur Wirtschaftsinformatik und Operations Research, Universitat zu Koln.

  . A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows.Technical Report, CRT-95-84, Centre de recherche sur les transports, Montréal. [Baker and al, 1989] :Baker, E., Schaffer, J., 1989. Solution improvement heuristics for the vehicle routing and scheduling problem with time windows constraints. American Journal of Mathematics and Management Sciences 6 (3,4), 261-300. [Chiang and al, 1996] :Chiang, W., Russell, R., 1996. Simulated annealing metaheuristics for the vehicle routing problem with time windows.Annals ofOperations Research 63, 3-27. [Christofides and al, 1984] :Christofides, N., Beasley, N., 1984. The period routing problem.Networks 14, 237-241.

Figure 1 :

 1 Figure 1: Petri net example. Places, transitions and arcs: Places are represented with circles and transitions are represented with bars. The arcs are directed from places to transitions or from transitions to places. The places contain tokens that travel through the net depending on the firing of a transition. A place p is said to be an input place to a transition t if an arc is directed from p to

Definition 2 (

 2 Marking)The marking i m of a place P p i  is a non-negative quantity representing the number of tokens in the place at a given state of the Petri net. The marking of the Petri net is defined as the function set of places to the set of non-negative integers. It is also defined as a vector th j state of the net. j M contains the marking of all the places and the initial marking is denoted by 0 M .

Figure

Definition 3 (

 3 Reachability graph):The reachability graph has the marking of the Petri net (or state of the Petri net) as a node. An arc of the graph joining i M with j M represents the transition when firing takes the Petri net from the marking (state) i M to the marking j M . The reachability graph of the Petri net in figure 1 is presented in figure 3.

Figure 3 :

 3 Figure 3:Reachability graph

  information regarding token conservation and transition firing sequences that leave the marking of the net unchanged. These concepts are used to assess the overall liveness and boundedness of the net. of the arc from place j p to transition j t . The incidence matrix A of a Petri net has T number of rows and P number of columns.

  Net-invariants) Let A be the incidence matrix. A P-invariant is a

  liveness of the Petri net model is assessed on Theorem 2 by means of the T-invariants of the incidence matrix. A Petri net model is covered by T-invariants if and only if, for each transition t in the net, there exists a positive T-invariant y such that   0  t y . This is a necessary condition but not sufficient. The liveness assessment by the use of T-invariants is still an open problem.

Figure V. 1 :

 1 Figure V.1: Characteristic Function of a Crisp Set

Figure

  Figure V.2: Examples of Fuzzy Set

Figure V. 7 :

 7 Figure V.7: Defuzzification using the Centre of Gravity Approach

  Mallorca Airport (airport code PMI) was originally created t handle the island's postal service and now over 20 million people each year. Known in English as Majorca, Mallorca Airport has one terminal with four modules, ladled A, B, C and D branching from it. Although located 8 kilometres from the capital. Mallorca Airport is owned by Aena Aeropuertoss. Mallorca Airport has ISO certification as well as continued noise reduction and insulation practices with surrounding residential areas. Located in the Mediterranean Sea, the island of Mallorca is the largest of the Balearic Islands and has 550 kilometres of coastline. It receives 11 million visitors annually with Germany accounting for the largest number of travellers while Spain and the UK follow close behind.

Figure VI. 1 :

 1 Figure VI. 1: Palma de Mallorca Airport

  Then, table 1.1enumerates the different aircraft related airport activities classified into categories depending on where they are performed.

	Passenger or freight terminal	Airside
	 Baggage check	 Ramp services :
	 Baggage handling	 Supervision
	 Ticketing and check-in	 Marshalling
	 Passenger boarding/de-boarding	 Start-up
	 Transit passenger handling	 Moving/towing aircraft
	 Elderly and disabled persons	 Safety measures
	 Information systems	 On-ramp aircraft servicing:
	 Government controls	 Repair faults
	 Load control	 Fuelling
	 Security	 Wheel and tire check
	 Cargo	 Ground power supply
		 De-icing
		 Cooling/heating
		 Toilet servicing
		 Potable water supply
		 Demineralised water
		 Routine maintenance
		 Non-routine maintenance
		 Cleaning of cockpit windows, wing,
		nacelles and cabin windows
		 On-board servicing:
		 Cleaning
		 Catering
		 In-flight entertainment
		 Minor servicing of cabin fittings
		 Alteration of seat configuration
		 External ramp equipment:
		 Passenger steps
		 Catering loaders
		 Cargo loaders
		 Mail and loading equipment
		 Crew steps on all freight aircraft

  Boeing 777 Manual) while figure 1.19 displays nominal durations for the ground handling activities for an A330-300 (source: Airbus A330 Manual).

		Figure 1.18 displays nominal durations for the ground handling activities for a B777-200
	Figure 1.17:Turnaround with tight ground handling activities Available Time Right door no 2 Right door no 4 0 10 20 Deboarding/Boarding AT L1 Position passenger Bridges or stairs 1,0 Deplane passengers 7,5 Service cabin -AFT LH Door 26,5 Service galleys -two trucks 29,5 27,0 Deboarding/Boarding AT L2 Headcounting (source: Passengers Services Board passengers 12,5 Catering AT R1 Remove passenger bridges 1,0 Catering AT R2	Time-Minutes 30 40	Right door no 1 50	60	70
	Cargo/ Baggage/ Handling Airplane Servicing	Unload fwd Compartment Unload aft Compartment unload and load bulk compartment load aft compartment Catering AT R4 Cleaning Cargo FWD CC Cargo AFT CC Bulk Refuelling load fwd compartment Potable water servicing 18,0 14,0 41,0 14,0 18,0 Fuel airplane Toilet servicing 23,0 Service potable Service toilets 15,0		Available Time Figure 1.19: Typical durations of handling operations Airbus 330-300
		water	17,0
		Push back	----
			0	5	10	15	20	25	30	35	40	45
							Time -Minutes
					Figure 1.18: Typical durations of handling operations Boeing 777-200 [Boeing, 2009]
						27

Table 2

 2

	.1 shows the results of a recent research [Norman and al. 2013]concerning how ground
	handling organization varies from an airport to another (this research considers 72 airports
	from all over the world).
	Activity	Airport Airlines Airport	Airline	Not
			handling company	handling company	applicable
	Baggage handling inbound	15.00% 31.00% 11.00%	41.00%	2.00%
	Baggage handling outbound	15.69% 32.35% 10.78%	40.20%	0.98%
	Passenger check-in	11.01% 38.53% 11.01%	39.53%	0.92%
	Transit passenger handling	10.42% 31.25% 10.42%	34.38%	13.54%
	disabled passengers services	18.87% 30.19%	9.43%	40.57%	0.94%
	Ground transportation systems	56.63% 3.61%	16.87%	12.05%	10.84%
	Airside Ramp services	26.32% 24.21%	8.42%	40.00%	1.05%
	Airside Supervision	67.82% 10.34%	3.45%	18.39%	0.00%
	Airside Marshalling	36.73% 24.49%	7.14%	30.61%	1.02%
	Airside Start up	22.68% 28.87%	6.19%	37.11%	5.15%
	Airside Ramp safety control	65.96% 17.02%	0.00%	15.96%	1.06%
	Airside On-ramp aircraft servicing	15.05% 34.41%	4.30%	39.78%	6.45%
	Airside Fuelling	15.29% 14.12% 27.06%	41.18%	2.35%
	Airside Wheel and tire check	4.12% 46.39%	6.19%	41.24%	2.06%

  The table below is the results from a statistical study of the departure delays encountered by a

	European domestic airline system (Lufthansa City Line) in 2008.
	REASON	EXAMPLES	PERCENTAGE
	Rotation	Delayed flight cycles	30%
	ATFM/ATC	Restrictions according to saturated ATC sectors,	25%
		traffic flow restrictions
	Airport Authorities Problems due to limited runway capacities, limited	15%
		availability of parking positions, security, etc.
	Ground handling Delayed ground processes (late passengers, handling	10%
		agent availability)
	Technical	Malfunction of aircraft systems	3%
	problems
	Weather conditions Adverse weather conditions (strong rain, snow,	2%
		strong wind, etc.)
	Other	Aircraft damage, strike, communication problems,	15%
		etc.
		Table2. 2: Departure delay causes

  25) Relation (3.13) consider the objective of minimizing the number of undelivered bags while constraint (3.14) sets i z to 1 if bag i is not delivered on time to its flight or handling station, Constraints (3.15) and (3.16) are depot starting and ending conditions (each route should leave the depot once and return to it once). Constraint (3.17) is a vehicle capacity constraint which must be satisfied on all routes. Constraint (3.18) is a flow conservation constraint at node i for vehicle k performing route r. Constraint (3.19) ensures that if edge (i, j) is used by vehicle k on route r, then the completion time at j is greater than the departure time at node i

plus the travel time between i and j and drop off time at j. Constraints (3.20) are time windows constraints and constraints (3.21) insure that new routes cannot be started before the previous routes have ended.

Constraint (3.22)

ensures that vehicle k cannot start route r until its corresponding baggage is available.

  considered a flight as a job. There are n jobs by the set , which denotes the earliest and latest starting times for a job  .

	duration  p and     b a   d D , , 1   is a set of d drivers, and	L		 1  ,	,	l		is a set of l loaders in a day, where the
	total workers is the set	W		D		L	. Worker	i 	W	is described by his/her shift hours   i i e t , ,
	and a set of kills represented by aircraft type/configuration combinations,	S  	F	. Worker i
	and worker j and worker  i j	,	j		W		may have overlapping skills, i.e.,	S	i	 j S		
													J		 1  , ,	 n	,
	where each job  is described by an aircraft/ configuration combination	f  	F	, a service

Table 5

 5

		2. Refuelling
		(9 minutes)
	0. Arrival	1. De-boarding (7 minutes)	4. Boarding (15 minutes)	5. Departure
		3. Catering
		(10 minutes)
		Figure 5.1 : Structure and duration of the ground handling activities
		Figure 5.2 : Vehicles routes

.2 provides the corresponding assignment solution which is graphically represented in figure 5.2.

Table 5

 5

	.3. It represents the number of the aircraft

  It is supposed here that it is possible considering the perturbed situation for all future ground handling related events to propose earliest and latest expected completion times, min

																													t
	and max t to construct a fuzzy dual triangular completion time number t ~where:
	R	(	t	)		( t	min		t	max	)	/	2	and	D	(	t	)		( t	max		t	min	)	/	2	(6.12)
	It is also supposed that the duration of each type of ground handling task can be represented
	in the same way by a fuzzy dual number d ~:
	R		( d	)		(	d	min		d	max	)	/	2	and				(	)	(	max	min	)	/	2

  Table 6.1.It is considered that during and after this period the airside capacity of the airport is insufficient, including taxiing capacity with the appearence of queues of taxiing aircraft, parking positions with apron congestion and saturated ground handling capacity. In that conditions, transfer times for aircraft and ground handling units activities durations are subject to large uncertainties. Here it has been considered two scenarios for the uncertainty: in the first one additional delays are between 0% and 40% of the original duration between 11a.m. and 2 p.m. with return to nominal situation afterwards, in the second scenario additional delays are between 0% and 40% of the original duration between 11a.m. and noon,

	between 20% and 60% of the original duration between noon and 1:30 p.m., between 0% and
	40% of the original duration between 1:30 p.m. and 2:30 p.m. with return to nominal
	situation afterwards.
		10h11h 11h12h 12h13h 13h14h 14h15h 15h16h
	Arrival	20 + 30	34 +15	25	7	15	15
	traffic
	Scheduled	17	19	28+15	17+20	17+10	17
	departures
			Table6. 1 : Effective arrivals and scheduled departures

of aircraft departure delay Time

	Number of aicraft departure delay
		00	1:00	2:00	3:00	4:00	5:00	6:00	7:00	8:00	9:00	10:00	11:00	13:00	14:00	15:00	16:00	17:00	18:00	19:00	20:00	21:00	22:00	23:00	0:00
													Time
		35
		30
		25
		20
		15
		10
	Number	0 5
		0:00	1:00	2:00	3:00	4:00	5:00	6:00	7:00	8:00	9:00	10:00	11:00	13:00	14:00	15:00	16:00	17:00	18:00	19:00	20:00	21:00	22:00	23:00	0:00

Table 1

 1 presents several typical interpretations for transitions and places.

	Input place	Transitions	Output places
	Preconditions	Event	Post conditions
	Input data	Computation step	Output data
	Input signal	Signal processor	Output signal
	Resources	Task or job	Resource released
	needed	Clause in logic	Conclusion
	Conditions	Processor	Buffer
	Buffers

Table 1 : Modelling interpretations of transitions and places

 1

A simple Petri net example is presented in figure

1

. This example is used later to define additional Petri net characteristics.

BIBLIOGRAPHY ANNEX I TYPICAL TIMES FOR GROUND HANDLING ACTIVITIES AT RAMP