A modified ant colony system for solving the travelling salesman problem with time windows

A modified ant colony system for solving the travelling salesman problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20084165
Country: Netherlands
Volume: 46
Issue: 9/10
Start Page Number: 1225
End Page Number: 1235
Publication Date: Nov 2007
Journal: Mathematical and Computer Modelling
Authors: ,
Keywords: heuristics: ant systems
Abstract:

The travelling salesman problem with time windows (TSPTW) involves finding the minimum cost tour in which all cities are visited exactly once within their requested time windows. This problem has a number of important practical applications, including scheduling and routing. The problem is regarded as NP-complete, and hence traditional optimization algorithms are inefficient when applied to solve larger scale TSPTW problems. Consequently, the development of approximation algorithms has received considerable attention in recent years. Ant colony optimization (ACO), inspired by the foraging behaviour of real ants, is one of the most attractive approximation algorithms. Accordingly, this study develops a modified ant algorithm, named ACS-TSPTW, based on the ACO technique to solve the TSPTW. Two local heuristics are embedded in the ACS-TSPTW algorithm to manage the time-window constraints of the problem. The numerical results obtained for a series of benchmark problem instances confirm that the performance of the ACS-TSPTW is comparable to that of ACS-Time, an existing ACO scheme for solving the TSPTW problem.

Reviews

Required fields are marked *. Your email address will not be published.