Euclidean Matching Problems and the Metropolis Algorithm

The Euclidean matching problem consist in partitionning a cloud of n points into n/2 pairs such that the sum of the euclidean distances between the endpoints of each couple is minmized, resp. maximized. In this paper the thermodynamically inspired approach of simulated annealing is applied to find good approximations to large scale problems of the above kind. Also the asymptotic behaviour of random euclidean matching problems is studied, in particular computational results on the rate of convergence towards the asymptote are given.


Published in:
Zeitschrift für Operations Research, 30, 3, 85-110
Methods of Operations Research
Year:
1986
Keywords:
Note:
PRO 86.02
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)