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.

Answer 3

This is a traveling salesman problem with a modification adding the working window constraint... which means the solution to this problem will be even harder to find than the standard traveling salesman problem.

I've several approaches that work decently to give approximate solutions.

1. Genetic Algorithms
2. Tabu Search
3. Randomized Algorithm (E.g., Random Walk)

I don't know if applies to your problem, off the top of my head I say it doesn't, but dynamic programming can occasionally be used on intractable problems.

Answer 4

There is a lot of work on this problem. It goes by different names

1. traveling salesman (vehicle routing) problem with time windows and precedence constraints.
2. Pick-up and delivery problem.

There is a host of research on this problem, a lot of it in the Operations Research Journals. This problem is in general, NP-Hard, so a general exact solution to the problem as you described the problem is not practical, but there might be good, exact or approximate solutions to your specific problem. The best algorithm will be a function of your data.

• How big is your dataset. If the "n" is relatively small (30-100) then an exact solution with math programming is likely possible.
• How tight are the time-windows and precedence constraints. If the number of possible locations to visit in any time window is small, then a solution like dynamic-programming is possible.
• If you can't find a special case, then you probably want to combine a heuristic construction algorithm with a local-search post-processor. An simple alternative is the so-called GRASP heuristic, where you
• take an existing construction heuristic,
• randomize is so that multiple runs will give you multiple solutions,
• run the randomized version multiple times
• take the best solution that results.