Route planning algorithms

[helios]

Given a network of nodes and directed edges with costs and benefits associated with traversing the edges, I want to find a route (i.e. a "walk" in graph theory terminology) that maximizes the total benefit and minimizes the total cost. The route should start in a node "near" a reference node.

Is there a class of algorithms that does this? Even just a search term is fine.

[Albatross]

Important questions:
Are there any restrictions on how many nodes are visited?
Is there a specified end node?
Are benefit and cost necessarily distinct or can they be combined into net benefit?
How large is your graph?

-Albatross

[helios]

1. Yes, the user may input a desired number of edges to traverse (generally <20), and the best route with that many edges should be displayed, or a few of the best routes should be displayed.
2. No, routes may end in any node.
3. No, cost and benefit are incomparable and there is no mapping between the two.
4. Roughly 50k nodes and 500M edges, IIRC. Most edges are very low benefit, though.

EDIT: Oh, also: The benefit of an edge may in some cases vary depending on which other edges have been previously traversed.

[tition]

I just realized I did not read carefully your formulation. I don't think I have seen an exact answer to your question anywhere, but I'd browse the following topics:
0. The most relevant things I found so far:
https://en.wikipedia.org/wiki/Shortest_path_problem
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
If you make your benefits negative then you are in fact searching for a shortest path.

1. This is not directly relevant, but I would read the intro to the Max-Flow-Min-Cut-Theorem
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

2. I would also browse the wikipedia article on linear optimization/simplex algorithm: that will simply give you more background on/generalizations of the previous topic. in case you are not happy with the travelling salesman approach, this may help you reformulate your problem to something that may be more approachable. Once again, this is not the original problem you are asking, but if your problem is hard enough, you may need to admit defeat and settle for a simplification.


2. I'd also review the traveling salesman problem: not sure how relevant is that to your case...
https://en.wikipedia.org/wiki/Travelling_salesman_problem
I remember that's an NP hard problem, so no expectation of a "good" algorithm. I think your problem is a modification of this problem - a modification that makes it harder than it already is - you seem to be optimizing against multiple costs functions, not to mention of the possibility that traversing edges modifies the cost function.

[booradley60]

Is there any benefit in splitting the problem into two graphs? A graph with only benefit edges and a graph with only cost edges?

[helios]

booradley60: I don't think that would make sense.

tition:
0. Now that you mention it, yes, I believe my current solution is equivalent to Dijkstra's algorithm, where the arrival condition is determined solely by the number of edges that have been traversed. Using cost-benefit as the distance function doesn't make sense in this case, though. I'm using -benefit/cost.
My current algorithm is:

1. Find all nodes within a certain radius from "home".
2. Find all outgoing edges for those nodes.
3. Reverse sort by benefit.
4. Drop bottom 75%. (This is mainly to ignore the tremendous number of worthless edges.)
5. Reverse sort by benefit/cost.
6. Drop bottom 50%.
(At this point, my test case shows 1M edges remaining.)
7. If step 6 has been performed target times, take top n walks and terminate.
8. Append to all edges all subedges, cloning walks as necessary.
9. Go to step 3.

1. Perhaps there's a specific way to interpret that result, but I don't see how it applies to my problem.

2. Can you recommend a gentle introduction? I don't really know that much about optimization.

I don't actually need to find the optimal solution. Specially not if every edge needs to be checked, which it obviously does. In such a large problem space there's bound to be a large number of "good enough" solutions.

[tition]

@helios: nope, I know of no gentle introduction to linear optimization.

Linear optimization tells you how to compute with sets determined by systems of linear >= inequalities (those are simply n-dimensional polyhedra, with infinite walls, edges, ... allowed). In particular, it tells you how to compute whether a set of linear inequalities 1) has a solution and 2) how to find the max/min of a linear function over such a set.

Unless you need to use this in practice, the above summary is all you need to know. It is also good to know that many problems related to flows in graphs can transformed to problems about minimizing/maximizing a linear function over a set given by linear inequalities.

It seems you have your solution for now (until your problem specs change hehe ...), so those algorithms are just in case you are interested - and of course, you never know when some application of those may pop up randomly ...

[helios]

Okay, I have a working solution. The algorithm is pretty much the same as above, only that the vector of edges is hard-limited to 100k elements instead of pruning a percentage, or the memory usage went out of control. I also had to modify the DB queries to eliminate 99.43% of the dataset (all edges with a profit <1000).

What I'm working on is a tool similar to https://eddb.io/trade/hops except, whereas that one can only search routes from a specific location and only attempts to maximize profit, mine searches all routes that start in a sphere and can also maximize efficiency (profit/cost), where cost is an approximation of the real time seconds a player will have to put in to complete the route. This prevents the situation where the player must visit a station that requires around 10 minutes of real time travel.