Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 107-113 |
| Number of pages | 7 |
| Journal | Computers and Operations Research |
| Volume | 87 |
| DOIs | |
| Publication status | Published - Nov 2017 |
Funding
The authors thank Serge Bisaillon for his technical support. This project is funded by the Danish Council for Independent Research- Social Sciences. Project ?Transportation issues related to waste management? [grant number 4182?00021] and by the Natural Sciences and Engineering Research Council of Canada [grant number 2015?06189]. This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.
Keywords
- Blossom algorithm
- Capacitated arc routing problem
- Garbage collection
- Perfect matching problem
- Rural postman problem
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research
Fingerprint
Dive into the research topics of 'Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS