USING EXACT ALGORITHM FOR THE UNDIRECTED URBAN POSTMAN PROBLEM
Keywords:
Arc Routing, Exact Algorithms, Urban Postman Problem, Variable Neighbourhood Search.Abstract
We are aware of four exact algorithms for the undirected UPP. The first, due to Christofides, Campos, Corberan, and Mota (1981) uses branch-and-bound combined with Lagrangean relaxation. Corberan and Sanchis (1994) described an integer linear programming
formulation solved using a branch-and-cut algorithm in which the separation problems are solved visually. Letchford (1996) added so-called path-bridge and Laporte (2000) introduced a new and more compact formulation which, when solved by branch-and-cut, yields excellent results on test problems. In what follows, we summarize some of the Ghiani and Laporte results.
References
Anily, S., Gendreau, M. and Laporte, G. Optimal sequencing of tasks on a tree shaped structure. Ricerca Operativa 2000; 29:3-14.
Assad, A.A. and Golden, B.L. “Arc routing methods and applications”. In M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser, Network Routing, Handbooks in Operation Research and Management Sciences, Amsterdam: North-Holland, 1995.
Amine, K. & Djellab, R. 2013. Industrial and Urban Applications of Eulerian and Chinese Walks, In Graph Theory for Operations Research and Management: Applications in Industrial Engineering, IGI-Global, Hershey, 271-279
