0
$\begingroup$

I've got an TSP problem which I can't seem to solve somehow. It consists of about 1200 addresses for which all distances (measured in seconds) between them, a frequency (once a week, twice a week, 3 times a week etc...) and cargo-weight are given.

I've looked into TSP solutions, but they only seem to offer ways to calculate the shortest route, not divide addresses over multiple routes.

I should divide these addresses over 5 days based on their frequency. Then for every day I should devide the adresses over 2 routes for a cargo-truck to drive.

Furthermore there are 3 constraints:

  • All routes should start and end at the same given address.
  • There is a maximum distance which all routes must not exceed.
  • A truck has a maximum cargo-space which it should not exceed, if it does the truck should go back to the starting point to pick up the rest of the cargo and then continue with its route.

I've tried solving this problem by constructing a TSP algorithm that consists of greedysearch as an initial route, and then proceeds with localsearch to find a local optimum. Then I'm trying to swap addresses between routes and checking whether the total distance has decreased afterwards.

I can check (optimize and find its distance) one set of routes in about 10-20 seconds, by using multi-threading. I could potentially reduce this by only checking the distance between the nodes that have changed (instead of the entire route), but even then I don't think it would affect the execution-time much since there are only ~120-130 nodes in every route and dictionary-lookups aren't that slow after all). And as you can probably imagine by now, this is so incredibly slow that it won't seem to solve the problem at all.

So far I haven't been able to find a solution that comes anywhere close to the target distance (I've managed 8000 without the constraints whereas it should be below 6000 with constraints) . This has all been WITHOUT implementing the constraints mentioned earlier (which should probably be done by applying certain penalties for constraints that aren't met).

What would be a smart/good way to approach this problem?

Thanks in advance!

$\endgroup$
  • $\begingroup$ What could be a plausible solution would be to approximate a route's optimal distance in a faster algorithm than localsearch. But this would need to finish in under, say, 1 or 2 seconds in order for me to be able to swap some nodes around and check them relatively fast (and would multithreading be smart if I would choose to do so? Since starting a thread takes some time aswell....) $\endgroup$ – Jean Jacques Dec 19 '17 at 13:29
  • $\begingroup$ It seems you're on the right track. But after swapping and checking whether the total distance has decreased, what do you do? Always undo if worse? You should use "simulated annealing" instead. $\endgroup$ – Albert Hendriks Dec 19 '17 at 22:36
  • $\begingroup$ I've looked into 3 approaches for this situation. The first being "swap whenever it's better than before", also calculating the best swap and executing that specific one, and lastly SA as you mentioned. But it seems to me that the SA approach runs even slower than the other 2... $\endgroup$ – Jean Jacques Dec 20 '17 at 19:09
  • $\begingroup$ It's normal to run for an hour or more to find a good solution to a planning problem like yours. SA should find a much better solution than your local search algorithm, but indeed it will take more time. $\endgroup$ – Albert Hendriks Dec 20 '17 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.