ding0.grid.mv_grid.solvers package¶
Submodules¶
ding0.grid.mv_grid.solvers.base module¶
Based on code by Romulo Oliveira copyright (C) 2015, https://github.com/RomuloOliveira/monte-carlo-cvrp Originally licensed under the Apache License, Version 2.0. You may obtain a copy of the license at http://www.apache.org/licenses/LICENSE-2.0
-
class
ding0.grid.mv_grid.solvers.base.
BaseSolution
(cvrp_problem)[source]¶ Bases:
object
Base abstract class for a CVRP solution
Parameters: cvrp_problem (type) – Desc Graph instance? -
can_process
(pairs)[source]¶ Returns True if this solution can process pairs
Parameters: pairs ( list
of pairs) – List of pairsReturns: bool – True if this solution can process pairs Todo
Not yet implemented
-
clone
()[source]¶ Returns a deep copy of self
Function clones:
- route
- allocation
- nodes
Returns: type – Deep copy of self
-
draw_network
(anim)[source]¶ Draws solution’s graph using networkx
Parameters: AnimationDing0 – AnimationDing0 object
-
get_pair
(pair)[source]¶ get pair description
Parameters: pair ( list
of nodes) – DescrReturns: type – Descr
-
is_complete
()[source]¶ Returns True if this is a complete solution, i.e, all nodes are allocated
Returns: bool – True if all nodes are llocated.
-
ding0.grid.mv_grid.solvers.local_search module¶
Based on code by Romulo Oliveira copyright (C) 2015, https://github.com/RomuloOliveira/monte-carlo-cvrp Originally licensed under the Apache License, Version 2.0. You may obtain a copy of the license at http://www.apache.org/licenses/LICENSE-2.0
-
class
ding0.grid.mv_grid.solvers.local_search.
LocalSearchSolution
(cvrp_problem, solution)[source]¶ Bases:
ding0.grid.mv_grid.solvers.base.BaseSolution
Solution class for Local Search metaheuristic
Parameters: - cvrp_problem (type) – Descr
- solution (BaseSolution) – Descr
-
class
ding0.grid.mv_grid.solvers.local_search.
LocalSearchSolver
[source]¶ Bases:
ding0.grid.mv_grid.solvers.base.BaseSolver
Improve initial savings solution using local search
The implementation of the local searach algorithm founds on the following publications [1], [2], [3], [4]
Graph operators:
Or-Opt (intra-route) Relocate (inter-route) Exchange (inter-route)
Todo
- Cross (inter-route) - to remove crossing edges between two routes
References
[1] - Wenger, “Multikriterielle Tourenplanung”, Dissertation, 2009
[2] - Kämpf, “Probleme der Tourenbildung”, Chemnitzer Informatik-Berichte, 2006
[3] O. Bräysy, M. Gendreau, “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms”, Transportation Science, vol. 39, Issue 1, pp. 104-118, 2005 [4] C. Boomgaarden, “Dynamische Tourenplanung und -steuerung”, Dissertation, 2007 -
benchmark_operator_order
(graph, solution, op_diff_round_digits)[source]¶ performs all possible permutations of route improvement and prints graph length
Parameters: - graph (NetworkX Graph Obj) – A NetworkX graaph is used.
- solution (BaseSolution) – BaseSolution instance
- op_diff_round_digits (float) –
Precision (floating point digits) for rounding route length differences.
Details: In some cases when an exchange is performed on two routes with one node each, the difference between the both solutions (before and after the exchange) is not zero. This is due to internal rounding errors of float type. So the loop won’t break (alternating between these two solutions), we need an additional criterion to avoid this behaviour: A threshold to handle values very close to zero as if they were zero (for a more detailed description of the matter see http://floating-point-gui.de or https://docs.python.org/3.5/tutorial/floatingpoint.html)
-
operator_cross
(graph, solution, op_diff_round_digits)[source]¶ applies Cross inter-route operator to solution
Takes every node from every route and calculates savings when inserted into all possible positions in other routes. Insertion is done at position with max. saving and procedure starts over again with newly created graph as input. Stops when no improvement is found.
Parameters: - graph (NetworkX Graph Obj) – Descr
- solution (BaseSolution) – Descr
- op_diff_round_digits (float) –
Precision (floating point digits) for rounding route length differences.
Details: In some cases when an exchange is performed on two routes with one node each, the difference between the both solutions (before and after the exchange) is not zero. This is due to internal rounding errors of float type. So the loop won’t break (alternating between these two solutions), we need an additional criterion to avoid this behaviour: A threshold to handle values very close to zero as if they were zero (for a more detaisled description of the matter see http://floating-point-gui.de or https://docs.python.org/3.5/tutorial/floatingpoint.html)
Returns: LocalSearchSolution – A solution (LocalSearchSolution class)
Todo
- allow moves of a 2-node chain
- Remove ugly nested loops, convert to more efficient matrix operations
-
operator_exchange
(graph, solution, op_diff_round_digits, anim)[source]¶ applies Exchange inter-route operator to solution
Takes every node from every route and calculates savings when exchanged with another one of all possible nodes in other routes. Insertion is done at position with max. saving and procedure starts over again with newly created graph as input. Stops when no improvement is found.
Parameters: - graph (NetworkX Graph Obj) – A NetworkX graaph is used.
- solution (BaseSolution) – BaseSolution instance
- op_diff_round_digits (float) –
Precision (floating point digits) for rounding route length differences.
Details: In some cases when an exchange is performed on two routes with one node each, the difference between the both solutions (before and after the exchange) is not zero. This is due to internal rounding errors of float type. So the loop won’t break (alternating between these two solutions), we need an additional criterion to avoid this behaviour: A threshold to handle values very close to zero as if they were zero (for a more detailed description of the matter see http://floating-point-gui.de or https://docs.python.org/3.5/tutorial/floatingpoint.html)
- anim (AnimationDing0) – AnimationDing0 object
Returns: LocalSearchSolution – A solution (LocalSearchSolution class)
Note
(Inner) Loop variables:
- i: node that is checked for possible moves (position in the route tour, not node name)
- j: node that precedes the insert position in target route (position in the route target_tour, not node name)
Todo
- allow moves of a 2-node chain
- Remove ugly nested loops, convert to more efficient matrix operations
-
operator_oropt
(graph, solution, op_diff_round_digits, anim=None)[source]¶ Applies Or-Opt intra-route operator to solution
Takes chains of nodes (length=3..1 consecutive nodes) from a given route and calculates savings when inserted into another position on the same route (all possible positions). Performes best move (max. saving) and starts over again with new route until no improvement is found.
Parameters: - graph (NetworkX Graph Obj) – A NetworkX graaph is used.
- solution (BaseSolution) – BaseSolution instance
- op_diff_round_digits (float) –
Precision (floating point digits) for rounding route length differences.
Details: In some cases when an exchange is performed on two routes with one node each, the difference between the both solutions (before and after the exchange) is not zero. This is due to internal rounding errors of float type. So the loop won’t break (alternating between these two solutions), we need an additional criterion to avoid this behaviour: A threshold to handle values very close to zero as if they were zero (for a more detailed description of the matter see http://floating-point-gui.de or https://docs.python.org/3.5/tutorial/floatingpoint.html)
- anim (AnimationDing0) – AnimationDing0 object
Returns: LocalSearchSolution – A solution (LocalSearchSolution class)
Note
Since Or-Opt is an intra-route operator, it has not to be checked if route can allocate (Route’s method can_allocate()) nodes during relocation regarding max. peak load/current because the line/cable type is the same along the entire route. However, node order within a route has an impact on the voltage stability so the check would be actually required. Due to large line capacity (load factor of lines/cables ~60 %) the voltage stability issues are neglected.
(Inner) Loop variables:
- s: length (count of consecutive nodes) of the chain that is moved. Values: 3..1
- i: node that precedes the chain before moving (position in the route tour, not node name)
- j: node that precedes the chain after moving (position in the route tour, not node name)
Todo
- insert literature reference for Or-algorithm here
- Remove ugly nested loops, convert to more efficient matrix operations
-
operator_relocate
(graph, solution, op_diff_round_digits, anim)[source]¶ applies Relocate inter-route operator to solution
Takes every node from every route and calculates savings when inserted into all possible positions in other routes. Insertion is done at position with max. saving and procedure starts over again with newly created graph as input. Stops when no improvement is found.
Parameters: - graph (NetworkX Graph Obj) – A NetworkX graaph is used.
- solution (BaseSolution) – BaseSolution instance
- op_diff_round_digits (float) –
Precision (floating point digits) for rounding route length differences.
Details: In some cases when an exchange is performed on two routes with one node each, the difference between the both solutions (before and after the exchange) is not zero. This is due to internal rounding errors of float type. So the loop won’t break (alternating between these two solutions), we need an additional criterion to avoid this behaviour: A threshold to handle values very close to zero as if they were zero (for a more detailed description of the matter see http://floating-point-gui.de or https://docs.python.org/3.5/tutorial/floatingpoint.html)
- anim (AnimationDing0) – AnimationDing0 object
Returns: LocalSearchSolution – A solution (LocalSearchSolution class)
Note
(Inner) Loop variables:
- i: node that is checked for possible moves (position in the route tour, not node name)
- j: node that precedes the insert position in target route (position in the route target_tour, not node name)
Todo
- Remove ugly nested loops, convert to more efficient matrix operations
-
solve
(graph, savings_solution, timeout, debug=False, anim=None)[source]¶ Improve initial savings solution using local search
Parameters: - graph (NetworkX Graph Obj) – Graph instance
- savings_solution (SavingsSolution) – initial solution of CVRP problem (instance of SavingsSolution class)
- timeout (
int
) – max processing time in seconds - debug (bool, defaults to False) – If True, information is printed while routing
- anim (AnimationDing0) – AnimationDing0 object
Returns: LocalSearchSolution – A solution (LocalSearchSolution class)
ding0.grid.mv_grid.solvers.savings module¶
Based on code by Romulo Oliveira copyright (C) 2015, https://github.com/RomuloOliveira/monte-carlo-cvrp Originally licensed under the Apache License, Version 2.0. You may obtain a copy of the license at http://www.apache.org/licenses/LICENSE-2.0
-
class
ding0.grid.mv_grid.solvers.savings.
ClarkeWrightSolver
[source]¶ Bases:
ding0.grid.mv_grid.solvers.base.BaseSolver
Clark and Wright Savings algorithm solver class
-
compute_savings_list
(graph)[source]¶ Compute Clarke and Wright savings list
A saving list is a matrix containing the saving amount S between i and j
S is calculated by S = d(0,i) + d(0,j) - d(i,j) (CLARKE; WRIGHT, 1964)
Parameters: graph (NetworkX Graph Obj) – A NetworkX graaph is used. Returns: list
of Node – List of nodes sorted by its savings
-
solve
(graph, timeout, debug=False, anim=None)[source]¶ Solves the CVRP problem using Clarke and Wright Savings methods
Parameters: - graph (NetworkX Graph Obj) – A NetworkX graaph is used.
- timeout (
int
) – max processing time in seconds - debug (bool, defaults to False) – If True, information is printed while routing
- anim (AnimationDing0) –
Returns: SavingsSolution – A solution
-
-
class
ding0.grid.mv_grid.solvers.savings.
SavingsSolution
(cvrp_problem)[source]¶ Bases:
ding0.grid.mv_grid.solvers.base.BaseSolution
Solution class for a Clarke and Wright Savings parallel algorithm
-
can_process
(pairs)[source]¶ Returns True if this solution can process pairs
Parameters: pairs ( list
of pairs of Route) – List of pairsReturns: bool – True if this solution can process pairs.
-
clone
()[source]¶ Returns a deep copy of self
Function clones:
- routes
- allocation
- nodes
Returns: SavingsSolution – A clone (deepcopy) of the instance itself
-