An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20091343
Country: United Kingdom
Volume: 59
Issue: 5
Start Page Number: 590
End Page Number: 599
Publication Date: May 2008
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: scheduling, programming: travelling salesman
Abstract:

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory.

Reviews

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