Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation

Jano I. van Hemert*, Neil B. Urquhart

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

This paper introduces a generator that creates problem instances for the Euclidean symmetric travelling salesman problem. To fit real world problems, we look at maps consisting of clustered nodes. Uniform random sampling methods do not result in maps where the nodes are spread out to form identifiable clusters. To improve upon this, we propose an evolutionary algorithm that uses the layout of nodes on a map as its genotype. By optimising the spread until a set of constraints is satisfied, we are able to produce better clustered maps, in a more robust way. When varying the number of clusters in these maps and, when solving the Euclidean symmetric travelling salesman person using Chained Lin-Kernighan, we observe a phase transition in the form of an easy-hard-easy pattern.
Original languageEnglish
Title of host publicationLecture Notes in Computer Science
EditorsXin Yao, John A. Bullinaria, Jonathan Rowe, Peter Tino, Ata Kaban, Edmund Burke, Jose A. Lozano, Jim Smith, Juan J. Merelo-Guervos, Hans-Paul Schwefel
PublisherSpringer
Pages151-160
Number of pages10
ISBN (Print)9783540230922
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
Volume3242
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation'. Together they form a unique fingerprint.

Cite this