Searching 4 graph optimization software

[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...

 

[AntistatiK]

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...

 

[A David]

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.