Algorithm: Voyage planning

Question

I need to plan a voyage connecting n locations in the sea with a specified origin and specified destination with following constraints.
The voyage has to touch all locations.
If there is a reservation from A to B then a has to be touched before B
The time spend at each location varies (depends upon the reservations to that location)
Each location has a working window. If the vessel reaches before working window it has to wait.
Note: "Minimum spanning tree" algorithms may not be as the time required at each port depends on the previous route (due to working window)
Is there any algorithm available for this?

Answer 1

See Traveling salesman problem

Answer 2

Ant colony optimization seems to be the best known solution to this. Note that this is a NP problem, actually even a NP-complete problem. This means it's "easy" to verify a solution being correct, but it's "hard" to find it. The only way to find the "optimum" solution would be to try all possible solutions, compare the results and take the best one. Of course that is not acceptable if you want to solve it within a reasonable time frame.

The ACO algorithms will find a good solution, close to the optimum. I say close, as AFAIK it can't guarantee to always find the best one. Better solutions might exist. However, often is not necessary to really find the best solution possible, a solution that is just "very good" will do the trick and here ACO is exactly what you are looking for. It can find the solution in reasonable time intervals and the solution will be good for sure.

In your case you need to modify it a bit. Usually it will only try to find the shortest route, only taking the path into account. In your case it must take your working window, reservations and time spent on a location into account. But these are just modifications of "how the ants travel", the basic algorithm stays the same and will still work the same.