A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem

1997 R. Agarwal, Ö. Ergun, J.B. Orlin, C.N. Potts, Parallel machine scheduling problems with variable depth local search, Working paper, School of Ind. and Sys. Engr., Georgia Institute of Technology, Atlanta, 2003 Ahuja, 2002, A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics, 123, 75, 10.1016/S0166-218X(01)00338-9 E. Balas, New classes of efficiently solvable generalized salesman problems, MSRR No. 615, GSIA, Carnegie Mellon University, Pittsburgh, 1996 Balas, 2001, Linear time dynamic programming algorithms for new classes of Restricted TSPs, INFORMS Journal on Computing, 13, 56, 10.1287/ijoc.13.1.56.9748 A. Bompadre, J.B. Orlin, Using grammars to generate very large scale neighborhoods for the traveling salesman problem and other sequencing problems, in: Proceedings of the 11th International IPCO Conference, Berlin, Germany, 2005, pp. 437–451 R.K. Congram, Polynomially searchable exponential neighborhoods for sequencing problems in combinatorial optimization, Ph.D. Dissertation, Faculty of Mathematical Studies, University of Southampton, UK, 2000 Congram, 2002, An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem, INFORMS Journal on Computing, 14, 52, 10.1287/ijoc.14.1.52.7712 Deĭneko, 2000, A study of exponential neighborhoods for the traveling salesman problem and the quadratic assignment problem, Mathematical Programming, 87, 519, 10.1007/s101070050010 Ö. Ergun, New neighborhood search algorithms based on exponentially large neighborhoods, Ph.D. Dissertation, Operations Research Center, MIT, Cambridge, 2001 Ö. Ergun, J.B. Orlin, A. Steele-Feldman, Creating very large scale neighborhoods out of smaller ones by compounding moves, Journal of Heuristics (2002) (in press) Gutin, 2002, Exponential neighborhoods and domination analysis for the TSP Held, 1962, A dynamic programming approach to sequencing problems, Journal of SIAM, 10, 196 C.N. Potts, S.L. van de Velde, Dynasearch—iterative local improvement by dynamic programming: part I, The traveling salesman problem, Faculty of Mathematical Studies, University of Southampton, UK, 1995 (preprint)