An Enhanced Ant Colony System for the Team Orienteering Problem with Time Windows

Published 1 July 2011Open access

Roberto Montemanni, Dennis Weyland, Luca Maria Gambardella

DOI10.1109/isccs.2011.95

Citations40

TL;DR

The resulting algorithm, called Enhanced Ant Colony System is experimentally shown to be extremely effective on some well-known benchmark instances available in the literature.

Abstract

The Team Orienteering Problem with Time Windows (TOPTW) is a combinatorial optimization problem arising both in industrial scheduling and in transportation. Ant Colony System (ACS) is a well-known metaheuristic framework, and many efficient algorithms for different optimization problems - among them the TOPTW - have been derived from this general framework. In this paper some directions for improving an ACS algorithm for the TOPTW recently appeared in the literature are identified. The resulting algorithm, called Enhanced Ant Colony System is experimentally shown to be extremely effective on some well-known benchmark instances available in the literature.

Keywords

Engineering

Operations ResearchAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints

4,181 Citations1987Marius M. Solomon

This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.

NetworksA tabu search heuristic for periodic and multi-depot vehicle routing problems

828 Citations1997Jean-Fran�ois Cordeau, Michel Gendreau +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 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.

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.

View PDF

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.

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.