Network optimization
View Patent ↗Aspects of the present disclosure involve a method for optimizing an extension of an optical network to provide service to one or more new customers. The method considers the location of existing network nodes as well as a metropolitan environment where the new customer is located (e.g., the geographical location of streets where fiber may be routed to a customer). Aspects of the present disclosure further employ one of various linear programming models, such as a 1-Layer Model, a 3-Layer Model, a 5-Layer Model and a Dual Path Model to generate cost effective solutions to extend the existing optical network to provide service to the new customers.
1. A method for optimizing a communication network configuration comprising:
identifying, using at least one processor, a plurality of arc paths and a plurality of nodes of a potential extension of an existing communication network sufficient to connect at least one potential customer location to the existing communication network, the at least one potential customer location associated with a value for connecting the at least one potential customer location to the existing communication network, the existing communication network comprising at least a first node and a second node interconnected by at least one existing communication path;
executing, using the at least one processor, a linear programming application to optimize a summation of the value of connecting each of the at least one potential customer locations less a cost of connecting each of the at least one potential customer locations using a combination of the plurality of arc paths beginning at the first node of the existing communication network and ending at the second node of the existing communication network, the linear programming application receiving as inputs at least one parameter, at least one variable, and a plurality of constraints including at least one connectivity constraint, at least one saturation constraint, at least one service constraint, and at least one distance constraint, the at least one distance constraint causing the combination of arc paths to not form an isolated loop; and
delivering using the at least one processor a solution including at least one path from the first node to the at least one potential location and to the second node.
2. The method of claim 1 further comprising:
providing for at least three different types of connection paths to the at least one customer location, the types of connection paths comprising a ring path, a protected lateral path, and an unprotected lateral path;
the value of connecting the at least one potential customer location including one or more values accounting for whether the path is the ring path the protected lateral path or the unprotected lateral path; and
the at least one distance constraint including at least a first distance constraint associated with the ring path and establishing about a maximum distance for the ring path, a second distance constraint associated with the protected lateral path and establishing about a maximum distance for the protected lateral path, and a third distance constraint associated with the unprotected lateral path and establishing about a maximum distance for the unprotected lateral path.
3. The method of claim 2 wherein the cost of connecting each of the at least one potential customer locations includes at least one equipment type for connecting the at least one potential customer to the existing network and the at least one distance constraint accounts for a range of the at least one equipment type such that a path for connecting the at least one potential customer to the existing network does not exceed the range of the at least one equipment type.
4. The method of claim 1 wherein:
the summation of the value of connecting each of the at least one customer locations less a cost of connecting each of the at least one location comprises:
Objective
Maximize
∑
n
∈
C
P
n
z
n
-
∑
(
n
,
m
)
∈
A
C
nm
x
nm
and further wherein:
the at least one parameter comprises:
Parameters
P n =“prize” value of connecting a potential customer node n
C nm =cost of laying fiber on the street represented by (n, m)
L nm =physical length of the street represented by (n, m)
M=a large number used in the routing constraints
the at least one variable comprises:
Variables
Count
Domain
x
nm
=
{
1
if
fiber
will
be
buried
along
arc
(
n
,
m
)
0
otherwise
∀ (n, m) ∈ A
binary
y
n
=
{
1
if
node
n
will
be
connected
to
the
fiber
networ
0
otherwise
∀n ∈ N
binary
z
n
=
{
1
if
potential
customer
node
n
meets
all
service
criteria
for
collecting
its
“
prize
”
0
otherwise
∀n ∈ C
binary
d n = lower bound on d istance from the existing network to node n
∀n ∈ N
continuous
along a directed fiber path
the at least one connectivity constraint comprises:
Connectivity Constraints
Count
y n = 1
∀n ∈ E
∑
(
n
,
m
)
∈
δ
+
(
m
)
x
nm
≥
y
m
∀m ∈ N/E
x nm ≦ y m
∀ (n, m) ∈ A
y
n
≤
∑
(
n
,
m
)
∈
δ
-
(
n
)
x
nm
∀n ∈ N/E
y n ≧ x nm
∀ (n, m) ∈ A
the at least one saturation constraint comprises:
Saturation Constraints
Count
x nm + x mn ≦ 1
∀(n, m) ∈ A
the at least one distance constraint comprises:
Distance Constraints
Count
d n = 0
∀n ∈ E
−d n + d m ≧ −M + (M + L nm )x nm
∀(n, m) ∈ A|m ∉ E;
and
the at least one service constraint comprises:
Service Constraints
Count
z n P ≦ y n R + y n P
∀n ∈ C
z n U ≦ y n R + y n P + y n U
∀n ∈ C
z n P + z n U ≦ 1
∀n ∈ C.
5. The method of claim 2 wherein:
the linear programming application optimizes the summation of:
Objective
Maximize
∑
n
∈
C
(
P
n
P
z
n
P
+
P
n
U
z
n
U
)
-
∑
(
n
,
m
)
∈
A
(
C
nm
x
nm
L
+
2
C
nm
x
nm
P
+
C
nm
x
nm
U
)
and further wherein:
the at least one parameter comprises:
Parameters
Count
P n l : “prize” value of providing a level l service to the
∀l ∈ {P, U},
potential customer node n.
n ∈ C
C nm : cost of laying fiber on a street represented by (n, m)
∀ (n, m) ∈ A
L nm : physical length of the street represented by(n, m)
∀ (n, m) ∈ A
M: a large number used in the routing constraints
D P : maximum length of the protected lateral
D U : maximum length of the unprotected lateral
the at least one variable comprises:
Variables
Count
Domain
x
nm
l
=
{
1
if
fiber
will
be
buried
along
arc
(
n
,
m
)
on
layer
l
0
otherwise
∀l ∈ {R, P, U}, (n, m) ∈ A
binary
y
n
l
=
{
1
if
node
n
will
be
connected
on
layer
l
0
otherwise
∀l ∈ {R, P, U}, n ∈ N
binary
z
n
l
=
{
1
if
potential
customer
node
n
meets
all
criteria
for
and
will
be
connected
with
service
level
l
0
otherwise
∀l ∈ {P, U}, n ∈ C
binary
d n l = distance from the “beginning” of a directed
∀l ∈ {R, P, U},
continuous
arc path to node nonlayer l
n ∈ N
the at least one connectivity constraint comprises:
Connectivity Constraints
Count
y n R = 1
y n P = 0
y n U = 0
∀n ∈ E
∑
(
n
,
m
)
∈
δ
+
(
m
)
x
nm
l
≥
y
m
l
∀l ∈ {R, P, U}, m ∈ N/E
x nm l ≦ y m l
∀l ∈ {R, P, U}, (n, m) ∈ A
y
n
R
≤
∑
(
n
,
m
)
∈
δ
-
(
n
)
x
nm
R
∀n ∈ N/E (layer R only)
y n R ≧ x nm R
∀ (n, m) ∈ A
y n R + y n P ≧ x nm P
∀ (n, m) ∈ A
y n R + y n P + y n U ≧ x nm U
∀ (n, m) ∈ A
the at least one saturation constraint comprises:
Saturation Constraints
Count
y n R + y n P + y n U ≦ 1
∀ n ∈ N
x nm R + x mn R + x nm P + x mn P + x nm U + x mn U ≦ 1
∀(n, m) ∈ A
the at least one distance constraint comprises:
Distance Constraints
Count
d n R = 0
d n P = 0
d n U = 0
n ∈ E
d n R ≦ M
d n P ≦ D P
d n U ≦ D U
n ∈ N
−d n R + d m R ≧ −M + (M + L nm )x nm R
∀(n, m) ∈ A|m ∉ E
−d n P + d m P ≧ −D P + (D P + L nm )x nm P
∀(n, m) ∈ A
−d n U + d m U ≧ −D U + (D U + L nm )x nm U
∀(n, m) ∈ A;
and
the at least one service constraint comprises:
Service Constraints
Count
z n P ≦ y n R + y n P
∀n ∈ C
z n U ≦ y n R + y n P + y n U
∀n ∈ C
z n P + z n U ≦ 1
∀n ∈ C.
6. The method of claim 3 wherein:
the linear programming application optimizes the summation of:
Objective
Maximize
∑
n
∈
C
(
P
n
P
z
n
P
+
P
n
U
z
n
U
)
-
∑
(
n
,
m
)
∈
A
(
C
nm
x
nm
R
+
2
C
nm
x
nm
P
+
C
nm
x
nm
U
)
-
∑
ℓ
∈
{
1
,
2
}
∑
n
∈
C
∑
t
∈
T
Q
t
q
n
,
t
ℓ
and further wherein:
the at least one parameter comprises:
Parameters
Count
P n l = prize value of providing a level l service to
∀l ∈ {P, U},
potential customer node n.
n ∈ C
C nm = cost of laying fiber on a street represented by
∀ (n, m) ∈ A
(n, m)
L nm = physical length of the street represented by (n, m)
∀ (n, m) ∈ A
M = a large number used in the routing constraints
D P = maximum length of the protected lateral
D U = maximum length of the unprotected lateral
G n l distance from node n to a chosen gateway in
∀l ∈ {1, 2},
direction l along an existing fiber
n ∈ E
Q t = cost of using equipment type t to build a customer
∀t ∈ T
connection)
R t = range of the equipment type t
∀t ∈ T
the at least one variable comprises:
Variables
Count
Domain
x
nm
l
=
{
1
if
arc
(
n
,
m
)
will
be
used
on
the
layer
l
0
otherwise
∀l ∈ {R, P, U, 1, 2}, (n, m) ∈ A
binary
y
n
l
=
{
1
if
node
n
will
be
connected
on
the
layer
l
0
otherwise
∀l ∈ {R, P, U, 1, 2}, n ∈ N
binary
z
n
l
=
{
1
if
potential
customer
node
n
meets
all
criteria
for
and
will
be
connected
with
a
service
level
l
0
otherwise
∀l ∈ {P, U}, n ∈ C
binary
d n l = distance from the “beginning” of a directed
∀l ∈ {R, P, U,
continuous
arc path to the node nonlayer l
1, 2}, n ∈ N
q
n
,
t
l
=
{
1
if
potential
customer
node
n
will
use
the
equipment
type
t
to
connecton
layer
l
0
otherwise
∀l ∈ {1, 2}, n ∈ C
binary
the at least one connectivity constraint comprises:
Connectivity Constraints
Count
y n R = 1
y n P = 0
y n U = 0
y n 1 = 1
y n 2 = 1
∀n ∈ E
∑
(
n
,
m
)
∈
δ
+
(
m
)
x
nm
l
≥
y
m
l
∀l ∈ {R, P, U, 1, 2}, m ∈ N/E
x n,m l ≦ y m l
∀l ∈ {R, P, U, 1, 2},
(n, m) ∈ A
y
n
R
≤
∑
(
n
,
m
)
∈
δ
-
(
n
)
x
nm
R
∀n ∈ N/E (layer R only)
y n R ≧ x nm R
∀ (n, m) ∈ A
y n R + y n P ≧ x nm P
∀ (n, m) ∈ A
y n R + y n P + y n U ≧ x nm U
∀ (n, m) ∈ A
y n 1 ≧ x nm 1
∀ (n, m) ∈ A
y n 2 ≧ x nm 2
∀ (n, m) ∈ A
the at least one saturation constraint comprises:
Saturation Constraints
Count
y n R + y n P + y n U ≦ 1
∀ n ∈ N
x nm R + x mn R + x nm P + x mn P + x nm U + x mn U ≦ 1
∀(n, m) ∈ A
x nm 1 ≦ x nm R + x nm P + x nm U
∀(n, m) ∈ A
x nm 2 ≦ x mn R + x nm P + x nm U
∀(n, m) ∈ A
the at least one distance constraint comprises:
Distance Constraints
Count
d n R = 0
d n P = 0
d n U = 0
d n 1 = G n 1
d n 2 = G n 2
∀n ∈ E
d n R ≦
d n P ≦
d n U ≦
d n 1 ≦
d n 2 ≦
∀n ∈ N
M
D P
D U
R max
R max
−d n R + d m R ≧−M + (M + L nm )x nm R
∀(n, m) ∈ A|m ∉ E
−d n P + d m P ≧−DP + (D P + L nm )x nm P
∀(n, m) ∈ A
−d n U + d m U ≧−DU + (D U + L nm )x nm U
∀(n, m) ∈ A
−d n 1 + d m 1 ≧−R max + (R max + L nm )x nm 1
∀(n, m) ∈ A
−d n 2 + d m 2 ≧−R max + (R max + L nm )x nm 2
∀(n, m) ∈ A
d n 1 ≦ R t + (1 − q n,t 1 )M
∀n ∈ C, t ∈ T
d n 2 ≦ R t + (1 − q n,t 2 )M
∀n ∈ C, t ∈ T;
and
the at least one service constraint comprises:
Service Constraints
Count
q n,t l ≦ y n l
∀l ∈ {1, 2}, n ∈ C
z
n
P
≤
∑
t
∈
T
q
n
,
t
l
∀l ∈ {1, 2}, n ∈ C
z
n
U
≤
∑
l
∈
{
1
,
2
}
∑
t
∈
T
q
n
,
t
l
∀n ∈ C
z n P + z n U ≦ 1
∀n ∈ C.
7. A computer network comprising:
an optical communication network extending an existing optical communication network comprising at least a first node and a second node, the optical communication network to provide service to at least one new customer location, the optical communication network comprising at least one fiber path between the first node and the second node, the optical communication network configured in accordance with an integer programming model comprising:
identifying a plurality of arc paths and a plurality of nodes of a potential extension of the existing optical communication network sufficient to connect at least one potential customer location to the existing communication network, the at least one potential customer location including the at least one new customer location and associated with a value for connecting the at least one potential customer location to the existing optical communication network;
optimizing a summation of the value of connecting each of the at least one potential customer location less a cost of connecting each of the at least one potential customer locations using a combination of the plurality of arc paths beginning at the first node of the existing optical communication network and ending at the second node of the existing optical communication network, the integer programming application receiving as inputs at least one parameter, at least one variable, and a plurality of constraints including at least one connectivity constraint, at least one saturation constraint, at least one service constraint, and at least one distance constraint, the at least one distance constraint causing the combination of arc paths to not form an isolated loop.
8. The computer network of claim 7 wherein the optical communication network is further configured in accordance with a solution to the integer programming model comprising:
providing for at least three different types of connection paths to the at least one potential customer location, the types of connection paths comprising a ring path, a protected lateral path, and an unprotected lateral path;
the value of connecting the at least one potential customer location including one or more values accounting for whether the path is the ring path the protected lateral path or the unprotected lateral path; and
the at least one distance constraint including at least a first distance constraint associated with the ring path and establishing about a maximum distance for the ring path, a second distance constraint associated with the protected lateral path and establishing about a maximum distance for the protected lateral path, and a third distance constraint associated with the unprotected lateral path and establishing about a maximum distance for the unprotected lateral path.
9. The computer network of claim 8 wherein the optical communication network is further configured in accordance with the solution to an integer programming model further wherein the cost of connecting each of the at least one potential customer locations includes at least one equipment type for connecting the at least one potential customer to the existing network and the at least one distance constraint accounts for a range of the at least one equipment types such that a path for connecting the at least one potential customer location to the existing network does not exceed the range of the at least one equipment type.
10. The computer network of claim 7 wherein:
the summation of the value of connecting each of the at least one potential customer locations less a cost of connecting each of the at least one potential customer locations comprises:
Objective
Maximize
∑
n
∈
C
P
n
z
n
-
∑
(
n
,
m
)
∈
A
C
nm
x
nm
and further wherein:
the at least one parameter comprises:
Parameters
P n =“prize” value of connecting a potential customer node n
C nm =cost of laying fiber on the street represented by (n, m)
L nm =physical length of the street represented by (n, m)
M=a large number used in the routing constraints
the at least one variable comprises:
Variables
Count
Domain
x
nm
=
{
1
if
fiber
will
be
buried
along
arc
(
n
,
m
)
0
otherwise
∀ (n, m) ∈ A
binary
y
n
=
{
1
if
node
n
will
be
connected
to
the
fiber
networ
0
otherwise
∀n ∈ N
binary
z
n
=
{
1
if
potential
customer
node
n
meets
all
service
criteria
for
collecting
its
“
prize
”
0
otherwise
∀n ∈ C
binary
d n = lower bound on d istance from the existing
∀n ∈ N
continuous
network to node n along a directed fiber path
the at least one connectivity constraint comprises:
Connectivity Constraints
Count
y n = 1
∀n ∈ E
∑
(
n
,
m
)
∈
δ
+
(
m
)
x
nm
≥
y
m
∀m ∈ N/E
x nm ≦ y m
∀ (n, m) ∈ A
y
n
≤
∑
(
n
,
m
)
∈
δ
-
(
n
)
x
nm
∀n ∈ N/E
y n ≧ x nm
∀ (n, m) ∈ A
the at least one saturation constraint comprises:
Saturation Constraints
Count
x nm + x mn ≦ 1
∀(n, m) ∈ A
the at least one distance constraint comprises:
Distance Constraints
Count
d n = 0
∀n ∈ E
−d n + d m ≧ −M + (M + L nm )x nm
∀(n, m) ∈ A|m ∉ E;
and
the at least one service constraint comprises:
Service Constraints
Count
z n P ≦ y n R + y n P
∀n ∈ C
z n U ≦ y n R + y n P + y n U
∀n ∈ C
z n P + z n U ≦ 1
∀n ∈ C.
11. The computer network of claim 8 wherein:
the linear programming application optimizes the summation of:
Objective
Maximize
∑
n
∈
C
(
P
n
P
z
n
P
+
P
n
U
z
n
U
)
-
∑
(
n
,
m
)
∈
A
(
C
nm
x
nm
L
+
2
C
nm
x
nm
P
+
C
nm
x
nm
U
)
and further wherein:
the at least one parameter comprises:
Parameters
Count
P n l : “prize” value of providing a level l service to the
∀l ∈ {P, U},
potential customer node n.
n ∈ C
C nm : cost of laying fiber on a street represented by (n, m)
∀ (n, m) ∈ A
L nm : physical length of the street represented by(n, m)
∀ (n, m) ∈ A
M: a large number used in the routing constraints
D P : maximum length of the protected lateral
D U : maximum length of the unprotected lateral
the at least one variable comprises:
Variables
Count
Domain
x
nm
l
=
{
1
if
fiber
will
be
buried
along
arc
(
n
,
m
)
on
layer
l
0
otherwise
∀l ∈ {R, P, U}, (n, m) ∈ A
binary
y
n
l
=
{
1
if
node
n
will
be
connected
on
layer
l
0
otherwise
∀l ∈ {R, P, U}, n ∈ N
binary
z
n
l
=
{
1
if
potential
customer
node
n
meets
all
criteria
for
and
will
be
connected
with
service
level
l
0
otherwise
∀l ∈ {P, U}, n ∈ C
binary
d n l = distance from the “beginning” of a directed
∀l ∈ {R, P, U},
continuous
arc path to node nonlayer l
n ∈ N
the at least one connectivity constraint comprises:
Connectivity Constraints
Count
y n R = 1
y n P = 0
y n U = 0
∀n ∈ E
∑
(
n
,
m
)
∈
δ
+
(
m
)
x
nm
l
≥
y
m
l
∀l ∈ {R, P, U}, m ∈ N/E
x nm l ≦ y m l
∀l ∈ {R, P, U}, (n, m) ∈ A
y
n
R
≤
∑
(
n
,
m
)
∈
δ
-
(
n
)
x
nm
R
∀n ∈ N/E (layer R only)
y n R ≧ x nm R
∀ (n, m) ∈ A
y n R + y n P ≧ x nm P
∀ (n, m) ∈ A
y n R + y n P + y n U ≧ x nm U
∀ (n, m) ∈ A
the at least one saturation constraint comprises:
Saturation Constraints
Count
y n R + y n P + y n U ≦ 1
∀ n ∈ N
x nm R + x mn R + x nm P + x mn P + x nm U + x mn U ≦ 1
∀(n, m) ∈ A
the at least one distance constraint comprises:
Distance Constraints
Count
d n R = 0
d n P = 0
d n U = 0
n ∈ E
d n R ≦ M
d n P ≦ D P
d n U ≦ D U
n ∈ N
−d n R + d m R ≧ −M + (M + L nm )x nm R
∀(n, m) ∈ A|m ∉ E
−d n P + d m P ≧ −D P + (D P + L nm )x nm P
∀(n, m) ∈ A
−d n U + d m U ≧ −D U + (D U + L nm )x nm U
∀(n, m) ∈ A;
and
the at least one service constraint comprises:
Service Constraints
Count
z n P ≦ y n R + y n P
∀n ∈ C
z n U ≦ y n R + y n P + y n U
∀n ∈ C
z n P + z n U ≦ 1
∀n ∈ C.
12. The computer network of claim 9 wherein:
the linear programming application optimizes the summation of:
Objective
Maximize
∑
n
∈
C
(
P
n
P
z
n
P
+
P
n
U
z
n
U
)
-
∑
(
n
,
m
)
∈
A
(
C
nm
x
nm
R
+
2
C
nm
x
nm
P
+
C
nm
x
nm
U
)
-
∑
ℓ
∈
{
1
,
2
}
∑
n
∈
C
∑
t
∈
T
Q
t
q
n
,
t
ℓ
and further wherein:
the at least one parameter comprises:
Parameters
Count
P n l = prize value of providing a level l service to potential
∀l ∈ {P, U},
customer node n.
n ∈ C
C nm = cost of laying fiber on a street represented by
∀ (n, m) ∈ A
(n, m)
L nm = physical length of the street represented by (n, m)
∀ (n, m) ∈ A
M = a large number used in the routing constraints
D P = maximum length of the protected lateral
D U = maximum length of the unprotected lateral
G n l distance from node n to a chosen gateway in
∀l ∈ {1, 2},
directionl along an existing fiber
n ∈ E
Q t = cost of using equipment type t to build a customer
∀t ∈ T
connection)
R t = range of the equipment type t
∀t ∈ T
the at least one variable comprises:
Variables
Count
Domain
x
nm
l
=
{
1
if
arc
(
n
,
m
)
will
be
used
on
the
layer
l
0
otherwise
∀l ∈ {R, P, U, 1, 2}, (n, m) ∈ A
binary
y
n
l
=
{
1
if
node
n
will
be
connected
on
the
layer
l
0
otherwise
∀l ∈ {R, P, U, 1, 2}, n ∈ N
binary
z
n
l
=
{
1
if
potential
customer
node
n
meets
all
criteria
for
and
will
be
connected
with
a
service
level
l
0
otherwise
∀l ∈ {P, U}, n ∈ C
binary
d n l = distance from the “beginning” of a directed
∀l ∈ {R, P, U,
continuous
arc path to the node nonlayer l
1, 2}, n ∈ N
q
n
,
t
l
=
{
1
if
potential
customer
node
n
will
use
the
equipment
type
t
to
connecton
layer
l
0
otherwise
∀l ∈ {1, 2}, n ∈ C
binary
the at least one connectivity constraint comprises:
Connectivity Constraints
Count
y n R = 1
y n P = 0
y n U = 0
y n 1 = 1
y n 2 = 1
∀n ∈ E
∑
(
n
,
m
)
∈
δ
+
(
m
)
x
nm
l
≥
y
m
l
∀l ∈ {R, P, U, 1, 2}, m ∈ N/E
x nm l ≦ y m l
∀l ∈ {R, P, U, 1, 2},
(n, m) ∈ A
y
n
R
≤
∑
(
n
,
m
)
∈
δ
-
(
n
)
x
nm
R
∀n ∈ N/E (layer R only)
y n R ≧ x nm R
∀ (n, m) ∈ A
y n R + y n P ≧ x nm P
∀ (n, m) ∈ A
y n R + y n P + y n U ≧ x nm U
∀ (n, m) ∈ A
y n 1 ≧ x nm 1
∀ (n, m) ∈ A
y n 2 ≧ x nm 2
∀ (n, m) ∈ A
the at least one saturation constraint comprises:
Saturation Constraints
Count
y n R + y n P + y n U ≦ 1
∀ n ∈ N
x nm R + x mn R + x nm P + x mn P + x nm U + x mn U ≦ 1
∀(n, m) ∈ A
x nm 1 ≦ x nm R + x nm P + x nm U
∀(n, m) ∈ A
x nm 2 ≦ x mn R + x nm P + x nm U
∀(n, m) ∈ A
the at least one distance constraint comprises:
Distance Constraints
Count
d n R = 0
d n P = 0
d n U = 0
d n 1 = G n 1
d n 2 = G n 2
∀n ∈ E
d n R ≦ M
d n P ≦ D P
d n U ≦
d n 1 ≦ R max
d n 2 ≦ R max
∀n ∈ N
D U
−d n R + d m R ≧ −M + (M + L nm )x nm R
∀(n, m) ∈ A|m ∉ E
−d n P + d m P ≧ −D P + (D P + L nm )x nm P
∀(n, m) ∈ A
−d n U + d m U ≧ −D U + (D U + L nm )x nm U
∀(n, m) ∈ A
−d n 1 + d m 1 ≧ −R max + (R max + L nm )x nm 1
∀(n, m) ∈ A
−d n 2 + d m 2 ≧ −R max + (R max + L nm )x nm 2
∀(n, m) ∈ A
d n 1 ≦ R t + (1 − q n,t 1 )M
∀n ∈ C, t ∈ T
d n 2 ≦ R t + (1 − q n,t 2 )M
∀n ∈ C, t ∈ T;
and
the at least one service constraint comprises:
Service Constraints
Count
q n,t l ≦ y n l
∀l ∈ {1, 2}, n ∈ C
z
n
P
≤
∑
t
∈
T
q
n
,
t
l
∀l ∈ {1, 2}, n ∈ C
z
n
U
≤
∑
l
∈
{
1
,
2
}
∑
t
∈
T
q
n
,
t
l
∀n ∈ C
z n P + z n U ≦ 1
∀n ∈ C.
13. A non-transitory computer readable medium comprising executable instructions configured to perform the method of claim 1 .
14. A non-transitory computer readable medium comprising executable instructions configured to perform the method of claim 2 .
15. A non-transitory computer readable medium comprising executable instructions configured to perform the method of claim 3 .
16. A non-transitory computer readable medium comprising executable instructions configured to perform the method of claim 4 .
17. A non-transitory computer readable medium comprising executable instructions configured to perform the method of claim 5 .
18. A non-transitory computer readable medium comprising executable instructions configured to perform the method of claim 6 .