cspy.Tabu

Simple Tabu-esque algorithm for the (resource) constrained shortest path problem.

Parameters

Gobject instance nx.Digraph()

must have n_res graph attribute and all edges must have res_cost attribute.

max_reslist of floats

[M_1, M_2, ..., M_{n\_res}] upper bounds for resource usage (including initial forward stopping point).

min_reslist of floats

[L_1, L_2, ..., L_{n\_res}] lower bounds for resource usage (including initial backward stopping point). We must have len(min_res) = len(max_res).

preprocessbool, optional

enables preprocessing routine. Default : False.

algorithmstring, optional

shortest path algorithm to use. Options are “simple” or “astar”. If the input network has a negative cycle, the “simple” algorithm is automatically chosen (as the astar algorithm cannot cope).

max_depthint, optional

depth for search of shortest simple path. Default : 1000. If the total number of simple paths is less than max_depth, then the shortest path is used.

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

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. See Using cspy

Example

To run the algorithm, create a Tabu instance, call run, and then query the attributes of interest: path, total_cost, or consumed_resources.

>>> from cspy import Tabu
>>> 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('A', 'C', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('B', 'C', res_cost=array([2, 1]), weight=-1)
>>> 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('F', 'Sink', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('E', 'Sink', res_cost=array([1, 1]), weight=1)
>>> max_res, min_res = [5, 5], [0, 0]
>>> tabu = Tabu(G, max_res, min_res)
>>> tabu.run()
>>> print(tabu.path)
['Source', 'A', 'C', 'D', 'E', 'Sink']