Trade Space Megacities. Los problemas de diseño de un Sistema Nacional Aeroespacial.

Aprovechando que las últimas entradas han sido sobre cuestiones aeroespaciales no puedo dejar de comentar sobre este paper que he visto hoy dónde hablan de la complejidad computacional y algorítmica de problemas de ingeniería aeroespacial (ya hablamos en una entrada anterior sobre rutas aéreas y complejidad, desde otro punto de vista).

Concretamente hablan del problema de sectorización del espacio aéreo. Se trata de rediseñar una partición del espacio aéreo en EEUU, que se adapte a las nuevas rutas aéreas, de tal manera que no se sobrecargue el trabajo de los controladores.

Título. Local redesigning of Aerospace sectors.


In this paper we study the Airspace Sectorization Problem (ASP) where the goal is to find an optimal partition (sectorization) of the airspace into a certain number of sectors, each managed by an air trafic controller. The objective of the ASP is to fi nd a “well-balanced” sectorization that distributes
the workload evenly among the controllers. We formulate the ASP as a partitioning problem of a set of moving points in a polygonal domain. In addition to the requirement of balancing the workload, we introduce restrictions on the geometry of the sectorization which come from the Air Trafic Management aspects.

We investigate several versions of the problem that arise from dif erent de nitions of the notion of the workload and various choices of geometric restrictions on the sectorization. We conclude that most of the formulations of the problem, except maybe in some trivial cases, are NP-hard. Finally, we propose a Local Redesigning Method (LRM), a heuristic algorithm that rebalances a given sectorization by adjusting the boundaries of the sectors. We evaluate LRM experimentally on synthetically generated scenarios as well as on the real historical trac data. We demonstrate that the sectorizations produced by our method are superior in comparison with the current sectorizations of the US airspace.

Nunca había visto la teoría de complejidad computacional aplicada a este contexto aeroespacial.  ¿ NP-Hard ? Más dificil todavia es la cuestión de los salarios de los controladores…


The current design of the National Airspace System (NAS) was developed based on ight routes that were formed historically. Over the years, the demand and the geometry of the routes have changed dramatically, yet the NAS has undergone little change. As a consequence, the current sectorization is no longer able to accommodate the rapidly increasing demand. The problem of designing a exible and dynamic airspace architecture that is able to adapt to changing trac ows is addressed by the Dynamic Airspace Con guration (DAC) project as a part of the Next Generation Air Transportation System (NextGen) [1]. The NAS is partitioned into 22 Air Route Trafic Control Centers, each subdivided into sectors, which are overseen by air trac controllers. The maximum workload that air trac controllers can safely handle results in a limitation on the capacities of the sectors.

If the changing trafic causes the demand on a sector to exceed its capacity, the sector will not be able to accommodate all the incoming flights. This will lead to some flights being rerouted around the congested area, and others to be delayed. There are two basic approaches to handling changes in trafic.

–The fi rst one is to design a new sectorization from scratch. Such methods concentrate on new trafic patterns, while discarding the old sectorization. Examples of this approach include: a cell-based Mixed Integer Programming (MIP) model [2, 3]; a sectorization method using binary space partitions [4, 5]; a Voronoi diagram method [6]; a graph partitioning method [7], etc. While a clean-sheet sectorization design provides a wide range for nding an optimal solution, it is undesirable due to a human factor; it is important for controllers to be familiar with the geometry of sectors and trafic patterns.

–The second approach is to perform a local rebalancing of the existing sectorization without introducing dramatic changes to the sectors. Klein et al. [8] present an algorithm that shifts pre-speci ed thin subsectors between adjacent sectors to rebalance them. A local method for adjusting the boundaries of sectors that provides “outs” (or extra space) around weather constraints is proposed by Drew [9]. This method uses a force-based approach to adjust the boundaries in order to improve the capacities of the sectors that are most impacted by weather. The Voronoi method presented by Xue [6] includes a local rebalancing option as well as a clean-sheet design option; it adjusts the design of sectors by iteratively moving the Voronoi centers. The existing sectorization (the one created by applying the Voronoi method in clean-sheet mode) is used as the seed for a genetic algorithm that adapts the sectorization to the new demand. Local methods may change the topology of the design, including changes in the number of sectors. For instance, a pair of adjacent sectors may be combined into one, or a single sector may be split into two. Sector combination methods, based on computing predicted capacity gaps and then greedily combining pairs of sectors having the largest such gaps, have been proposed and examined in experiments of [10].

In this paper we discuss theoretical aspects of the ASP and present a new approach to the problem of redesigning sectorizations by local adjustments of the sector boundaries. We present a Local Redesigning Method
(LRM), a highly customizable multi-criteria optimization heuristic. We have developed GeoSect-Local (a complement to GeoSect sectorization tool introduced in [4, 5]) that performs LRM adjustments to an input sectorization. The input sectorization can be any partition of the airspace region of interest, including current NAS sectorization, manually entered sectors, or the output of any other sectorization method, such as the top-down GeoSect clean-sheet method.


Una respuesta to “Trade Space Megacities. Los problemas de diseño de un Sistema Nacional Aeroespacial.”

  1. Bedemand Slagelse Says:

    Heya! I realize this is kind of off-topic but I had to ask.
    Does building a well-established website like yours
    require a massive amount work? I’m brand new to writing a blog but I do write in my journal daily.
    I’d like to start a blog so I can easily share my personal experience and feelings online.
    Please let me know if you have any recommendations or tips for new aspiring bloggers.

    Appreciate it!

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )


Conectando a %s

A %d blogueros les gusta esto: