Abstract
We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple constraints directly without increasing computational complexity. An algorithm that combines the SOP-3-exchange with an Ant Colony Optimization algorithm is described, and we present experimental evidence that the resulting algorithm is more effective than existing methods for the problem. The best-known results for many of a standard test set of 22 problems are improved using the SOP-3-exchange with our Ant Colony Optimization algorithm or in combination with the MPO/AI algorithm (Chen and Smith 1996).
Keywords
Ant colony optimization algorithmsTravelling salesman problemLocal search (optimization)Mathematical optimizationMetaheuristicComputer scienceParallel metaheuristicSet (abstract data type)Extremal optimizationAnt colonyAlgorithmMathematicsMeta-optimization
Affiliated Institutions
Related Publications
A new version of ant system for subset problems
Early applications of Ant Colony Optimization (ACO) have been mainly concerned with solving ordering problems (e.g., traveling salesman problem). We introduce a new version of A...
Ant colony system: a cooperative learning approach to the traveling salesman problem
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...
MAX-MIN Ant System and local search for the traveling salesman problem
Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution ...
Ant system: optimization by a colony of cooperating agents
An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach...
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP). An approach...
Publication Info
- Year
- 2000
- Type
- article
- Volume
- 12
- Issue
- 3
- Pages
- 237-255
- Citations
- 367
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
367
OpenAlex
Cite This
Luca Maria Gambardella,
Marco Dorigo
(2000).
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem.
INFORMS journal on computing
, 12
(3)
, 237-255.
https://doi.org/10.1287/ijoc.12.3.237.12636
Identifiers
- DOI
- 10.1287/ijoc.12.3.237.12636