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

被引：26

作者：

Ergun, Ozlem ^{[1
]}

Orlin, James B.

机构：

[1] Georgia Inst Technol, Atlanta, GA 30339 USA

[2] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA

来源：

DISCRETE OPTIMIZATION | 2006年 / 3卷 / 01期

基金：

美国国家科学基金会;

关键词：

traveling salesman problem; very large-scale neighborhood search; dynamic programming;

D O I：

10.1016/j.disopt.2005.10.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the standard dynamic program to solve the TSP. We then obtain exponentially large neighborhoods by selecting a polynomially bounded number of states, and restricting the dynamic program to those states only. We show how the Balas and Simonetti neighborhood and the insertion dynasearch neighborhood can be viewed in this manner. We also show that one of the dynasearch neighborhoods can be derived directly from the 2-exchange neighborhood using this approach. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：78 / 85

页数：8

共 14 条

[1]

AARTS E, 1997, LOCAL SEARCH COMBINA

[2]

AGARWAL R, 2003, PARALLEL MACHINE SCH

[3] A survey of very large-scale neighborhood search techniques [J].