I need an algorithm to determine the best itinerary for a series of events.

Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each event is at a physical location thus it takes time to travel from event to event. It is not necessary to attend every event.

What itinerary will yield the largest total reward?

Does anyone know if there is an existing algorithm for this or one that would be easily adapted? Given the similarity to the traveling salesman problem I am tempted to start with a weighted TSP solution and work from there.

  • 3
    $\begingroup$ 1) Sort the events by time. 2) Dynamic programming: for each event, assuming that you visit this event, determine the best reward you can get by the time you visit this event. $\endgroup$ – Dmitry Aug 14 at 17:45
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Aug 14 at 19:08

We can construct a directed graph with events as vertices, where an event $E_2$ has an incoming edge from another event $E_1$ if starting from $E_1$, we can arrive $E_2$ in time to get its reward. The edge value is the time difference between the events.

For each vertex (event), we do a depth first search rooted at this vertex where on each iteration we add the value of the previous tree edge to the current tree edge and check to see if it is greater than the time associated with the current vertex. If it is then our considered sequence of events from the root vertex has just timed out.

var MaxReward = 0
var bestItinerary = []

  for vertex v in graph:
    _f(v, v.time, 0, [])

_f(v, curr_time, rewardSoFar):
  if time > v.time:
    if rewardSoFar > MaxReward:
      MaxReward = rewardSoFar
      bestItinerary = itinerarySoFar
    rewardSoFar = rewardSoFar + v.reward
    for edge, neighbor in v.getNeighbors:
      _f(neighbor, curr_time + edge.value, rewardSoFar, itinerarySoFar)
| cite | improve this answer | |

I figured out one solution to my problem.

I created a graph of all the events as nodes. I then drew directed edges from each event to all events which could be attended after (accounting for travel time). Thus every valid path through the graph is a valid order to visit events in chronological time. Each edge is weighted with the reward for the event it ends at.

With this graph the time component is removed from the problem and I can use standard graph traversal algorithms to find the longest/heaviest path.

| cite | improve this answer | |
  • $\begingroup$ The time component is not entirely removed because if a points to b, and a & b both point to c, then visiting c by first visiting b reduces our chances of making it to c in time. So there would be some invalid paths to not consider when computing the longest path. $\endgroup$ – droptop Aug 15 at 18:21
  • $\begingroup$ When I make the edges I compute the needed travel time for each and only add the edge if there is enough time. E.g, A is at t=0, B is at t=10, and C is at t=15; A-B takes 8s, A-C takes 10s, and B-C takes 4s. From A, I can go to B or C and make it on time. From B, I can go the C and make it on time (t=10 + 4 < 15). From C, I cannot go to B (t=15 + 4 > 10). In my actual use case, the time spent at each event is much smaller than the travel time so it can be safely ignored. $\endgroup$ – harryk Aug 16 at 13:53
  • $\begingroup$ what about going to c from a by via b? $\endgroup$ – droptop Aug 16 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.