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 \geq 5.- max_reslist of floats
[M_1, M_2, ..., M_{n\_res}] upper bounds for resource usage.
- min_reslist of floats
[L_1, L_2, ..., L_{n\_res}] 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
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']