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 have res_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

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']