Determination of path arrangement of infrastructure link network with trunk-and-branch topology
A computer-implemented method for determining a path arrangement of an infrastructure link network with a trunk-and-branch topology. The method includes: modelling a geographic terrain including three or more geographic locations that are connectable with each other via an infrastructure link network; determining a cost function associated with a cost for constructing the infrastructure link network that connects the three or more geographic locations; and determining a path arrangement of the infrastructure link network based on the modelled geographic terrain and by optimizing the cost function taking into account one or more constraints. The path arrangement of the infrastructure link network has a trunk-and-branch topology and includes: three or more infrastructure links that connect the three or more geographic locations, and one or more connection points each arranged between two or more of the infrastructure links.
1. A computer-implemented method for determining a path arrangement of an infrastructure link network with a trunk-and-branch topology, comprising:
modelling a geographic terrain including three or more geographic locations that are connectable with each other via an infrastructure link network;
determining a cost function associated with a cost for constructing the infrastructure link network that connects the three or more geographic locations; and
determining a path arrangement of the infrastructure link network based on the modelled geographic terrain and by optimizing the cost function taking into account one or more constraints,
the path arrangement of the infrastructure link network having a trunk-and-branch topology and including: three or more infrastructure links that connect the three or more geographic locations, and one or more connection points each arranged between two or more of the infrastructure links.
2. The computer-implemented method of claim 1 , wherein the one or more constraints comprise a maximum path length between two of the geographic locations, the maximum path length being defined by one or more of the infrastructure links.
3. The computer-implemented method of claim 1 , wherein optimizing the cost function taking into account one or more constraints comprises minimizing the cost function taking into account one or more constraints.
4. The computer-implemented method of claim 1 , wherein the modelling of the geographic terrain comprises modelling the geographic terrain as an irregular two-dimensional (2D) manifold in three-dimensional (3D) Euclidean space.
5. The computer-implemented method of claim 1 , wherein the cost function is a depth dependent cost function.
6. The computer-implemented method of claim 1 , wherein the cost for constructing the infrastructure link network comprises costs associated with laying and/or constructing (i) the infrastructure links and (ii) one or more connector units each connecting two or more of the infrastructure links, wherein each of the one or more connector units is arranged or to be arranged at a respective one of the one or more connection points.
7. The computer-implemented method of claim 1 , wherein the determining of the path arrangement of the infrastructure link network comprises determining a total number of and/or respective positions of the one or more connection points.
8. The computer-implemented method of claim 1 , wherein the determination of the path arrangement of the infrastructure link network comprises:
formulating the determination of the path arrangement of the infrastructure link network as a Steiner Minimal Tree problem taking into account the one or more constraints; and
solving the Steiner Minimal Tree problem taking into account the one or more constraints;
wherein the trunk-and-branch topology of the path arrangement of the infrastructure link network generally corresponds to a Steiner topology.
9. The computer-implemented method of claim 8 , wherein the formulating comprises formulating the Steiner Minimal Tree problem as a constrained Steiner Minimal Tree problem that can be represented by:
min
S
∈
H
,
Γ
F
(
S
)
=
f
(
S
)
+
c
b
·
N
b
s
.
t
.
d
k
(
x
i
,
x
j
)
≤
b
k
(
x
i
,
x
j
)
,
k
=
1
,
…
,
❘
"\[LeftBracketingBar]"
R
❘
"\[RightBracketingBar]"
where H is a set of mesh points in the modelled geographic terrain; I′ is a set of geodesic curves of the Steiner tree; R is a set of one or more constraints; S={s 1 , s 2 , . . . , s N 1 } is a set of positions of one or more Steiner nodes in the modelled geographic terrain; f(S) is an infrastructure link laying cost of the infrastructure link network, which is dependent on the positions of the one or more Steiner nodes S and the geodesic curves Γ; N b is the number of Steiner nodes; C b is the cost of each connector unit; x i and x j are any pair(s) of terminal nodes subjected to constrain factor(s), each of the terminal nodes corresponding to a respective one of the geographic locations; b(x i , x j ) is a value of the constraint; and d k (x i ,x j ) is a path length defined by one or more infrastructure links between nodes, x i and x j .
10. The computer-implemented method of claim 9 , wherein the solving comprises:
converting the constrained Steiner Minimal Tree problem into an unconstrained problem based on a Lagrange multiplier based method; and
determining a solution for the unconstrained problem to obtain respective optimal position of one or more Steiner nodes, each of the one or more Steiner nodes corresponding to a respective one of the one or more connection points.
11. The computer-implemented method of claim 10 , wherein the Lagrange multiplier based method applies a Lagrangian function that can be represented as:
L
(
S
,
λ
)
=
f
(
S
)
+
∑
k
=
1
❘
"\[LeftBracketingBar]"
R
❘
"\[RightBracketingBar]"
λ
k
(
g
k
(
S
)
-
b
k
(
x
i
,
x
j
)
)
+
c
b
·
N
b
where L(S,λ) is a Lagrangian function of s and λ; λ=[λ 1 , λ 2 , . . . , λ |R| ] T is the vector of Lagrange multipliers, λ k ≤0; f(S) represents the infrastructure link laying cost of the infrastructure link network; g k (S) denotes d k which is determined by the position of Steiner node(s) on a path of one or more infrastructure links between constrained nodes x i and x j .
12. The computer-implemented method of claim 11 , wherein the determining of the solution comprises:
applying fast marching method to each of the terminal nodes to obtain corresponding distance maps; and
processing the distance maps and a predetermined Steiner tree topology based on a directed acyclic graph based dynamic programming algorithm to obtain respective coordinate of the one or more Steiner nodes.
13. The computer-implemented method of claim 12 , wherein the one or more constraints consist of a single constraint associated with a maximum path length between two of the geographic locations, the maximum path length being defined by one or more of the infrastructure links.
14. The computer-implemented method of claim 13 , wherein the determining of the solution further comprises:
updating the distance maps based on a value of λ associated with the single constraint; and
processing the updated distance maps and the predetermined Steiner tree topology based on the directed acyclic graph based dynamic programming algorithm to obtain further respective coordinate of the one or more Steiner nodes.
15. The computer-implemented method of claim 14 , wherein the determining of the solution further comprises:
(1) updating the value of λ based on a primal-dual subgradient method;
(2) updating the distance maps based on the updated value of λ; and
(3) processing the updated distance maps and the predetermined Steiner tree topology based on the directed acyclic graph based dynamic programming algorithm to obtain updated coordinates of one or more Steiner nodes.
16. The computer-implemented method of claim 15 , wherein the determining of the solution further comprises:
iteratively repeating steps (1) to (3) until or after a limit of the constraint is reached, until or after a threshold associated with a limit of the constraint is reached, or until or after a predetermined number of iterations is completed, so as to obtain respective optimal position of the one or more Steiner nodes.
17. The computer-implemented method of claim 12 , wherein the one or more constraints comprise a plurality of constraints associated with a corresponding plurality of maximum path lengths each between respective two of the geographic locations, each of the maximum path lengths being defined by one or more of the infrastructure links.
18. The computer-implemented method of claim 17 , wherein the determining of the solution further comprises:
updating the distance maps based on values of two or more λs each associated with a respective one of the constrains; and
processing the updated distance maps and the predetermined Steiner tree topology based on the directed acyclic graph based dynamic programming algorithm to obtain further respective coordinate of the one or more Steiner nodes.
19. The computer-implemented method of claim 18 , wherein the determining of the solution further comprises:
(1) updating all of the values of λs based on a primal-dual subgradient method;
(2) updating the distance maps based on the updated values of λs; and
(3) processing the updated distance maps and the predetermined Steiner tree topology based on the directed acyclic graph based dynamic programming algorithm to obtain updated coordinates of one or more Steiner nodes.
20. The computer-implemented method of claim 19 , wherein the determining of the solution further comprises:
iteratively repeating steps (1) to (3) until or after respective limits of one or more of the constraints is reached, until or after respective thresholds associated with respective limits of one or more of the constraints is reached, or until or after a predetermined number of iterations is completed, so as to obtain respective optimal position of the one or more Steiner nodes.
21. The computer-implemented method of claim 1 , wherein the infrastructure link network comprises a submarine communication cable network.
22. The computer-implemented method of claim 21 , wherein the cost for constructing the submarine communication cable network comprises cost associated with laying and/or constructing (i) the communications cables and (ii) one or more branching units for connecting with at least two of the communications cables, wherein each of the one or more branching units is arranged at a respective one of the one or more connection points.
23. A non-transitory computer readable medium comprising computer instructions which, when executed by one or more processors, cause the one or more processors to carry out the method of claim 1 .
24. A system for determining a path arrangement of an infrastructure link network with a trunk-and-branch topology, comprising one or more processors arranged to:
model a geographic terrain including three or more geographic locations that are connectable with each other via an infrastructure link network;
determine a cost function associated with a cost for constructing the infrastructure link network that connects the three or more geographic locations; and
determine a path arrangement of the infrastructure link network based on the modelled geographic terrain and by optimizing the cost function taking into account one or more constraints,
the path arrangement of the infrastructure link network having a trunk-and-branch topology and including: three or more infrastructure links that connect the three or more geographic locations, and one or more connection points each arranged between two or more of the infrastructure links.