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

<p>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.</p>

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

<p>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.</p>

<p>Thank you,<br>
Radu-Stefan</p>

CC BY-SA 3.0
2013-06-23T13:15:54.347Z
Check this out: http://www.jucs.org/jucs_16_3/mobile_agent_routing_with/jucs_16_03_0372_0401_camponogara.pdf
George
CC BY-SA 3.0
2013-06-23T14:16:51.027Z
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
CC BY-SA 3.0
2013-06-23T17:18:43.350Z
Setting the time to infinity would give you [the longest path](http://en.wikipedia.org/wiki/Longest_path_problem), so this problem is *strongly* NP-Hard.
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-06-24T23:47:49.573Z
@ChandraChekuri comment->answer please ? so the system doesn't keep bring this question back to life ?
Suresh Venkat
CC BY-SA 3.0
2013-07-03T14:51:18.467Z
I have used Bioinspired algo: [Ant Colony Optimization Routing Algorithm with Tabu Search](http://www.iaeng.org/publication/IMECS2010/IMECS2010_pp2104-2107.pdf) with reference to your exact problem statement for [my conference paper](http://searchdl.org/index.php/conference/view/430)
Yoshi
CC BY-SA 3.0
2013-07-06T20:58:42.197Z
@ChandraChekuri thank you for you comment. A simple Google scholar search really did the job. I found the following paper very useful: http://www.cs.uiuc.edu/~chekuri/papers/orienteering-journal.pdf
Radu-Stefan Zugravu
<graph-algorithms><shortest-path>
Path finding algorithm to maximise points of interest along the route
Radu-Stefan Zugravu
# Path finding algorithm to maximise points of interest along the route

(Asked by: username_0 on 2013-06-23)

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

**Tags:** graph-algorithms, shortest-path
> **Comments:**
> **username_1**: Check this out: http://www.jucs.org/jucs_16_3/mobile_agent_routing_with/jucs_16_03_0372_0401_camponogara.pdf  
> **username_2**: 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.  
> **username_3**: Setting the time to infinity would give you [the longest path](http://en.wikipedia.org/wiki/Longest_path_problem), so this problem is *strongly* NP-Hard.  
> **username_4**: @ChandraChekuri comment->answer please ? so the system doesn't keep bring this question back to life ?  
> **username_5**: I have used Bioinspired algo: [Ant Colony Optimization Routing Algorithm with Tabu Search](http://www.iaeng.org/publication/IMECS2010/IMECS2010_pp2104-2107.pdf) with reference to your exact problem statement for [my conference paper](http://searchdl.org/index.php/conference/view/430)  
> **username_0**: @ChandraChekuri thank you for you comment. A simple Google scholar search really did the job. I found the following paper very useful: http://www.cs.uiuc.edu/~chekuri/papers/orienteering-journal.pdf  

---

## 0 answers

