D-ants: Savings based ants divide and conquer the vehicle routing problem

Marc Reimann*, Karl Doerner, Richard F. Hartl

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

296 Citations (Scopus)

Abstract

This paper presents an algorithm that builds on the Savings based Ant System presented in [Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), Morgan Kaufmann, San Francisco, 2002] and enhances its performance in terms of computational effort. This is achieved by decomposing the problem and solving only the much smaller subproblems resulting from the decomposition. The computational study and statistical analysis conducted both on standard benchmark problem instances as well as on new large scale Vehicle Routing Problem instances will show that the approach does not only improve the efficiency, but also improves the effectiveness of the algorithm leading to a fast and powerful problem solving tool for real world sized Vehicle Routing Problems.

Original languageEnglish
Pages (from-to)563-591
Number of pages29
JournalComputers and Operations Research
Volume31
Issue number4
Early online date23 Mar 2003
DOIs
Publication statusPublished - Apr 2004

Fingerprint

Dive into the research topics of 'D-ants: Savings based ants divide and conquer the vehicle routing problem'. Together they form a unique fingerprint.

Cite this