TSP with time windows?
evilC
help me greatly even as-is.
However, the problem I face is of a rather more complicated nature - I
need to solve the TSP with time windows (As in "opening hours" or some
other similar concept).
Obviously this creates a connundrum if it is not possible to visit all
locations, so this would need to be handled accordingly (ie the route
that takes in the most).
How difficult would this be? A complete re-write of the logic?
Regards
Clive
Geir Kokkvoll Engdahl
BpTspSolver actually features three different solvers, and the
difficulty of your problem depends on which one of these three you
wish to modify. I think modifying tspBruteForce will be quite easy,
but this solver only works efficiently for up to 10 - 12 locations.
Then there is tspDynamic, which gets you up to ~20 locations (if you
have enough memory available to javascript, that is). The tspDynamic
routine will be much harder to modify. Then there is tspAntColonyK2,
which does not always yield the best solution, but produces good
solutions for up to 100 locations. It is not as hard as tspDynamic to
modify, the hardest part is probably the K2-rewiring, which is
optional (but does improve the solutions a lot).
Geir
evilC
I would say that a maximum of 10-12 would be quite adequate. I would
envisage normal usage to be 4-5 nodes.
I take it that all that bruteforce does is go through all possible
combinations and add up the time for each one?
If so, I could see that being not too hard to modify.
I would be grateful for any pointers you could give.
Geir Kokkvoll Engdahl
You're basically right. Brute force goes through all possible
combinations (or rather permutations). You only need to add an extra
check to ensure that the time windows are satisfied for each
permutation (order). Then there is the questions what to do when no
solution is possible. You could try all subsets of size N-1, then N-2,
and so on. This will require new code, but isn't all that hard.
Geir