Longest circle in graphs

Question

Hi folks,

I want to solve the following problem:

I have a DAG which contains cities and jobs between them that needs to be done. The jobs are for trucks which can load a definied limit. The more the truck is loaded the better is the tour. Some jobs are for loading something in and some are for loading defined things out. You can always drive from city a to b even if there is no job to be done between them. The last restriction is that I always need to start in city a and return to a because there is the home of the trucks :)

I first thought of Dijkstra's shortest path algorithm. I could easly turn that into longest path calculation. My problem in mind is now that all these algorithms are for calculating a shortest or longest path from vertex a to b, but I need it from a returning to a - in a circle.

Has some one some kicks for my mind?

Thanks for your feedback!

Marco

Answer 1

This crazy combination of knapsack and travelling salesman is surely NP-hard.

Virtually everywhere, when you want to load your agent with optimal job schedule, or when you want to build a route through all vertexes in the graph, or when you feel that you need to look for a "longest path*", you most likely run into an NP-complete or an NP-hard problem.

That means, that there is no known fast and exact solution to the problem, i.e. the one that runs in a polynomial time.

So you have to create approximations and implement non-optimal algorithms based on your particular conditions. What time loss is acceptable? Are there additional patterns the trucks can drive? Do you know more about the graph (e.g. is the area divided into distant dense regions)? Answer these questions and you'll find a non-strict heuristics that satisfies your customers.

---

*yes, searching for longest paths is not as easy as you think. Longest path problem is NP-complete, given that your graph is not acyclic.

Answer 2

You can adjust the traveling sales man problem dynamic programming algorithm to do what you want.

The classic approach says that you want to maximize the optimum function from all cities but you can take in consideration, at each step also the possibility of returning home.

And like Pavel mentioned, this problem is definitively NP-hard. Do you have some upper bounds for the number of cities or maximum number of objects that can be loaded in a truck?

PS: Do you want the BEST solution (maximum profit - might not be realistic in terms of processing time) or you accept some approximation?

Answer 3

You're trying to find the smallest possible way to get everything done? This reminds me of a max-flow/min-cut problem. You might be able to approximate the best answer by:

• Connect all terminal nodes to a final end node.
• Run one of the various maximum flow algorithms to find the max flow between a and end.
• Return to city a. Update the graph to reflect what you just did. Repeat until all jobs are done.

The idea is that you get the most bang for every trip. Each trip after the 1st will be less efficient and less efficient, but that's to be expected.

Note: This only works because you have a DAG. Travelling salesman wouldn't be NP-Complete on a DAG, either, and it will likely be impossible to even hit all nodes on the graph. Re-reading your problem, it seems like you don't have a DAG, since you can return to city a - is that true?

Answer 4

Isn't this a Transportation problem?

Depending on the trucks number and starting points, you could add a fake transporations or add costs in order to satisfy your restrictions.

I'd also ask about truck restrictions:

• are they all based in the same city?
• do you have a fixed number of them?
• and what you win if you use less then you have?
• is there a cycle time restriction?