Graph search problem with route restrictions
- by Darcara
I want to calculate the most profitable route and I think this is a type of traveling salesman problem.
I have a set of nodes that I can visit and a function to calculate cost for traveling between nodes and points for reaching the nodes. The goal is to reach a fixed known score while minimizing the cost.
This cost and rewards are not fixed and depend on the nodes visited before.
The starting node is fixed.
There are some restrictions on how nodes can be visited. Some simplified examples include:
Node B can only be visited after A
After node C has been visited, D or E can be visited. Visiting at least one is required, visiting both is permissible.
Z can only be visited after at least 5 other nodes have been visited
Once 50 nodes have been visited, the nodes A-M will no longer reward points
Certain nodes can (and probably must) be visited multiple times
Currently I can think of only two ways to solve this:
a) Genetic Algorithms, with the fitness function calculating the cost/benefit of the generated route
b) Dijkstra search through the graph, since the starting node is fixed, although the large number of nodes will probably make that not feasible memory wise.
Are there any other ways to determine the best route through the graph? It doesn't need to be perfect, an approximated path is perfectly fine, as long as it's error acceptable.
Would TSP-solvers be an option here?
