4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Check this out: jucs.org/jucs_16_3/mobile_agent_routing_with/… $\endgroup$ – George Jun 23 '13 at 13:15
  • 8
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jun 23 '13 at 14:16
  • 1
    $\begingroup$ Setting the time to infinity would give you the longest path, so this problem is strongly NP-Hard. $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 23 '13 at 17:18
  • 2
    $\begingroup$ @ChandraChekuri comment->answer please ? so the system doesn't keep bring this question back to life ? $\endgroup$ – Suresh Venkat Jun 24 '13 at 23:47
  • 1
    $\begingroup$ @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 $\endgroup$ – Radu-Stefan Zugravu Jul 6 '13 at 20:58

Your Answer

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

Browse other questions tagged or ask your own question.