I'm looking for an algorithm to solve this problem.

I have a region in which there are several areas identify by its id and x,y,z position. I've made a graph in which each vertex identifies one ot these areas (for a max of 200 vertex). From a start point S, I know the cost, specified in seconds and inserted in the arch (so only integer values), to reach each vertex from each other vertex (a complete graph). When I visit a vertex I get a reward (float valiues).

My objective is to find a paths in a the graph that maximize the reward but I'm subject to a cost constraint on the paths. Indeed I have only limited minutes to complete the path (for example 600 seconds.)

The graph is made as matrix adjacency matrix for the cost and reward (but if is useful I can change the representation).

I can visit vertex more time but with one reward only!

I think to find the optimum solution is a np-hard problem, but also an approximate solution is apprecciated :D


I'm trying study how to solve the problem with branch & bound...

  • $\begingroup$ Finding the optimal solution is NP-hard, yes. Give every edge cost equal the Euclidean distance between them and give each vertex reward $1$. The question "Is the maximum reward from distance $d$ equal to the number of vertices?" is the decision version of Euclidean TSP. (Using Euclidean distances means there's no advantage in returning to a vertex you've visited before, so guarantees that a solution really is equivalent to a TSP solution.) $\endgroup$ – David Richerby Dec 19 '14 at 14:34
  • $\begingroup$ @user1990169 Good point! Fixed. $\endgroup$ – David Richerby Dec 19 '14 at 14:34

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.