in distance until no Easy heuristic to additional on small-scale, clustered longer possible comprehend and constraints such problems with a short horizon. communicate as time windows If used, at least use the ‘time Not very scalable gap’ selection measure to prevent too much waiting time in the solutions. Next to that, penalizing the creation of new extended thus favouring sequential construction of routes, helps in route reduction. The SavPlus variant (which allows more types of moves) is suitable for small-scale problems. It provides better solution but is not a pure savings heuristic: has elements of insertion Create one seed Fast, also on Relatively* poor Recommended for overall use. Sequential route, insert bigger problems, results on the Especially good on problems Insertion customers with Only one run distance criterion that are clustered, have a short best combined needed Not the best time horizon and high time score on insertion Best performance heuristic if few window density. Use the cost and regret if only fast settings time windows (regret-type) to depot’ ‘distance until no longer are allowed (2nd are present and window width’ ‘time possible, then experiment) selection measures repeat the process Cost-based Create multiple Better than Outperformed Not recommended in any case Parallel seed routes, insert parallel by CombReg Insertion customers based insertion on and FewAlt on R (sweep-based on combined score clustered problems and RC, seed selection) on insertion cost Needs quite and regret some tuning, Needs multiple runs CombReg Create multiple Most scalable multiple Recommended in problems seed routes, select heuristic because it runs with few time windows (sweep-based seed selection) customer with does not need to Good for long horizons highest evaluate all moves Good for (semi-) randomized regret/urgency, at once At least include the to ‘distance insert at with depot’ selection measure, lowest cost, etc. preferably more regret measures FewAlt Create multiple Does not need Relatively*slow, Only recommended for (sweep-based seed routes, select much tuning especially on minimization of the number of seed selection) customer with bigger problems routes on (semi-) randomized
in distance until no longer possible Easy heuristic to comprehend and communicate additional constraints such as time windows Not very scalable on small-scale, clustered problems with a short horizon. If used, at least use the ‘time gap’ selection measure to prevent too much waiting time in the solutions. Next to that, penalizing the creation of new extended thus favouring sequential construction of routes, helps in route reduction. The SavPlus variant (which allows more types of moves) is suitable for small-scale problems. It provides better solution but is not a pure savings heuristic: has elements of insertion Sequential Insertion Create one seed route, insert customers with best combined score on insertion cost and regret until no longer possible, then repeat the process Fast, also on bigger problems, Only one run needed Best performance if only fast settings are allowed (2nd experiment) Relatively* poor results on the distance criterion Not the best heuristic if few time windows are present Recommended for overall use. Especially good on problems that are clustered, have a short time horizon and high time window density. Use the (regret-type) ‘distance to depot’ and ‘time window width’ selection measures Cost-based Parallel Insertion (sweep-based seed selection) Create multiple seed routes, insert customers based on combined score on insertion cost and regret Better than parallel insertion on clustered problems Outperformed by CombReg and FewAlt on R and RC, Needs quite some tuning, Needs multiple runs Not recommended in any case CombReg (sweep-based seed selection) Create multiple seed routes, select customer with highest regret/urgency, insert at with lowest cost, etc. Most scalable heuristic because it does not need to evaluate all moves at once multiple runs Recommended in problems with few time windows Good for long horizons Good for (semi-) randomized At least include the ‘distance to depot’ selection measure, preferably more regret measures FewAlt (sweep-based seed selection) Create multiple seed routes, select customer with Does not need much tuning Relatively*slow, especially on bigger problems Only recommended for minimization of the number of routes on (semi-) randomized
10966-Kisjes.docx