Capacitated Routing on a Planar Partition

A planar partition of the airspace is a finite collection of non-overlapping polygonal cells $\mathcal{P} = \{C_1, C_2, \ldots, C_k\}$ whose union covers the operating region. Each cell carries a capacity $\kappa(C_i) \in \mathbb{Z}_{\geq 0}$, the maximum number of aircraft permitted to occupy $C_i$ at the same time.

A flight's trajectory is a polyline $\gamma$. Routing on $\mathcal{P}$ replaces $\gamma$ by its cell sequence: the ordered list of cells $\gamma$ visits, with consecutive duplicates collapsed.

To compute the cell sequence efficiently when $k$ is large, query the STRtree on $\mathcal{P}$ with the bounding box of $\gamma$ to obtain the candidate cells, then test which candidates the polyline actually crosses, in order.

For example, with the $2 \times 2$ grid partition

$$C_1 = [0,4]\times[0,4], \quad C_2 = [4,8]\times[0,4], \quad C_3 = [0,4]\times[4,8], \quad C_4 = [4,8]\times[4,8],$$

the polyline $(1,1) \to (6,3) \to (7,6)$ starts in $C_1$, crosses $x=4$ into $C_2$, then crosses $y=4$ into $C_4$. The cell sequence is

$$C_1 \to C_2 \to C_4.$$

Two cells are adjacent in the cell graph if they share a positive-length edge. In the grid above, $C_1$ is adjacent to $C_2$ and $C_3$ but not to $C_4$, which it touches only at a corner.