0
$\begingroup$

I am wondering if there is any existing algorithm for the following routing problem.

Let's suppose that you are given a directed graph where the edges are labeled with a weight indicating a cost. Each node belongs to a POI (point-of-interest) such as restaurants, grocery stores, etc. Given a set of POIs you have to visit, what is the shortest route from a node X to Y, visiting all the POIs given you? (e.g., "I have to go to my office from my house. On the way, I have to visit a grocery store, a department store, and a gas station. What is the shortest route?)

I tried to find if there was any literature on this problem but could not find any. Does anybody know this type of problem and any solution?

Thanks

$\endgroup$
1
  • 1
    $\begingroup$ This sounds strictly harder than the traveling salesman problem, which would mean it's NP-complete. $\endgroup$ Oct 11, 2013 at 0:25

1 Answer 1

1
$\begingroup$

Unfortunately, it sounds like you might be describing the Travelling Saleman Problem. The good news is that this is a problem that has been studied in tremendous detail. The bad news is that the problem is NP-Hard, which basically means that it cannot be solved in polynomial time.

Having said that, there are many approaches that you can take that will either give you the exact answer for small problems, or for larger problems will converge to a solution that is good, but is not guaranteed to be optimal.

EDIT:

It may seem at first blush that your problem is easier than the travelling salesman problem. After all, you don't need to visit the grocery store, you only need to visit a grocery store. However, I would posit that choosing a path that visits $N$ points of interest in the graph given a set of constraints is strictly harder than solving a travelling salesman problem with $N$ cities. Consider the traditional TSP to be a specific case of your problem in which there is only one grocery store to choose from, and only one gas station, etc. This simplified version of your problem reduces to solving TSP.

Whether or not your problem is harder than TSP, I think that your best bet is to adapt existing TSP algorithms to your specific scenario. While none of these can guarantee the optimal solution in polynomial time, I think that you will find that they can fairly quickly converge to a satisfactory solution in a very reasonable amount of time.

$\endgroup$
3
  • $\begingroup$ It is not TSP because TSP requires visiting all nodes in the graph whereas my problem is to visit only a subset of the nodes, satisfying some constraints... $\endgroup$
    – DSKim
    Oct 11, 2013 at 4:12
  • $\begingroup$ See my response as an edit to the post. $\endgroup$
    – nispio
    Oct 11, 2013 at 5:30
  • 1
    $\begingroup$ @DSKim But if you find a general algorithm to solve this problem in general, that algorithm should work in all situations. In particular that algorithm must work in the particular case when all the POI are 1 element sets. And then you have the TSP. $\endgroup$
    – N. S.
    Oct 11, 2013 at 5:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .