ESAIM: Control, Optimisation and Calculus of Variations

Table of Contents - October 2009 - Volume 15, Issue 04  

Research Article

Continuous reformulations and heuristics for the Euclidean travelling salesperson problem

Valkonen, Tuomoa1 and Kärkkäinen, Tommia1

a1 Department of Mathematical Information Technology, University of Jyväskylä, Jyväskylä, Finland. tujumava@jyu.fi; tka@mit.jyu.fi

Abstract

We consider continuous reformulations of the Euclidean travelling salesperson problem (TSP), based on certain clustering problem formulations. These reformulations allow us to apply a generalisation with perturbations of the Weiszfeld algorithm in an attempt to find local approximate solutions to the Euclidean TSP.

(Received March 17 2008)

(Online publication August 20 2008)

Key Words:

  • Euclidean TSP;
  • clustering;
  • diff-convex;
  • Weiszfeld algorithm

Mathematics Subject Classification:

  • 90C26;
  • 90C59;
  • 90C27