A branch-and-cut algorithm for the Undirected Rural Postman Problem |
| |
| Authors: | Gianpaolo Ghiani Gilbert Laporte |
| |
| Institution: | GERAD, école des Hautes études Commerciales, 3000 chemin de la C?te-Sainte-Catherine, Montréal, Canada H3T 2A7, e-mail: {ghiani,gilbert}@crt.umontreal.ca, CA
|
| |
| Abstract: | The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is
presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results
indicate that the algorithm is capable of solving much larger instances than previously reported.
Received: December 1, 1997 / Accepted: October 13, 1999?Published online January 27, 2000 |
| |
| Keywords: | : Arc Routing Problems – Undirected Rural Postman Problem – branch-and-cut – polyhedral analysis – facets |
| 本文献已被 SpringerLink 等数据库收录！ |
|
