Shortest path with nodes containing collectibles of negative cost
This is NP-Complete, by reduction from Traveling Salesman Problem (TSP).

Take any TSP.  Give every city an extremely large "negative-benefit," and set the origin city as both the start and finish.  Now running a solver for your problem will give the solution to the TSP.



I'm not sure of any "efficient heuristics", but if you remove the condition that nodes are allowed to be visited twice, the problem becomes much easier.  If you subtract every nodes' "negative benefit" from all its incoming edges, it becomes a normal shortest path problem.