Path finding algorithm to maximise points of interest along the route

Question

5.00/5 (1 vote)

See more:

Hi,

I am trying to write an algorithm to find a path (not necessarily 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 eadge of my graph I know the cost in time to traverse that edge and the gain in points of interest along that edge.

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?

Thank you,
Radu-Stefan

Posted 22-Jun-13 22:43pm

Radu-Stefan Zugravu

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Bernhard Hiller · Answer 1 · 2013-06-23T20:40:00

Routing algorithms try to minimize costs - measured by the distance or by the travel time. I'd naively try to translate your problem into such an optimization. I am not sure whether following idea works:
Assume a number of POIs per travel time (take the maximum or a value above it). When you now calculate the costs of your segments, use the difference between that value and the number of POIs encountered along that segment as a measure for "missed POIs". And then use the common algorithms for minimizing the number of missed POIs.
I fear that the constraint of the available time might not always be met.