On a Geometric Graph-Covering Problem Related to Optimal Safaty-Landing-Site Location
Authors:
Autores
| Person role | Person | |
|---|---|---|
|
7607 |
603,3281
|
|
|
7606 |
603,3281
|
Informations:
Pesc publication
O desenvolvimento de sistemas de transporte aéreo urbano tem atraído o interesse de grandes empresas nos últimos anos. Um problema que surge do seu desenvolvimento é a necessidade de locais para pouso de emergência, que devem cumprir certas exigências de segurança. Neste contexto, propomos formulações de programação inteira para o problema de localização ótima de Pontos de Pouso de Emergência (Safety Landing Sites – SLSs). Foram desenvolvidos dois modelos para o problema. O primeiro modelo, baseado em recobrimento de conjuntos, considera que os locais candidatos são finitos e representados por pontos discretos, e é formulado como um problema de programação linear binária. O segundo modelo, trata do caso mais geral, no qual os SLS devem estar contidos em regiões convexas, sendo formulado como um problema de programação inteira mista com restrições cônicas de segunda ordem. Foi desenvolvido um algoritmo gerador de instâncias, as quais foram utilizadas nos experimentos numéricos que validam a aplicabilidade dos modelos. Por fim, introduzimos o strong fixing para os dois modelos, uma técnica que permite fixar o valor de variáveis, aprimorando a técnica clássica conhecida como reduced-cost fixing. O strong fixing demonstrou ser altamente eficaz na redução do tamanho de problemas inteiros nos nossos experimentos.
The development of urban air transportation systems has attracted the interest of major companies in recent years. One problem that arises from this initiative is the need for emergency landing sites, which must meet certain safety requirements. In this context, we propose integer-programming formulations for the problem of optimal location of Safety-Landing Sites (SLSs). Two models were developed for the problem. The first model, based on set covering, considers that candidate sites are finite and represented by discrete points, and is formulated as a binary linear programming problem. The second model considers a more general case, in which the SLS must be contained in convex regions, and is formulated as a mixed-integer second-order cone programming problem. An instance generator algorithm was developed and used in the numerical experiments to validate the applicability of the models. Finally, we introduce ``strong fixing'' for both models, a technique that allows fixing the value of variables, enhancing the classical technique of reduced-cost fixing. The strong-fixing procedure has proven to be highly effective in reducing the size of the resulting integer problems in our experiments.