For the sake of simplicity, the heuristic chosen supposes that the cost of the vehicles only depends on one dimension dim. It sequentially builds the routes for the vehicles which have the largest capacity, extending these routes with the cheapest visits after each step of visit addition.
Here is how the algorithm works:
-
Select an open vehicle
w with the largest capacity. If there is none, the algorithm ends.
-
Start a partial route consisting of the first visit of
w. Let vl be the last visit of this partial route.
-
Find a visit
v which minimizes the cost of going from vl to v using vehicle w. If it is not possible to find such a visit without violating constraints, close the current partial route of w and go to step 1.
-
Add
v to the end of the partial route and let vl = v. Go to step 3.
PREVIOUS
NEXT