Pathfinding algorithm to maximize profit

user_14062063 0
Viewed 472

Say we have a directed graph where each edge contains a tuple (d,p) where d is the distance that must be traveled and p is the profit you'll get by traversing that edge, and after traversing an edge, it's profit is set to 0. My question is, given a starting node and maximum distance D (such that Σd < D across all edges traversed), solve for the maximum profit, where profit is defined as Σp across all edges traversed.

You can revisit nodes and re-traverse edges.

I've attempted to modify dijkstra to no success, since dijkstra doesn't know when to stop it's flood fill, and as far as I can tell there's no way to guarantee the best solution with dijkstra before checking all possibilities. I've also looked into variations of TSP, and this problem seems much more path-finding related. Any references, pseudocode, or already understood algorithms would be appreciated. I am, of course, not looking for brute-force algorithms.

path-finding graph-algorithm graph algorithm
1 Answers

Given the scale of the problem, we might have success attacking it with an integer program. For each directed edge e, let x(e) be a nonnegative integer variable representing the number of times we use the edge, and y(e) be a 0-1 variable representing the number of times we profit from the edge. For each vertex v, let w(v) be a 0-1 variable indicating whether v is visited, and z(v) be a 0-1 variable indicating whether v is the ending vertex. The easy part of the integer program is

maximize sum_e p(e) y(e)
subject to
y(e) <= x(e)            # can't profit from an edge if we don't use it
for all e, y(e) <= w(head(e))    # can't profit unless we visit
for all e, y(e) <= w(tail(e))    # can't profit unless we visit
sum_e d(e) x(e) <= D    # bounded distance
sum_v z(v) = 1          # exactly one ending vertex
# path constraints
for all vertices v, sum_{e with head v} x(e) - sum_{e with tail v} x(e) =
    z(v) - 1 if v is the starting vertex,
    z(v)     otherwise.

The hard part is preventing cycles to nowhere (analog of the subtour elimination constraint for TSP). If we manage this, then we can find an Euler trail in the subgraph whose edges have multiplicity indicated by the y(e).

We take the same strategy as TSP -- write an exponential number of constraints, enforce them post hoc.

for all sets of vertices S containing the starting vertex,
    for all vertices v not in S,
        sum_{directed edges e entering S} y(e) >= w(v)
user_21446690
Related