# Path finding algorithm to maximise points of interest along the route

I am trying to write an algorithm to find a path (not the shortest one) between a given start and end point.

An user will enter the start location, the end location and the available time to travel. For each edge of my graph I know the cost in time to traverse that edge and the gain in points of interest along that edge. I want to find the path witch maximises the gain in points of interest and falls within the given time.

Until now I only found references to A Star routing algorithm or optimisations to it witch only compute the shortest path.

Could you please give me some hints on what algorithm should I use or some references to solutions of similar problems? This algorithm is an important part of my Dissertation.

Thank you,
Radu-Stefan

• Check this out: jucs.org/jucs_16_3/mobile_agent_routing_with/… – George Jun 23 '13 at 13:15
• This is called the Orienteering problem in the operations research/algorithms literature. It is NP-Hard (easy to prove this via a reduction from the Hamiltonianian Cycle Problem). Approximation algorithms are known in both undirected and directed graphs. A simple Google scholar search on orienteering will bring up several. – Chandra Chekuri Jun 23 '13 at 14:16
• Setting the time to infinity would give you the longest path, so this problem is strongly NP-Hard. – BlueRaja - Danny Pflughoeft Jun 23 '13 at 17:18
• @ChandraChekuri comment->answer please ? so the system doesn't keep bring this question back to life ? – Suresh Venkat Jun 24 '13 at 23:47
• @ChandraChekuri thank you for you comment. A simple Google scholar search really did the job. I found the following paper very useful: cs.uiuc.edu/~chekuri/papers/orienteering-journal.pdf – Radu-Stefan Zugravu Jul 6 '13 at 20:58