×

Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs. (English) Zbl 1391.90622

Summary: The aim of this paper is to computationally compare several algorithms for the minimum cost perfect matching problem on an undirected complete graph. Our work is motivated by the need to solve large instances of the capacitated arc routing problem (CARP) arising in the optimization of garbage collection in Denmark. Common heuristics for the CARP involve the optimal matching of the odd-degree nodes of a graph. The algorithms used in the comparison include the CPLEX solution of an exact formulation, the LEDA matching algorithm, a recent implementation of the Blossom algorithm, as well as six constructive heuristics. Our results show that two of the constructive heuristics consistently exhibit the best behavior compared with the other four.

MSC:

90C35 Programming involving graphs or networks
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Algorithmic, Solutions Software GmbH, 2017. http://www.algorithmic-solutions.com. Accessed 9 June 2017.
[2] Beardwood, J.; Halton, J. H.; Hammersley, J. M., The shortest path through many points, Proc. Camb. Philos. Soc., 55, 299-327, (1959) · Zbl 0118.35601
[3] Cook, W.; Rohe, A., Computing minimum-weight perfect matchings, INFORMS J. Comput., 11, 138-148, (1999) · Zbl 1040.90539
[4] Edmonds, J., Path, trees, and flowers, Can. J. Math., 17, 449-467, (1965) · Zbl 0132.20903
[5] Frederickson, G. N., Approximation algorithms for some postman problems, J. Assoc. Comput Mach, 26, 538-554, (1979) · Zbl 0405.90076
[6] Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacited arc routing problem, Oper. Res., 48, 129-135, (2000) · Zbl 1106.90384
[7] Kiilerich, L.; Wøhlk, S., New large-scale data instances for CARP and variations of CARP, INFOR: Inf. Syst. Oper. Res, (2017)
[8] Kolmogorov, V., http://pub.ist.ac.at/ vnk/software.html#blossom5.
[9] Kolmogorov, V., Blossom V: a new implementation of a minimum cost perfect matching algorithm, Math. Program. Comput., 1, 43-67, (2009) · Zbl 1171.05429
[10] Papadimitriou, C. H., The probabilistic analysis of matching heuristics, Proceedings of the 15th Annual Allerton Conference on Communication Control and Computing, 368-378, (1977)
[11] Prins, C.; Labadi, N.; Reghioui, M., Tour splitting algorithms for vehicle routing problems, Int. J. Prod. Res., 47, 507-536, (2009) · Zbl 1231.90388
[12] Wattenhofer, M.; Wattenhofer, R., Fast and simple algorithms for weighted perfect matching, Electron. Notes Discrete Math, 17, 285-291, (2004) · Zbl 1125.05318
[13] Wøhlk, S., An approximation algorithm for the capacitated arc routing problem, Open Oper. Res. J., 2, 8-12, (2008) · Zbl 1322.90015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.