Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Heuristic Algorithmsfor The Eu...

Heuristic Algorithmsfor The Euclidean Three-Matching Problem

Gábor Magyar, Mika Johnsson, Olli Nevalainen, Heuristic Algorithmsfor The Euclidean Three-Matching Problem. TUCS Technical Reports 262, Turku Centre for Computer Science, 1999.

Abstract:

We discuss the heuristic solution of the Three-Matching Problem (3MP), which is an NP-complete graph problem arising from automated manufacturing applications. In the 3MP we have to partition a set of n=3l points into l disjoint subsets, each consisting of three points, and to minimize the total cost of the partition. The cost of a point triplet is the length of the two shortest line segments connecting the three points. The problem is related to the 3-dimensional assignment problem, facility location problems and clustering and partitioning problems.

We describe several heuristics for the 3MP by adapting the existing algorithms developed for the related problems. As the performance of these approaches is not satisfactory, we present a number of tailored local search heuristics, which are based on 2-opt improvements. These methods have similarities to the widely studied local search methods of the TSP, although they also include new ideas in controlling the application of the 2-opt operator.

The paper contains an extensive empirical comparison of the presented heuristics and other recently studied solution methods for 3MP. The local search turns out to be very promising. When designing local search methods one should carefully consider the order in which the neighborhood is scanned, how the new solutions are accepted and when the method is restarted. We conclude that the choice of the appropriate solution method depends on the problem size and the amount of time available for problem solving. The issues of natural generalizations of the problem and their solution methods are also discussed.

<p>Contact Gábor Magyar (gabor.magyar@cs.utu.fi) for the complete report.

BibTeX entry:

@TECHREPORT{tMaJoNe99a,
  title = {Heuristic Algorithmsfor The Euclidean Three-Matching Problem},
  author = {Magyar, Gábor and Johnsson, Mika and Nevalainen, Olli},
  number = {262},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {1999},
  keywords = {combinatorial optimization, heuristic algorithms, local search, genetic algorithms, graph problems},
  ISBN = {952-12-0422-2},
}

Edit publication