Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem

References

• Assad A. A., Golden B. L., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Arc routing methods and applications. Network Routing. Handbooks in Operations Research and Management Science (1995) (North-Holland, Amsterdam, The Netherlands) 375–483Google Scholar
• Benavent E., Corberàn A., Sanchis J. M., Dror M. Linear programming based methods for solving arc routing problems. Arc Routing: Theory, Solutions and Applications (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 231–275Crossref, Google Scholar
• Bentley J. L. Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. (1992) 4:387–411Link, Google Scholar
• Beullens P., Muyldermans L., Cattrysse D., Van Oudheusden D. A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. (2003) 147:629–643Crossref, Google Scholar
• Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. (1976) . Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Christofides N., Campos V., Corberán A., Mota E. An algorithm for the rural postman problem. (1981) . Report I.C.O.R. 81.5, Imperial College, London, UKGoogle Scholar
• Corberán A., Sanchis J. M. A polyhedral approach to the rural postman problem. Eur. J. Oper. Res. (1994) 79:95–114Crossref, Google Scholar
• Corberán A., Letchford A. N., Sanchis J. M. A cutting plane algorithm for the general routing problem. Math. Programming Series A (2001) 90:291–316Crossref, Google Scholar
• Cornuéjols G., Fonlupt J., Naddef D. The traveling salesman problem on a graph and some related integer polyhedra. Math. Programming (1985) 33:1–27Crossref, Google Scholar
• Croes G. A. A method for solving traveling salesman problems. Oper. Res. (1958) 6:791–812Link, Google Scholar
• Dror M.Arc Routing: Theory, Solutions and Applications (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) Crossref, Google Scholar
• Edmonds J. The Chinese postman problem. Oper. Res. (1963) 13(Supplement 1):B73–B77Google Scholar
• Edmonds J., Johnson E. J. Matching, Euler tours and the Chinese postman problem. Math. Programming (1973) 5:88–124Crossref, Google Scholar
• Eiselt H. A., Gendreau M., Laporte G. Arc routing problems, Part II: The rural postman problem. Oper. Res. (1995) 43:399–414Link, Google Scholar
• Fleischmann B. A cutting plane procedure for the traveling salesman problem on a road network. Eur. J. Oper. Res. (1985) 21:307–317Crossref, Google Scholar
• Frederickson G. N. Approximation algorithms for some postman problems. J. Assoc. Comput. Machinery (1979) 26:538–554Crossref, Google Scholar
• Ghiani G., Laporte G. A branch and cut algorithm for the undirected rural postman problem. Math. Programming Series A (2000) 87:467–481Crossref, Google Scholar
• Gomory R. E., Hu T. C. Multi-terminal network flows. SIAM J. Appl. Math. (1961) 9:551–570Crossref, Google Scholar
• Guan M. Graphic programming using odd or even points. Chinese Math. (1962) 1:237–277Google Scholar
• Hertz A., Laporte G., Nanchen Hugo P. Improvement procedures for the undirected rural postman problem. INFORMS J. Comput. (1999) 11:53–62Link, Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E., Lenstra J. K. The traveling salesman problem: A case study. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, UK) 215–310Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. The traveling salesman problem. Network Models. Handbooks in Operations Research and Management Science (1995) (North-Holland, Amsterdam, The Netherlands) 225–330Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B.The Traveling Salesman Problem (1985) (John Wiley and Sons, Chichester, UK) Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G. On general routing problems. Networks (1976) 6:273–280Crossref, Google Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell System Tech. J. (1965) 44:2245–2269Crossref, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Muyldermans L. Routing, districting and location for arc traversal problems. (2003) . Ph.D. dissertation, Center for Industrial Management, Katholieke Universiteit Leuven, Heverlee, BelgiumCrossref, Google Scholar
• Orloff C. S. A fundamental problem in vehicle routing. Networks (1974) 4:35–64Crossref, Google Scholar
• Padberg M. W., Rao M. R. Odd minimum cut-sets and b-matchings. Math. Oper. Res. (1982) 7:67–80Link, Google Scholar
• Voudouris C., Tsang E. Partial constraint satisfaction problems and guided local search. Proc. Second Internat. Conf. on Practical Application of Constraint Technology (PACT ’96) (1996) London, UK:337–356Google Scholar
• Voudouris C., Tsang E. Guided local search and its application to the traveling salesman problem. Eur. J. Oper. Res. (1999) 113:469–499Crossref, Google Scholar