# Searching 4 graph optimization software

• AntistatiK
The problem is often called "the traveling salesman problem" or "route optimization". The problem can be solved in polynomial time provided you have a list of the vertices and the connections between them. However, in this particular case, the traveling hauler problem, the goal is not to simply find the shortest path, but to find the path with the highest connection score. This means that some vertices may have to be connected even if it doesn't make the path shorter. In summary, the author is looking for a software that can solve a problem he has identified, but is not aware of any that does. He has found a way to solve the problem in polynomial time, but is waiting forf

#### AntistatiK

I'd like 2 solve the following problem (well, routinely solve a bunch of such problems):
Let us have a number of points (vertices), that can be interconnected. Not any 2 points are connected. Each connection is assigned a value. I want 2 find the maximum path in the graph, that is, the one with the highest connection score (of course, visiting any point only once). Optionally, scores may be direction-dependent, that is, the value of connecting point A 2 B is not necessary equal 2 the value of B -> A. Also optionally, I want 2 specify, or limit, the number of vertices (out of the whole set) I want 2 connect. Also optionally, I want some particular vertices 2 be included by all means.
I found that the problem of minimizing such score is well-known, call it route optimization, or "traveling postman (salesman)". But I haven't found the software that solves my particular problem. Maybe it's realized in a software suite, but I'm not aware of it. I'm waiting 4 your ideas...

Call it "the problem of traveling hauler", it's more intuitive. In the morning, he has a set of requests, such as "carry smth from A to B for \$N". If he's on the road with no cargo, traffic cops fine him, also he burns out expensive fuel. He wants 2 earn the highest sum by the end of the day...

Last edited:
Notice that if you make the scores negative then minimizing that path is that same as your maximization problem, i.e, your problem is still the traveling salesman problem.

What do you mean by "Not any 2 points are connected"? I read this as meaning your graph doesn't have any connections.

There do exist ways to solve the problem, but none computes in polynomial time. That is, there isn't a known way to solve it other than trying all the possible paths then picking the shortest one.