Fine-tuning a parametric Clarke and Wright heuristic by means of EAGH (empirically adjusted greedy heuristics)

Alt?nel and Öncan (2005) (A new enhancement of the Clarke and Wrightsavings heuristic for the capacitated vehicle routing problem) proposed aparametric Clarke and Wright heuristic to solve the capacitated vehicle routingproblem (CVRP). The performance of this parametric heuristic is sensitive tofine-tuning. Antinel and Öncan used an enumerative parameter-settingapproach and improved on the results obtained with the original Clarke andWright heuristic, but their approach requires much more computation time tosolve an instance. Battarra et al (2008) (Tuning a parametricClarke–Wright heuristic through a genetic algorithm) proposed a geneticalgorithm to set the parameter values. They succeeded in reducing the timeneeded to solve an instance, but the quality of the solution was slightly worse.In this paper, we propose to use the EAGH (empirically adjusted greedyheuristics) procedure to set the parameter values. A computational experimentshows the efficiency of EAGH; in an even shorter time, we improve on the bestresults obtained with any parametric Clarke and Wright heuristic method proposedin the literature.