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 pairs
Returns: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) – Descr
Returns: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.
length()[source]

Returns the solution length (or cost)

Returns:float – Solution length (or cost).
process(node_or_pair)[source]

Processes a node or a pair of nodes into the current solution

MUST CREATE A NEW INSTANCE, NOT CHANGE ANY INSTANCE ATTRIBUTES

Parameters:node_or_pair (type) – Desc
Returns:type – A new instance (deep copy) of self object

Todo

Not yet implemented

routes()[source]

Returns a generator for iterating over solution routes

Yields:type – Generator for iterating over solution routes.
class ding0.grid.mv_grid.solvers.base.BaseSolver[source]

Bases: object

Base algorithm solver class

solve(data, vehicles, timeout)[source]

Must solves the CVRP problem

Must return BEFORE timeout

Must returns a solution (BaseSolution class derived)

Parameters:
  • data (type) – Graph instance
  • vehicles (int) – Vehicles number
  • timeout (int) – max processing time in seconds

Todo

Not yet implemented

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 pairs
Returns: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
is_complete()[source]

Returns True if this is a complete solution, i.e, all nodes are allocated

Todo

TO BE REVIEWED

Returns:bool – True if this is a complete solution.
process(pair)[source]

Processes a pair of nodes into the current solution

MUST CREATE A NEW INSTANCE, NOT CHANGE ANY INSTANCE ATTRIBUTES

Returns a new instance (deep copy) of self object

Parameters:pair (type) – description
Returns:type – Description (Copy of self?)

Module contents