As in Chapter 7, Pickup and Delivery Problems, you search for a solution using the two-phase approach of generating a first solution and then improving it. However, in this example the solution process is iterative. Each depot model is improved and then the whole problem is improved. When the next iteration to improve depots begins, a synchronization needs to be performed. During this synchronization, the submodels are updated with the changes made during the improvement stage of the whole problem.
Here is a short description of the proposed heuristic:
-
Find a first solution.
-
Improve the solution at each depot.
-
Synchronize the solution with the full model.
-
Improve the whole routing plan. This phase is one that can cause visits to migrate from one depot to another. In other words, moves can be performed that cause a vehicle from a different depot to perform a visit.
-
Return to Step 2 until no further improvement is possible.
-
Do a final solution synchronization.
PREVIOUS
NEXT