Optimal Location of Safety Landing Sites
Liding Xu
Claudia D’Ambrosio, Leo Liberti, Sonia Vanier

OptimiX, LIX, École polytechniqueliding.xu@polytechnique.edu

July, EURO 2021

1/22

Urban air mobility

Urban air mobility (UAM) is driven by advancements inbattery, distributed electric propulsion, and autonomy
technologies.
Electric vertical takeoff and landing (eVTOL) aircraft, areexpected to be safer, quieter, and less expensive tooperate than helicopters.
We study the safety design of UAM networks: install safety
landing sites (SLSs) for eVTOLs.

2/22

Outline

Problem description.
Mathematical models and formulations.
Algorithms.
Numerical experiments.
Conclusion.

3/22

BackgroundeVTOLs would exploit the vertical space i.e., to alleviate
congestion on the ground.
Safety is the primary consideration in network planning.

4/22

Space networks

The 3d continuous sky is discretized into a 2d grid network.
Vertiports are subset of nodes of the network.
SLSs are located outside the grid, their covering areas areballs.
Demands are transportation in eVTOLs among vertiports.
SLSs allow eVTOLs to land in their covered ranges.

5/22

ts
Figure: A path from vertiport s to vertiport t (in red)
6/22

Mathematical formulations

Mathematical formulations are derived frommulti-commodity flow (MCF) problem.
Unsplittable MCF is known to be N P −hard, but integer
programming approach is efficient in practice.

7/22

Mathematical formulations

Two representations, edge and path formulations.
Compact Edge formulation: every node has flow
conservation constraints and associated variables, andtheir size grows polynomially w.r.t. network size.
Path formulation: edge variables are aggregated intopath variables i.e. incident vectors. Exponential number ofpath variables.

8/22

SLS location problem

Decision variables are the routing of eVTOLs and theselection of SLSs to install.
Objective: the cost of eVTOL transportation.
Cover constraints: every route is covered by SLSs.
Capacity constraints: each edge can have a limited
number of eVTOLs.
Budget constraints: the number of installed SLSs is lessthan b.
Unsplittable constraints.

9/22

Notations
The network G = (V , A, c, m ) where V and A is the set ofnodes and edges.
cij : The cost of moving 1 eVTOL on edge, (i, j ) ∈ A.
mij : The capacity of eVTOLs on edge, (i, j ) ∈ A.
D demands, demand h ∈ D requires transportation of aeVTOL from a source vertiport sh ∈ V to a destination
vertiport th ∈ V .
`¯ is the number of available SLSs.
¯ .
A` is the set of edges covered by SLS ` ∈ {1, . . . , `}A0 is the set of edges covered by all vertiports.

10/22

Edge formulationmin ∑x,y∑ cij xijhh∈D (i,j )∈Ah
−1 if i = shh∑ xji − ∑ xij = +1 if i = t h(j,i )∈A(i,j )∈A0 otherwise∀i ∈ N, h ∈ D∑ xijh ≤ mij∀(i, j ) ∈ A,h ∈D`¯xijh ≤∑y`∀(i, j ) ∈ A \ A0 , h ∈ D`=1,(i,j )∈A``¯∑ y` ≤ b`=1xij ∈ {0, 1}∀(i, j ) ∈ A, y` ∈ {0, 1} ∀` = 1, . . . , `¯11/22

Path formulationmin∑

Dcij ∑∑

h=1 p ∈P h ,(i,j )∈p(i,j )∈AD
∑h=1 ∑p∈P h ,(i,j )∈p xph ≤ mij∑p∈P h xph = 1xph∀(i, j ) ∈ A,
∀h = [1, D ],12/22

Path formulationmin∑

Dcij ∑∑

xph

h=1 p ∈P h ,(i,j )∈p(i,j )∈AD
∑h=1 ∑p∈P h ,(i,j )∈p xph ≤ mij∑p∈P h xph = 1∑p∈P h ,(i,j )∈p xph ≤ ∑``=1,(i,j )∈A` y`∑``=1 y` ≤ bxph ∈ {0, 1}y` ∈ {0, 1}∀(i, j ) ∈ A,
∀h = [1, D ],∀h = [1, D ], ∀(i, j ) ∈ A \ A0 ,∀h = [1, D ], ∀p ∈ P h ,¯∀` = {1, . . . , `}Its linear relaxation is solved by the column generation.

13/22

Algorithms

