A multi-objective optimization approach to the ground handling scheduling problem

Author

Padrón Astorga, Silvia

Director

Ramos González, Juan José

Guimarans Serrano, Daniel

Date of defense

2014-07-22

ISBN

9788449048227

Legal Deposit

B-2942-2015

Pages

135 p.



Department/Institute

Universitat Autònoma de Barcelona. Departament de Telecomunicació i Enginyeria de Sistemes

Abstract

El tiempo de escala o turnaround es uno de los procesos aeroportuarios más críticos y se define como el período de tiempo en que la aeronave está en rampa, entre un vuelo de llegada y uno de salida. Durante el turnaround se realizan un conjunto de operaciones necesarias para preparar un avión para el próximo vuelo. Estas tareas son interdependientes y cada operación es una potencial fuente de demoras para el resto de las actividades, así como para otros procesos dentro del aeropuerto. Además, las decisiones de planificación que se toman para cada operación afectan la programación de otras tareas y el rendimiento de sus recursos. La falta de integración entre las diferentes operaciones y un uso ineficiente de los recursos durante el turnaround son causas importantes de retrasos en los vuelos. Esta tesis tiene como objetivo contribuir a la eficiencia de las operaciones de asistencia en tierra durante el turnaround, abordando el problema desde una perspectiva global. Con este fin se han considerado diferentes operaciones, así como las relaciones de precedencia entre estas, en lugar de programar cada actividad por separado. Se propone una aproximación multiobjetivo para realizar la planificación de los vehículos que dan servicio a las aeronaves en un aeropuerto durante un día. La solución al problema consiste en obtener un plan para estos vehículos que cumpla con las restricciones de tiempo, de precedencia y con las limitaciones de capacidad. Además de obtener una programación optimizada para cada actividad, es importante tener en cuenta el impacto que estas tienen en otras tareas. De esta manera, podemos integrar las decisiones realizadas para cada operación y contribuir a optimizar el proceso global. Dos objetivos han sido definidos con este fin: (I) minimizar el tiempo de espera para iniciar una operación y la reducción de las ventanas de tiempo disponibles, usando los vehículos eficientemente; y (II) minimizar el tiempo total de finalización del turnaround. Para resolver el problema multiobjetivo se ha desarrollado un nuevo método llamado Sequence Iterative Method (SIM) y se obtiene un rango de soluciones, las cuales representan el mejor compromiso entre los dos objetivos. Mediante un esquema de descomposición basado en Job Shop Scheduling Problem, el problema de optimización es desglosado. Este esquema proporciona un método consistente para resolverlo completo, simplificando el modelo y el proceso de resolución. En primer lugar, se calcula una ventana de tiempo para cada operación de acuerdo con las restricciones temporales y de precedencia. Un Vehicle Routing Problem with Time Windows (VRPTW) es identificado para cada tipo de vehículo involucrado, lo que da lugar a múltiples VRPTWs. Estos se resuelven de forma individual y las decisiones tomadas para cada problema de enrutamiento se propagan a los demás VRPTWs a través de reducciones en las ventanas de tiempo disponibles. Las principales funciones de la aproximación son modeladas e implementadas en Constraint Programming (CP). Además, CP se emplea en combinación con Variable Neighborhood Descent (VND) y Large Neighborhood Search (LNS) como metodología para resolver los VRPTWs. El conocido método Insertion Heuristic se utilizó para encontrar una primera solución de forma rápida, la cual se mejora posteriormente utilizando la metodología. Por último, una versión de la aproximación es propuesta con el objetivo de aplicar una exploración más exhaustiva para encontrar las soluciones de Pareto. En este caso, estas se obtienen mediante el método de Insertion Heuristic y solo las más prometedoras son mejoradas con la metodología. Se sugieren dos estrategias para determinar qué soluciones son las más prometedoras y estas reglas pueden ser también empleadas para finalmente seleccionar la mejor a implementar.


Turnaround is one of the most critical airport processes. It is defined as the period of time the aircraft is on the ramp between an inbound and outbound flight, and different ground handling operations are performed. Ground handling comprises a set of interrelated services necessary to prepare an aircraft for the next flight. Since ground handling tasks are very interdependent, each operation is a potential source of delays which could be easily propagated to other operations and other airport processes. Moreover, planning decisions about each vehicle required to perform an operation affect the scheduling of other activities and the performance of other resources. The lack of integration of the different activities and an inefficient use of the resources during turnaround are important causes of flight delays. This thesis aims to contribute to the operational efficiency of ground handling facing the problem from a global perspective. Different operations and their interconnections have been considered instead of scheduling each activity in isolation. We introduce a multi-objective approach for scheduling the ground handling vehicles that perform this set of related activities. Solving this problem consists of obtaining a schedule for the vehicles that service aircraft at an airport during one working day. The schedule has to satisfy temporal, precedence, and capacity constraints. Besides obtaining optimized schedules for each activity, it is important to take into account the impact on other tasks. This way, we can integrate the scheduling decisions made for each service and contribute to optimize the overall ground handling process. Two objectives are defined in order to integrate the scheduling decisions : (i) minimizing the waiting time before an operation starts and the total reduction of the corresponding time windows, using the vehicles efficiently; and (ii) minimizing the total completion time of the turnarounds. A new method called Sequence Iterative Method (SIM) has been developed to address the multi-objective problem. With the aim to achieve a more flexible and accurate decision process, a range of solutions representing the best compromise between the two objectives is obtained. The ground handling problem is separated using a workcenter-based decomposition schema. This schema provides a consistent method to solve the complete problem and simplifies the model and the solution process. First, a planning problem is solved and a time window for each operation is calculated according to the temporal and precedence restrictions. One Vehicle Routing Problem with Time Windows (VRPTW) is identified for each type of vehicle involved, which leads to multiple VRPTWs. These are solved individually and decisions made on each routing problem are propagated to the other VRPTWs through reductions on the available time windows. The main features are modeled and implemented in Constraint Programming (CP). Furthermore, CP is used in combination with Variable Neighborhood Descent (VND) and Large Neighborhood Search (LNS) as a part of a hybrid methodology to solve each of the routing problems. The well-known Insertion Heuristics method has been applied to produce a quick first solution which is later improved using the methodology. Finally, a version of the approach is proposed with the goal to allow a more exhaustive exploration to find Pareto solutions. In this case, solutions are obtained using the Insertion Heuristic and just the most promising are improved by the methodology. Two strategies are suggested to determine which solutions are the most promising and these rules can be also employed to guide the decision maker towards the selection of the best schedule to implement.

Keywords

Airtransportation; Multi-objective optimization; Constraint programming

Subjects

68 - Industries, crafts and trades for finished or assembled articles

Knowledge Area

Tecnologies

Documents

spa1de1.pdf

763.5Kb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)