[Apdio] Palestras do SEOOR - Centro ALGORITMI - UMinho (3ªf 09.03, 14h00)

[Cláudio Alves <claudio@dps.uminho.pt>]

 

Convidam-se os interessados a participar na próxima palestra do SEOOR - Grupo de Engenharia de Sistemas, Optimização e Investigação Operacional do Centro de Investigação ALGORITMI da Universidade do Minho.

 

ORADOR:

Raed Mansi

Doutorado em Informática pela Universidade de Valenciennes et du Hainaut-Cambrésis (França)

(Especialidade em Automação e Informática dos Sistemas Industriais e Humanos)

Actualmente Investigador pós-doutorando no SEOOR

 

TÍTULO: Exact hybrid algorithms and matheuristics for knapsack variants and disruption management in the airline industry

 

DATA  : 09 de Março (3ªf), 14h00

LOCAL : Anfiteatro EEII.024 (Edifício da Escola de Engenharia - Gualtar)

 

RESUMO:

In the first part of this talk, two important variants of the knapsack problem will be addressed: the bilevel knapsack problem and the multiple-choice multidimensional knapsack problem. For the first problem, we will present new state-of-the art algorithms based on the hybridization of exact dynamic and integer programming methods and on new recursive rules. Additionally, we will show how the problem can be solved as a sequence of standard knapsack problems.

 

Iterative hybrid heuristics based on relaxations will be presented for solving the multiple-choice multidimensional knapsack problem. These heuristics converge theoretically towards an optimal solution of the problem by solving a series of sub-problems of small size obtained by exploiting the information of relaxations. Our methods are improved by fixing variables and adding cuts and pseudo-cuts induced by local search and relaxations. These added constraints are used to reduce the search space. The results show that the heuristics converge quickly to good solutions.

 

The second part of the talk will be devoted to the problem of Disruption Management in the Airline Industry (DMAI).The goal of this problem is to resume normal operations as quickly as possible during the recovery period while minimizing the resulting costs and the potential impacts to passengers. In cases of disruptions, DMAI aims to reassign aircraft and passengers simultaneously rather than according to the natural hierarchy of aircraft, crews and passengers. We will consider many types of practical disruptions such as mechanical failures, personnel strikes or inclement weather. Even finding a feasible flight schedule is a hard problem.

 

The solution method that will be discussed is an oscillation strategy heuristic combined with mathematical programming. Our numerical results show the effectiveness of this method, which produced the best results known for some of the most demanding real-life instances of the problem. With these results, we ranked 2nd in the 6th international challenge of the French Society of Operations Research and Decision Analysis.

 

 

Saudações cordiais,

 

Cláudio Alves

DPS, EENG, UM