Column generation is an efficient method for solving large
scale linear programming.
Column generation progressively solves restricted masterproblems (RMP).
Efficient when column size is exponential to row size (LPrelaxation of path formulation!).
Branch-and-bound: implicitly enumerates solutions for
combinatorical problems.
Branch-and-price: embeds column generation intobranch-and-bound.

14/22

Column generation
How does reduce cost pricing work?
Answer: Look at the dual problem of LP relaxation.
LP relaxation:
Dmin∑ cij ∑(i,j )∈A∑

xph

h=1 p ∈P h ,(i,j )∈ph∀(i, j ) ∈ A, (γij ≥ 0)
∑Dh=1 ∑p ∈P h ,(i,j )∈p xp ≤ mijh∀h = [1, D ], (µh ∈ R )∑p∈P h xp = 1`h∑p∈P h :(i,j )∈p xp ≤ ∑`=1:(i,j )∈A` y` ∀h = [1, D ], ∀(i, j ) ∈ A \ A0 ,(ηijh ≥ 0)
( ξ ≥ 0)∑``=1 y` ≤ bhxp ∈ [0, ∞)∀h = [1, D ], ∀p ∈ P h ,¯y` ∈ [0, ∞)∀` = {1, . . . , `}15/22

Pricing problem
The dual is:`max − ∑(i,j )∈A γij mij − ∑D
h=1 µh − ξ ∑`=1 b∑(i,j )∈p (cij + γij ) + µh + ∑(i,j )∈p:(i,j )6∈A0 ηijh ≥ 0,h− ∑D
h=1 ∑(i,j )∈A` ηij + ξ ≥ 0,γij ≥ 0,µh ∈ R,
ηijh ≥ 0,∀h = [1, D ], ∀p ∈ P h¯∀`in{1, . . . , `}∀(i, j ) ∈ A∀h = [1, D ]∀h = [1, D ],∀(i, j ) ∈ A \ A0

ξ ≥ 0.
Reduced cost of p ∈ P h :RC (p ) = ∑(i,j )∈p (cij + γij ) + µh + ∑(i,j )∈p:(i,j )6∈A0 ηijh .
The column with the least reduced cost is found by ashortest path algorithm.
16/22

Numerical experiments: instances

Instance

Nodes

Edges

Demands

SLSs

vertiports

12
3
4
5
6
7
8

36
48
63
100
225
324
400
529

120
164
220
360
840
1224
1520
2024

3
6
7
11
17
20
25
25

16
20
20
36
49
64
81
100

4
6
6
16
36
49
64
81

Table: Instances

17/22

Numerical experiments: a visual example
scatter typenodeskyport
SLS1.21.0
0.8
0.6
0.4
0.2
0.0
−0.2
−0.25

0.00

0.25

0.50

0.75

1.00

1.25

1.50

Figure: A template city
18/22

Numerical experiments: computational results

I
1234
56
78

B
55559
2025
29

Edge formulation

Path formulationz∗

Gap(%)

t

Nodes

z∗

Gap(%)

t

Nodes

175.98355.92591.19300.051512.132290.753025.70
-00
0
0
0
0
0.35
-

0.02
0.05
4.74
0.05
22.83
790.373600
3600

111538
11446
20861
30341
20861

175.98355.92591.19300.051512.18-00000.31-0.53
0.2
3600
0.56
3600
3600
3600
3600

423
128920164666
33192
10635
10829

Compact edge formulation is solved by Cplex 12.10.0
single thread mode.
Path formulation is solved by Scip 7.0.1 with Cplex as a LPsolver.
Time limit is set to 3600 seconds.
19/22

Experiments: discussions

I1
2
3
4
56
78

B
5
55
5
920
2529

Edge formulation

Path formulationz∗

Gap(%)

t

Nodes

z∗

Gap(%)

t

Nodes

175.98355.92591.19300.051512.132290.753025.70-0000
000.35-0.020.05
4.74
0.05
22.83
790.373600
3600

111538
11446
20861
30341
20861

175.98355.92591.19300.051512.18
-

00
0
0
0.31
-

0.53
0.2
3600
0.56
3600
3600
3600
3600

423
128920164666
33192
10635
10829

Cplex indeed separates cuts to strengthen the edge
formulation.
The scip’s branch and price deactives cut separation.
SLS variable y makes the network design problem harderthan the routing problem.
20/22

Conclusion

Summary
We propose an model for SLS location problem.
We propose 2 formulations for the model.
We devise algorithms to solve 2 formulations.

21/22

Future work
Combine with Bender decomposition.
Improve the stability of column generation.
Valid inequalities.

22/22