Ideas for a heuristic traveling salesman solution with additional constraints

Safe movement

Here are some ideas for safely changing an existing valid solution:

• Any two consecutive stops can always be swapped if they are both pickups or both. This is obviously true for the "both deliveries" case; for the case of "both pickups": if you had room to pick up A, then pick up B without delivering anything in between, then you have the option of first picking B, then picking A. (Actually a more general rule: perhaps : in any sequence with pure delivery or pure reception of consecutive stops, the stops can be rearranged arbitrarily, but listing all the possibilities can get prohibitive for long sequences, and you should benefit greatly from considering only pairs.)
• Pickup A can be replaced by any subsequent delivery of something else B, provided that the original pickup appears after B has been picked up and its own delivery after the initial delivery of B. In the special case where pickup A is immediately followed by B delivery , they can always be swapped.
• If there is a delivery of an item of size d followed by a pickup of an item of size p, then they can be swapped provided there is enough extra room: in particular, provided that f> = p, where f is the free space available before delivery. (We already know that f + d> = p, otherwise the original schedule would not be possible - this is a hint of looking for small supplies to apply this rule.)

If you start with purely random generated schedules, just try all the possible moves, greedily pick the best, apply it, and then repeat until no more steps lead to improvement, this will give you a big improvement in quality!

Relational solutions

It is very helpful to have a way to score the solution so that they can be ordered. The good thing about counting is that it's easy to include severity levels: just as the first digit of a two-digit number is more important than the second digit, you can make an estimate so that more important things (like deadlines) get much more weight than less important ones. things (such as total travel time or distance). I would suggest something like 1000 * num_deadline_violations + total_travel_time

. (This assumes, of course, that total_travel_time is in units that will stay below 1000.) Then we'll try to keep this to a minimum.

Control solutions

Instead of making one decision and trying all of the above possible actions on it, I would instead suggest using a pool of k decisions (say k = 10000) stored in a min-heap . This allows you to pull the best solution into the pool in O (log k) and insert new solutions at the same time.

First, you can fill the pool with randomly generated possible solutions; then at each step you will fetch the best solution in the pool, try every possible step to create it to create child solutions, and push any child solutions that are better than their parents back into the pool. Whenever the pool doubles in size, pull out the first (i.e. best) k solutions and make a new mini-heap with them, discarding the old one. (Performing this step after the heap grows to a constant multiple of its original size, as it has the nice property of leaving the time complexity unchanged.)

It may happen that some movement along solution X causes a child solution Y that is already in the pool. This wastes memory, which is unfortunate, but one nice property of the minimum heap method is that you can at least handle these duplicates cheaply when they hit the front of the heap: all duplicates will have the same score, so they all appear sequentially when fetching solutions from the top of the heap. So, to avoid duplicate decisions to create duplicate downstream children, just check that the new top of the heap is different from the solution just checked out and keep fetching and discarding solutions until it's done.

A note on persisting worst- case solutions: It might seem like it is worth supporting child solutions even if they are slightly worse than their parents, and indeed, it can be useful (or even need to find the absolute optimal solution), but it also has an unpleasant consequence: means you can cycle from one solution to your child and back (or possibly a longer cycle). This takes up CPU time on those solutions that we have already visited.