Skip to content
GitLab
Explore
Sign in
Primary navigation
Search or go to…
Project
ba
Manage
Activity
Members
Labels
Plan
Issues
Issue boards
Milestones
Wiki
Requirements
Code
Merge requests
Repository
Branches
Commits
Tags
Repository graph
Compare revisions
Snippets
Locked files
Build
Pipelines
Jobs
Pipeline schedules
Test cases
Artifacts
Deploy
Releases
Package registry
Container Registry
Model registry
Operate
Environments
Terraform modules
Monitor
Incidents
Analyze
Value stream analytics
Contributor analytics
CI/CD analytics
Repository analytics
Code review analytics
Issue analytics
Insights
Model experiments
Help
Help
Support
GitLab documentation
Compare GitLab plans
Community forum
Contribute to GitLab
Provide feedback
Keyboard shortcuts
?
Snippets
Groups
Projects
Show more breadcrumbs
markn92
ba
Merge requests
!1
Working np Algorithm
Code
Review changes
Check out branch
Download
Patches
Plain diff
Merged
Working np Algorithm
dev
into
master
Overview
0
Commits
23
Pipelines
0
Changes
15
Merged
markn92
requested to merge
dev
into
master
5 years ago
Overview
0
Commits
23
Pipelines
0
Changes
15
Expand
Algorithm seems to work. More testing and overthinking the structure necessary.
0
0
Merge request reports
Compare
master
master (base)
and
latest version
latest version
315f3c52
23 commits,
5 years ago
15 files
+
780
−
129
Inline
Compare changes
Side-by-side
Inline
Show whitespace changes
Show one file at a time
Files
15
Search (e.g. *.vue) (Ctrl+P)
evrouting/charge/T.py
+
220
−
38
Options
from
copy
import
copy
from
collections
import
namedtuple
from
typing
import
Callable
,
NamedTuple
from
math
import
inf
import
networkx
as
nx
from
evrouting.T
import
SoC
,
Wh
,
ChargingCoefficient
,
Time
,
Node
from
evrouting.graph_tools
import
charging_cofficient
,
consumption
Label
=
namedtuple
(
'
Label
'
,
[
'
t_trip
'
,
'
beta_u
'
,
'
u
'
,
'
SoCProfile_u_v
'
])
class
SoCProfile
:
"""
The SoC Profile maps an initial SoC to the SoC after
traversing a path.
class
ChargingFunction
:
SoC profile of a path is fully described with two parameters:
- cost: Cost of going from u to v.
- out: Maximal SoC after passing the path from u to v.
"""
def
__init__
(
self
,
G
:
nx
.
Graph
,
l
:
Label
):
self
.
t_trip
:
Time
=
l
.
t_trip
self
.
beta_u
:
SoC
=
l
.
beta_u
self
.
u
:
Node
=
l
.
u
self
.
b_u_v
:
SoCProfile
=
l
.
SoCProfile_u_v
self
.
c_u
:
ChargingCoefficient
=
charging_cofficient
(
G
,
l
.
u
)
def
__init__
(
self
,
path_cost
:
Wh
,
capacity
:
SoC
):
"""
Calculates the maximum SoC after traversing the path, which is
(for non-negative path costs) U - cost.
def
__call__
(
self
,
t
)
->
SoC
:
if
t
<
self
.
t_trip
:
:param path_cost: Cost of the path. The SoC Profile of
a single vertex has no cost.
:param capacity: The battery
'
s capacity.
"""
self
.
capacity
:
SoC
=
capacity
self
.
path_cost
:
Wh
=
path_cost
self
.
out
:
SoC
=
capacity
-
self
.
path_cost
def
__call__
(
self
,
initial_soc
:
SoC
)
->
SoC
:
"""
:param initial_soc: The initial SoC.
:returns: The SoC after traversing the path.
"""
if
initial_soc
<
self
.
path_cost
:
return
-
inf
final_soc
=
initial_soc
-
self
.
path_cost
return
final_soc
if
final_soc
<
self
.
capacity
else
self
.
capacity
return
self
.
beta_u
(
self
.
beta_u
+
self
.
c_u
*
(
t
-
self
.
t_trip
))
def
__add__
(
self
,
other
:
'
SoCProfile
'
)
->
'
SoCProfile
'
:
"""
Combines to SoC Profiles.
def
get_minimum
(
self
)
->
Time
:
"""
TODO: Explain.
"""
cost_p
=
self
.
b_u_v
.
cost
return
max
(
self
.
t_trip
,
(
cost_p
-
self
.
beta_u
)
/
self
.
c_u
+
self
.
t_trip
)
The for the combined SoC Profile, given a SoC Profile for a path a
and a path b, holds:
cost = cost_a + cost_b
out = U - cost
class
SoCProfile
:
:return: Combined SoC Profile.
"""
return
SoCProfile
(
self
.
path_cost
+
other
.
path_cost
,
self
.
capacity
)
class
ChargingFunction
:
"""
Describe SoC profile with two parameters:
- cost: Cost of going from u to v.
- out: Maximal SoC after passing the path from u to v.
Charging functions map charging time to resulting SoCs. Since they are
monotonic, there exists also an inverse mapping SoC to charging time.
Dummy Charging Station
======================
Special case is a so called dummy charging station. This is the case
if the charging coefficient is 0. Then there is no actual charging and
the value of the charging station is always the same as the arrival SoC.
A dummy charging station is necessary for initialization of the problem
to trigger spawning of new labels.
"""
def
__init__
(
self
,
G
:
nx
.
Graph
,
U
:
SoC
,
u
:
Node
,
v
:
Node
=
None
):
if
v
is
None
:
self
.
cost
:
Wh
=
0
self
.
out
:
Wh
=
U
def
__init__
(
self
,
c
:
ChargingCoefficient
,
capacity
:
SoC
,
initial_soc
:
SoC
=
None
):
"""
:param c: The stations charging coefficient. If c=0, the this becomes
a so called dummy charging station, that exists to trigger label
creation in the algorithm.
:param capacity: The battery
'
s capacity, respectively the maximum of
the charging function.
:param initial_soc: The SoC at arriving at the charging station. This is
optional for dummy charging stations, that do not actually charge:
cf(b) = soc
"""
self
.
c
:
ChargingCoefficient
=
c
self
.
capacity
:
SoC
=
capacity
self
.
initial_soc
:
SoC
=
initial_soc
@property
def
is_dummy
(
self
)
->
bool
:
"""
Tell if function is a dummy function.
"""
return
self
.
c
==
0
def
__call__
(
self
,
t
:
Time
,
initial_soc
:
SoC
=
0
)
->
SoC
:
"""
:param t: Charging time
:param initial_soc: Initial SoC when starting to charge
:return: SoC after charging.
"""
if
self
.
is_dummy
:
if
self
.
initial_soc
is
None
:
raise
ValueError
(
'
Charging coefficient is 0 but no initial SoC given.
'
)
soc
=
self
.
initial_soc
else
:
self
.
cost
:
Wh
=
consumption
(
G
,
u
,
v
)
self
.
out
:
Wh
=
U
-
self
.
cost
soc
=
initial_soc
+
self
.
c
*
t
return
soc
if
soc
<
self
.
capacity
else
self
.
capacity
@property
def
inverse
(
self
)
->
Callable
[[
SoC
],
Time
]:
"""
:returns: Inverse charging function mapping SoC to charging
time (assuming initial SoC=0)
"""
if
self
.
is_dummy
:
raise
ValueError
(
'
Dummy Carging function has no inverse.
'
)
c
=
self
.
c
capacity
=
self
.
capacity
def
cf_inverse
(
soc
:
SoC
)
->
Time
:
if
soc
>
capacity
:
# Return max charge time
return
capacity
/
c
elif
soc
<
0
:
# Return min charge time
return
0
return
soc
/
c
return
cf_inverse
def
__call__
(
self
,
beta
)
->
SoC
:
if
beta
<
self
.
cost
:
class
Label
(
NamedTuple
):
"""
Label used for the Algorithm.
The (paleto optimal) label where u=t is the
contains the minimum trip time necessary to get to t.
The label of node v consists of a tuple:
(t_trip, soc_last_cs, last_cs, soc_profile_cs_v)
Where:
:t_trip: Trip time to node v without charging time at the last
charging station.
:soc_last_cs: Arrival SoC at the last charging station.
:last_cs: (Node ID of) The last charging station.
:soc_profile_cs_v: The SoC Profile describing the costs going from
the charging station to current node v.
"""
t_trip
:
Time
soc_last_cs
:
SoC
last_cs
:
Node
soc_profile_cs_v
:
SoCProfile
class
SoCFunction
:
"""
SoC Function of a node
'
s label maps trip time plus an additional charging
time at the last charging station to a SoC at the node.
"""
def
__init__
(
self
,
label
:
Label
,
cf_cs
:
ChargingFunction
):
"""
:param label: Label containing to a node. It has the fields:
:t_trip: Trip time. Includes time to reach v from the last
charging station in the path but excludes charging at u.
:soc_last_cs: The SoC at reaching the last charging station
before any charging.
:last_cs: The last charging station in the path to current node.
:soc_profile_cs_v: The SoC Profile of the path cs -> v.
:cf_cs: Charging function of cs.
:param cf_cs: The charging function of the last charging station.
"""
# Unpack label
self
.
t_trip
:
Time
=
label
.
t_trip
self
.
last_cs
:
Node
=
label
.
last_cs
self
.
soc_last_cs
:
SoC
=
label
.
soc_last_cs
self
.
soc_profile_cs_v
:
SoCProfile
=
label
.
soc_profile_cs_v
self
.
cf_cs
:
ChargingFunction
=
cf_cs
def
__call__
(
self
,
t
:
Time
)
->
SoC
:
"""
Maps a new trip time to a SoC at the current node. The new trip time
then includes and fixes charging time at the last charging station.
:param t: t = trip time + charging at the last charging station
:return: SoC at current node at time t after spending t - t_trip at
the last charging station to charge the battery.
"""
if
t
<
self
.
t_trip
:
# Impossible to reach the current node for times < trip time
return
-
inf
return
beta
-
self
.
cost
def
__add__
(
self
,
other
:
'
SoCProfile
'
)
->
'
SoCProfile
'
:
new
=
copy
(
self
)
new
.
cost
=
self
.
cost
+
other
.
cost
new
.
out
=
self
.
out
-
other
.
cost
return
self
.
soc_profile_cs_v
(
self
.
cf_cs
(
t
-
self
.
t_trip
,
self
.
soc_last_cs
)
)
@property
def
minimum
(
self
)
->
Time
:
"""
:returns: Least feasible trip time. That is, the minimum time when
the SoC functions yields a SoC value that is not -inf.
This is either the trip time, or if energy needs to be charged
at the previous charging station to traverse the path, trip time
plus charging time until the battery holds the minimum energie to
traverse the path to the current node (which is the cost of the
path). This time is:
t = t_trip + cf_cs^(-1)(cost_cs_v) - cf_cs^(-1)(soc_last_sc)
Thus, for t_min holds:
t_min = max(t_trip, t)
"""
cost_p
=
self
.
soc_profile_cs_v
.
path_cost
if
cost_p
>
self
.
soc_last_cs
:
if
self
.
cf_cs
.
is_dummy
:
# Not feasible. Dummy stations do not load.
return
-
inf
return
self
.
t_trip
+
\
self
.
cf_cs
.
inverse
(
cost_p
)
-
\
self
.
cf_cs
.
inverse
(
self
.
soc_last_cs
)
return
new
return
self
.
t_trip
Loading