| dc.creator |
Ergun, Özlem |
|
| dc.creator |
Orlin, James |
|
| dc.date |
2004-12-10T19:13:45Z |
|
| dc.date |
2004-12-10T19:13:45Z |
|
| dc.date |
2004-12-10T19:13:45Z |
|
| dc.date.accessioned |
2013-10-09T02:39:46Z |
|
| dc.date.available |
2013-10-09T02:39:46Z |
|
| dc.date.issued |
2013-10-09 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/7387 |
|
| dc.identifier.uri |
http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
|
| dc.description |
We provide two different neighborhood construction techniques for creating exponentially large neighborhoods that
are searchable in polynomial time using dynamic programming. We illustrate both of these approaches on very large
scale neighborhood search techniques for the traveling salesman problem. Our approaches are intended both to
unify previously known results as well as to offer schemas for generating additional exponential neighborhoods that
are searchable in polynomial time. The first approach is to define the neighborhood recursively. In this approach,
the dynamic programming recursion is a natural consequence of the recursion that defines the neighborhood. In
particular, we show how to create the pyramidal tour neighborhood, the twisted sequences neighborhood, and
dynasearch neighborhoods using this approach. In the second approach, 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. |
|
| dc.format |
563560 bytes |
|
| dc.format |
application/pdf |
|
| dc.language |
en_US |
|
| dc.relation |
MIT Sloan School of Management Working Paper;4463-03 |
|
| dc.subject |
dynamic programming |
|
| dc.subject |
neighborhood construction techniques |
|
| dc.title |
Dynamic Programming Methodologies in Very Large Scale Neighborhood Search Applied to the Traveling Salesman Problem |
|
| dc.type |
Working Paper |
|