Tabu algorithm violates resource constraints

[Kuifje02]

Describe the bug The tabu algorithm violates resource constraints

To Reproduce

# graph definition :
G = nx.DiGraph(directed = True,n_res=2)
G.add_edge("Source", 1, weight=10, res_cost=np.array([1,1]))
G.add_edge("Source", 2, weight=10, res_cost=np.array([1,1]))
G.add_edge("Source", 3, weight=10, res_cost=np.array([1,1]))
G.add_edge(1, "Sink", weight=-10, res_cost=np.array([1,0]))
G.add_edge(2, "Sink", weight=-10, res_cost=np.array([1,0]))
G.add_edge(3, "Sink", weight=-10, res_cost=np.array([1,0]))
G.add_edge(3, 2, weight=-5, res_cost=np.array([1,1]))
G.add_edge(2, 1, weight=-10, res_cost=np.array([1,1]))

# resource limits
max_res, min_res = [len(G.edges()),2], [0,0]

# solve with tabu
path = cspy.Tabu(G, max_res, min_res).run()
print(path)

# solve with BiDirectional
path = cspy.BiDirectional(G, max_res, min_res, direction="both").run()
print(path)

Expected behavior

# Tabu path :
['Source', 3, 2, 1, 'Sink'] 
# Bidirectional path
['Source', 2, 1, 'Sink']

In other words, the Tabu path seems to violate the second resource constraint, as path Source-3-2-1-Sink consumes 3 units of the second resource, and max_res = [M,2]. The bidirectional version seems to work.

[torressa]

Hi @Kuifje02! Cheers for the bug. I've dug into it and realised there was a problem with the heuristic function used to call the networkx algorithm astar_path. I've been making some changes so will fix soon!

[torressa]

Created a test file with the example tests_issue20.py. It seems to work now.