cspy.GRASP¶
Greedy Randomised Adaptive Search Procedure for the (resource) constrained shortest path problem. Adapted from Ferone et al 2019.
Parameters¶
- Gobject instance
nx.Digraph()
must have
n_res
graph attribute and all edges must haveres_cost
attribute. Also, the number of nodes must be .- max_reslist of floats
upper bounds for resource usage.
- min_reslist of floats
lower bounds for resource usage.
- preprocessbool, optional
enables preprocessing routine. Default : False.
- max_iterint, optional
Maximum number of iterations for algorithm. Default : 100.
- max_localiterint, optional
Maximum number of local search iterations. Default : 10.
- time_limitint, optional
time limit in seconds. Default: None
- thresholdfloat, optional
specify a threshold for a an acceptable resource feasible path with total cost <= threshold. Note this typically causes the search to terminate early. Default: None
- alphafloat, optional
Greediness factor 0 (random) –> 1 (greedy). Default : 0.2.
- REF_callbackREFCallback, optional
Custom resource extension callback. See REFs for more details. Default : None
Raises¶
- Exception
if no resource feasible path is found
- cspy.GRASP.consumed_resources¶
Get accumulated resources consumed along the path.
- cspy.GRASP.path¶
Get list with nodes in calculated path.
- cspy.GRASP.total_cost¶
Get accumulated cost along the path.
Notes¶
The input graph must have a n_res
attribute.
The edges in the graph must all have a res_cost
attribute.
Also, we must have len(min_res)
len(max_res)
.
See Using cspy
Example¶
To run the algorithm, create a GRASP
instance and call run.
>>> from cspy import GRASP
>>> from networkx import DiGraph
>>> from numpy import array
>>> G = DiGraph(directed=True, n_res=2)
>>> G.add_edge('Source', 'A', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('Source', 'B', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('Source', 'C', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('A', 'C', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('A', 'E', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('A', 'F', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('B', 'C', res_cost=array([2, 1]), weight=-1)
>>> G.add_edge('B', 'F', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('B', 'E', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('C', 'D', res_cost=array([1, 1]), weight=-1)
>>> G.add_edge('D', 'E', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('D', 'F', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('D', 'Sink', res_cost=array([10, 10]), weight=10)
>>> G.add_edge('F', 'Sink', res_cost=array([10, 1]), weight=1)
>>> G.add_edge('E', 'Sink', res_cost=array([1, 1]), weight=1)
>>> grasp = GRASP(G, [5, 5], [0, 0], max_iter=50,
max_localiter=10)
>>> grasp.run()
>>> path = grasp.path
>>> print(path)
['Source', 'A', 'C', 'D', 'E', 'Sink']