Coupling ant colony systems with strong local searches
European Journal of Operational ResearchPublished 8 March 2012Open access
Luca Maria Gambardella, Roberto Montemanni, Dennis Weyland
Citations87
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In this paper some directions for improving the original framework when a strong local search routine is available, are identified and some modifications able to speed up the method and make it competitive on large problem instances are described.
Abstract
Ant colony system is a well known metaheuristic framework, and many efficient algorithms for different combinatorial optimization problems have been derived from this general framework. In this paper some directions for improving the original framework when a strong local search routine is available, are identified. In particular, some modifications able to speed up the method and make it competitive on large problem instances, on which the original framework tends to be weaker, are described. The resulting framework, called Enhanced Ant Colony System is tested on three well-known combinatorial optimization problems arising in the transportation field. Many new best known solutions are retrieved for the benchmarks available for these optimization problems.
Keywords
Computer ScienceEngineering
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Ant system: optimization by a colony of cooperating agents
11,908 Citations1996Marco Dorigo, Vittorio Maniezzo +1 more
Artificial LifeAnt Algorithms for Discrete Optimization
2,819 Citations1999Marco Dorigo, Gianni A. Di +1 more
An overview of recent work on ant algorithms, that is, algorithms for discrete optimization that took inspiration from the observation of ant colonies' foraging behavior, and the ant colony optimization (ACO) metaheuristic is presented.
Distributed Optimization by Ant Colonies
2,580 Citations1992Alberto Colorni, Marco Dorigo +3 more
A distributed problem solving environment is introduced and its use to search for a solution to the travelling salesman problem is proposed.
Theoretical Computer ScienceAnt colony optimization theory: A survey
2,287 Citations2005Marco Dorigo, Christian Blum
A survey on theoretical results on ant colony optimization, which highlights some open questions with a certain interest of being solved in the near future and discusses relations between ant colonies optimization algorithms and other approximate methods for optimization.
New Ideas In Optimization
2,135 Citations1999David Corne, Marco Dorigo +5 more
The techniques treated in this text represent research as elucidated by the leaders in the field and are applied to real problems, such as hilllclimbing, simulated annealing, and tabu search.
The Traveling Salesman Problem
1,622 Citations2019Lawrence Snyder, Zuo‐Jun Max Shen
International series in management science/operations research/International series in operations research & management scienceHandbook of Metaheuristics
1,600 Citations2010Michel Gendreau, Jean‐Yves Potvin
The Handbook now includes updated chapters on the best known metaheuristics, including simulated annealing, tabu search, variable neighborhood search, scatter search and path relinking, genetic algorithms, memetic algorithms, genetic programming, ant colony optimization, and multi-start methods.
Transportation ScienceA Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows
930 Citations1997Éric D. Taillard, Philippe Badeau +3 more
A tabu search heuristic for the vehicle routing problem with soft time windows, where lateness at customer locations is allowed although a penalty is incurred and added to the objective value.
European Journal of Operational ResearchThe orienteering problem: A survey
924 Citations2010Pieter Vansteenwegen, Wouter Souffriau +1 more
The OP is formally described and many relevant variants are presented and all published exact solution approaches and (meta) heuristics are discussed and compared.
Lecture notes in economics and mathematical systemsTraveling Salesman Problem
800 Citations1986H. T. Lau
The traveling salesman problem is to start from a node in G, visit every other node exactly once and return back to the starting node in such a way that the total traveled distance is minimum.
Naval Research Logistics (NRL)The orienteering problem
762 Citations1987Bruce Golden, Larry Levy +1 more
MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows
726 Citations1999Luca Maria Gambardella, Éric D. Taillard +1 more
It is shown that MACS-VRPTW is competitive with the best known existing methods both in terms of solution quality and computation time and improves some of the best solutions known for a number of problem instances in the literature.
European Journal of Operational ResearchStochastic vehicle routing
622 Citations1996Michel Gendreau, Gilbert Laporte +1 more
The main problems of stochastic vehicle routing are described within a broad classification scheme and the most important contributions are summarized in table form.
The Traveling Salesman Problem: A Case Study in Local Optimization
601 Citations2008David S. Johnson, Lyle A. McGeoch
This chapter discusses how various approaches to combinatorial optimization have been adapted to the TSP and evaluates their relative success in this perhaps atypical domain from both a theoretical and an experimental point of view.
European Journal of Operational ResearchThe team orienteering problem
556 Citations1996I‐Ming Chao, Bruce Golden +1 more
A fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points and the computational results are presented in detail.
INFORMS Journal on ComputingFast Algorithms for Geometric Traveling Salesman Problems
469 Citations1992Jon Jouis Bentley
Efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets and three local optimizations are described, which are able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours.
INFORMS journal on computingAn Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
371 Citations2000Luca Maria Gambardella, Marco Dorigo
A new local optimizer called SOP-3-exchange is presented for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple constraints directly without increasing computational complexity.
Computers & Operations ResearchIterated local search for the team orienteering problem with time windows
342 Citations2009Pieter Vansteenwegen, Wouter Souffriau +2 more
A simple, fast and effective iterated local search meta-heuristic to solve the TOPTW and an insert step is combined with a shake step to escape from local optima, produces a heuristic that performs very well on a large and diverse set of instances.
European Journal of Operational ResearchA fast and effective heuristic for the orienteering problem
321 Citations1996I‐Ming Chao, Bruce Golden +1 more
A fast and extremely effective heuristic is presented and tested on 67 problems taken from the literature and 40 new test problems and the computational results are presented in detail.
INFORMS journal on computingSolving the Orienteering Problem through Branch-and-Cut
308 Citations1998Matteo Fischetti, Juan‐José Salazar‐González +1 more
A branch-and-cut algorithm for finding an optimal OP solution, based on several families of valid inequalities, is described and proved to be able to solve to optimality large-scale instances involving up to 500 nodes, within acceptable computing time.
Operations ResearchA Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers
279 Citations1996Michel Gendreau, Gilbert Laporte +1 more
A tabu search heuristic is developed for a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands and produces an optimal solution in 89.45% of cases.
Transportation ScienceAn Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers
277 Citations1995Michel Gendreau, Gilbert Laporte +1 more
The stochastic vehicle routing problem, where each customer has a known probability of presence and a random demand, is considered and is solved for the first time to optimality by means of an integer L-shaped method.
Computers & Operations ResearchA TABU search heuristic for the team orienteering problem
268 Citations2003Hao Tang, Elise Miller-Hooks
Results from computational experiments show that the proposed tabu search heuristic consistently produces high-quality solutions and outperforms other published heuristics tbr the TOP.
Computers & Operations ResearchA heuristic for the multiple tour maximum collection problem
223 Citations1994Steven E. Butt, Tom M. Cavalier
A heuristic for the multiple tour maximum collection problem is developed that has the ability to handle large problems in a very short amount of computation time and will always produce a feasible solution if one exists.
GRASP with Path-Relinking: Recent Advances and Applications
220 Citations2005Mauricio G.C. Resendel, Celso C. Ribeiro
Recent advances and applications of GRASP with path-relinking are reviewed, and a discussion of extensions to this strategy, concerning in particular parallel implementations andApplications of path- Relinking with other metaheuristics are discussed.
4ORAn exact algorithm for team orienteering problems
219 Citations2006Sylvain Boussier, Dominique Feillet +1 more
The solution method proposed here is based on a Branch & Price algorithm, and is the first exact method proposed for such problems, except for a preliminary work from Gueguen and a work from Butt and Ryan.
Annals of Operations ResearchCombining simulated annealing with local search heuristics
217 Citations1996Olivier Martin, Steve W. Otto
A meta-heuristic to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space.
Operations research, computer science. Interface seriesMetaheuristics: Progress as Real Problem Solvers
202 Citations2005Toshihide Ibaraki, Koji Nonobe +1 more
This paper presents a metaheuristics approach to GRASP with Path-Relinking that combines a Tabu Search Heuristic for a University Timetabling problem with a multi-Objective Hyper-Heuristic Approaches for Space Allocation andTimetabling.
Computers & Operations ResearchHeuristics for the multi-period orienteering problem with multiple time windows
194 Citations2009Fabien Tricoire, Martin Romauch +2 more
This work presents the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering Problem (OP) and teamorienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application.
Computers & Industrial EngineeringAnts can solve the team orienteering problem
181 Citations2007Liangjun Ke, Claudia Archetti +1 more
An ant colony optimization (ACO) approach is proposed for the team orienteering problem and four methods are proposed to construct candidate solutions in the framework of ACO, i.e., the sequential, deterministic-concurrent and random-constable and simultaneous methods.
NetworksA branch-and-cut algorithm for the undirected selective traveling salesman problem
162 Citations1998Michel Gendreau, Gilbert Laporte +1 more
Several classes of valid inequalities for the symmetric STSP are developed and used in a branch-and-cut algorithm that can solve instances involving up to 300 vertices.
Computers & Operations ResearchDecremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming
153 Citations2008Giovanni Righini, Matteo Salani
This work compares different strategies proposed in the literature to guide decremental state space relaxation and proposes a new heuristic technique to initialize the critical vertex set and provides experimental evidence of its effectiveness.
Lecture notes in computer scienceAn Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem
150 Citations2002Leonora Bianchi, Luca Maria Gambardella +1 more
This work addresses the question of whether and in which context an a priori tour found by a TSP heuristic can also be a good solution for the PTSP by testing the relative performance of two ant colony optimization algorithms, Ant Colony System (ACS) and pACS, and a variant of it which aims to minimize thePTSP objective function.
Journal of the Operational Research SocietyThe Orienteering Problem with Time Windows
147 Citations1992Marisa G. Kantor, Moshe B. Rosenwein
Mathematical ProgrammingThe precedence-constrained asymmetric traveling salesman polytope
147 Citations1995Egon Balas, Matteo Fischetti +1 more
This paper studies the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph, and derives several families of valid inequalities.
Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems
140 Citations1996Norbert Ascheuer
International series in management science/operations research/International series in operations research & management scienceScatter Search and Path-Relinking: Fundamentals, Advances, and Applications
129 Citations2010Maurício G. C. Resende, Celso C. Ribeiro +2 more
This work describes the hybridization of path-relinking with genetic algorithms to implement a progressive crossover operator, and describes the mechanics, implementation issues, randomization, and use of pools of high-quality solutions to hybridize path- Relinking with other heuristic methods.
European Journal of Operational ResearchAn inexact algorithm for the sequential ordering problem
129 Citations1988Laureano F. Escudero
The AP-based lower bound on the optimal solution to ATSP is tightened by using some of the procedures given in [1]; a local search for improving the initial FSO is performed; it uses 3- and 4-changed based procedures.
Computers & Operations ResearchAn optimal solution procedure for the multiple tour maximum collection problem using column generation
125 Citations1999Steven E. Butt, David M. Ryan
An optimal solution procedure is presented for the Multiple Tour Maximum Collection Problem based on a set-partitioning formulation and makes efficient use of both column generation and constraint branching.
Computers & Operations ResearchA Path Relinking approach for the Team Orienteering Problem
121 Citations2009Wouter Souffriau, Pieter Vansteenwegen +2 more
A Path Relinking metaheuristic approach for solving the Team Orienteering Problem (TOP), a particular routing problem in which a score is earned for visiting a location, which improves the best known results in five instances.
European Journal of Operational ResearchAn efficient implementation of local search algorithms for constrained routing problems
107 Citations1990Martin Savelsbergh
This work investigates the implementation of local search algorithms for routing problems with various side constraints such as time windows on vertices and precedence relations between vertices based on the k-exchange concept and shows how this effort can be reduced to a constant.
European Journal of Operational ResearchUsing greedy clustering method to solve capacitated location-routing problem with fuzzy demands
100 Citations2013Yahia Zare Mehrjerdi, Ali Nadizadeh
To solve the capacitated location-routing problem with fuzzy demands (CLRP-FD), a greedy clustering method including the stochastic simulation is proposed and the best value of the dispatcher preference index of the model is obtained.
Naval Research Logistics (NRL)A multifaceted heuristic for the orienteering problem
97 Citations1988Bruce Golden, Qiwen Wang +1 more
A significantly improved procedure for the orienteering problem is described and test, based on four concepts—center of gravity, randomness, subgravity, and learning, which results in more nearly optimal solutions than previous procedures.
Annals of Operations ResearchA Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
79 Citations1994Laureano F. Escudero, Monique Guignard +1 more
This work introduces a formulation for the constrained minimum weight Hamiltonian path problem, and defines Lagrangian relaxation for obtaining strong lower bounds on the makespan, and valid cuts for further tightening of the lower bounds.
European Journal of Operational ResearchStrong linear programming relaxations for the orienteering problem
72 Citations1994Adrienne C. Leifer, Moshe B. Rosenwein
The quality of upper bound obtained is significantly enhanced over the bound obtained from solving the basic LP relaxation, and the procedure to obtain upper bounds by solving three successive linear programs is proposed.
INFORMS Journal on Applied AnalyticsPrecedence Constrained Routing and Helicopter Scheduling: Heuristic Design
72 Citations1992M. T. Fiala Timlin, William R. Pulleyblank
INFORMS journal on computingA Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics
67 Citations2008Stefan Irnich
A new unified modeling and heuristic solution framework for vehicle-routing problems (VRPs) with complex side constraints with strong modeling capabilities as well as efficient solution procedures to be used in all kinds of metaheuristics is presented.
Swarm IntelligenceEstimation-based ant colony optimization and local search for the probabilistic traveling salesman problem
63 Citations2009Prasanna Balaprakash, Mauro Birattari +3 more
This paper proposes an empirical estimation approach to evaluate the cost of the solutions constructed by the ants, and uses a recent estimation-based iterative improvement algorithm as a local search to obtain a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.
SIAM Journal on OptimizationA Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing)
58 Citations1993Norbert Ascheuer, Laureano F. Escudero +2 more
Several 0–1 models of the sequential ordering problem are presented and the authors’ computational experience in finding lower bounds of the optimal solution value of several real-life instances of SOP is reported.
Lecture notes in computer scienceSolving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic
54 Citations2002Leonora Bianchi, Luca Maria Gambardella +1 more
An ant based a priori tour construction heuristic, the probabilistic Ant Colony System (pACS), which is derived from ACS, a similar heuristic previously designed for the TSP problem is proposed and it is shown that for high customers probabilities ACS solutions are better than pACS solutions.
Computers & Operations ResearchAggregation for the probabilistic traveling salesman problem
51 Citations2005Ann Melissa Campbell
This paper addresses questions such as how to best divide customers into regions and what scale is necessary to represent the full objective and presents computational results from experiments with both uniformly distributed and clustered data sets on large problem instances.
Journal of Mathematical Modelling and AlgorithmsSolving the Probabilistic TSP with Ant Colony Optimization
49 Citations2004Jürgen Branke, Michael Guntsch
New ways to apply Ant Colony Optimization (ACO) to the Probabilistic Traveling Salesperson Problem (PTSP) are described, and it is shown that ACO works well even when only an approximative evaluation function is used, which speeds up the algorithm, leaving more time for the actual construction.
INFORMS journal on computingTime-Indexed Formulations and the Total Weighted Tardiness Problem
49 Citations2007Louis-Philippe Bigras, Michel Gamache +1 more
An acceleration strategy based on a decomposition of the time horizon into subperiods, where each subperiod is associated with a subproblem of the column-generation approach, is used to solve the linear relaxation of the total weighted tardiness problem.
Computers & Operations ResearchA hybrid particle swarm optimization approach for the sequential ordering problem
44 Citations2010Davide Anghinolfi, Roberto Montemanni +2 more
A particle swarm optimization approach hybridized with a local search procedure is discussed, shown to be very effective in guiding a sophisticated local search previously introduced in the literature towards high quality regions of the search space.
Computers & Operations ResearchA heuristic manipulation technique for the sequential ordering problem
42 Citations2007Roberto Montemanni, Derek H. Smith +1 more
A problem manipulation technique to be used in conjunction with heuristic algorithms is discussed, which aims to make the search space associated with each problem more attractive for the underlying heuristic algorithm.
Parallel ComputingA cooperative parallel rollout algorithm for the sequential ordering problem
39 Citations2003Francesca Guerriero, Marco Mancini
This paper presents a parallel version of the rollout algorithm, an innovative heuristic method for solving NP-Hard combinatorial optimization problems, recently proposed by Bertsekas et al, by considering a cooperative multi-thread parallelization strategy.
INFORMS journal on computingEstimation-Based Local Search for Stochastic Combinatorial Optimization Using Delta Evaluations: A Case Study on the Probabilistic Traveling Salesman Problem
39 Citations2008Mauro Birattari, Prasanna Balaprakash +2 more
Experimental results on a large set of instances show that the proposed approach can lead to a very fast and highly effective local search algorithm.
Commonality and Genetic Algorithms
39 Citations1996Stephen Chen, Stephen Edward Smith
The comnionality hypothesis introduced in this paper suggests that the prescrvation of cummnn schemata is the centml source of power for commonalilyhared crossovcr operators, and two new crossover opcrators are proposed for sequcncing problcms.
International Journal of Simulation and Process ModellingSequential ordering problems for crane scheduling in port terminals
37 Citations2009Roberto Montemanni, Derek H. Smith +2 more
This paper experimentally evaluates the contributions of the basic ingredients of the state-of-the-art algorithm for the SOPs: Local Searches, ant colony and heuristic manipulation.
Progress in materials handling and logisticsTransportation with Common Carrier and Private Fleets: System Assignment and Shipment Frequency Optimization
33 Citations1991Randolph W. Hall, Michael Racer
IIE TransactionsTransportation with common carrier and private fleets: system assignment and shipment frequency optimization
29 Citations1995Randolph W. Hall, Michael Racer
European Journal of Operational ResearchAdaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem
27 Citations2008Prasanna Balaprakash, Mauro Birattari +2 more
Experimental results show that a particular heuristic customization of the two procedures adopted increases significantly the effectiveness of the estimation-based local search.
Operations research proceedingsSolving the Sequential Ordering Problem with Automatically Generated Lower Bounds
27 Citations2004István T. Hernádvölgyi
This work uses novel branch&bound search algorithms with lower bounds obtained from homomorphic abstractions of the original state space from the TSPLIB to derive lower bounds for Sequential Ordering Problem variants of constrained ATSPs.
Ant Colony Systems for Large Sequential Ordering Problems
24 Citations2007Roberto Montemanni, Derek H. Smith +1 more
This paper proposes an extension of a well known ant colony system for the sequential ordering problem, aiming at making the approach more efficient on large problems.
Lecture notes in computer scienceA Hybrid Genetic Algorithm Based on Complete Graph Representation for the Sequential Ordering Problem
23 Citations2003Dong-il Seo, Byung-Ro Moon
This paper uses Voronoi quantized crossover that adopts complete graph representation and showed remarkable improvement in comparison with state-of-the-art genetic algorithms.
Lecture notes in computer scienceTheoretical Properties of Two ACO Approaches for the Traveling Salesman Problem
22 Citations2010Timo Kötzing, Frank Neumann +2 more
This paper investigates ACO algorithms with respect to their runtime behavior for the traveling salesperson (TSP) problem, and presents a new construction graph that has a stronger local property than the given input graph which is often used for constructing solutions.
uO Research (University of Ottawa)Automatically generated lower bounds for search
16 Citations2004István T. Hernádvölgyi
This thesis fills the gap in research by investigating the search performance of lower bounds derived from abstractions and derives high performance pattern databases to search for macro-operators and to solve challenging instances of the well known Sequential Ordering Problem (SOP).
Lecture notes in computer scienceNew Approximation-Based Local Search Algorithms for the Probabilistic Traveling Salesman Problem
14 Citations2009Dennis Weyland, Leonora Bianchi +1 more
New local search algorithms for the Probabilistic Traveling Salesman Problem (PTSP) are presented using sampling and ad-hoc approximation to improve both runtime and solution quality of state-of-the-art local search algorithm for the PTSP.
European Journal of Operational ResearchMinimum directed 1-subtree relaxation for score orienteering problem
10 Citations1998Seiji Kataoka, Takeo Yamada +1 more
This paper proposes the minimum directed 1-subtree problem as a new relaxation to this problem and develops two methods to improve its lower bound and describes a cut and dual simplex method and a Lagrangian relaxation method.