A comparison study of optimization methods for the bipartite matching problem (BMP)

A comparison study of optimization methods for the bipartite matching problem (BMP) with independent random distances between the points is presented. It is shown that the results obtained are in reasonable agreement with the theoretical prediction despite the relatively small samples considered. In the first four intervals, which include more than 80% of the valid solutions considered, the theoretical results are within one standard deviation of the results obtained by all methodologies. The average computation times per valid solution obtained using VSA (variant of simulated annealing) is superior to the average time of other methodologies. Another interesting result is the fact that the MSA (microcanonical simulated annealing) average time is as much as four times smaller than the FSA (fast simulated annealing) average time.<>