Tuning a Parametric Clarke-Wright Heuristic for the Vehicle Routing Through a Genetic Algorithm

Maria Battarra, Bruce Golden, Daniele Vigo

Research output: Contribution to journalArticle

21 Citations (Scopus)

Abstract

Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.
LanguageEnglish
Pages1568-1572
JournalJournal of the Operational Research Society
Volume59
Issue number11
Early online date29 Aug 2007
DOIs
StatusPublished - 2008

Fingerprint

Vehicle routing
Set theory
Tuning
Genetic algorithms
Testing
Genetic algorithm
Heuristics

Cite this

Tuning a Parametric Clarke-Wright Heuristic for the Vehicle Routing Through a Genetic Algorithm. / Battarra, Maria; Golden, Bruce; Vigo, Daniele.

In: Journal of the Operational Research Society, Vol. 59, No. 11, 2008, p. 1568-1572.

Research output: Contribution to journalArticle

@article{0780366637bb43568769d3a965592f56,
title = "Tuning a Parametric Clarke-Wright Heuristic for the Vehicle Routing Through a Genetic Algorithm",
abstract = "Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.",
author = "Maria Battarra and Bruce Golden and Daniele Vigo",
year = "2008",
doi = "10.1057/palgrave.jors.2602488",
language = "English",
volume = "59",
pages = "1568--1572",
journal = "Journal of the Operational Research Society",
issn = "0160-5682",
publisher = "Palgrave Macmillan",
number = "11",

}

TY - JOUR

T1 - Tuning a Parametric Clarke-Wright Heuristic for the Vehicle Routing Through a Genetic Algorithm

AU - Battarra, Maria

AU - Golden, Bruce

AU - Vigo, Daniele

PY - 2008

Y1 - 2008

N2 - Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.

AB - Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.

U2 - 10.1057/palgrave.jors.2602488

DO - 10.1057/palgrave.jors.2602488

M3 - Article

VL - 59

SP - 1568

EP - 1572

JO - Journal of the Operational Research Society

T2 - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 11

ER -