Presentation | 1996/10/28 Neural Network Approch to Travelling Salesman Problem Based on City Adjacency and Its Evaluation Toshio TANAKA, Satoshi MATSUDA, Tatsumi FURUYA, Tetsuya HIGUCHI, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | A stability condition of solutions and an instability condition of nonsolutions are derived for Hop-field network for TSP based on city adjacency. By setting weights to satisfy these conditions, it is actually shown that we can always obtain solutions for many TSP instances. We also make, by simulations, performance comparisons of this network with the network based on city position in tour. For the network based on city position, errors in solutions obtained have a tendency to increase as the problem size increases, but, for one based on city adjacency, does not depend on the problem size. Also we show that, for TSPs with less than 130 cities, the network based on city adjacency takes shorter computation time than the one based on city position, but, for TSPs with more than 130 cities, the contrary is observed. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Hopfield network / Travelling Salesman Problem / city adjacency / subtour |
Paper # | NC96-39 |
Date of Issue |
Conference Information | |
Committee | NC |
---|---|
Conference Date | 1996/10/28(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Neurocomputing (NC) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Neural Network Approch to Travelling Salesman Problem Based on City Adjacency and Its Evaluation |
Sub Title (in English) | |
Keyword(1) | Hopfield network |
Keyword(2) | Travelling Salesman Problem |
Keyword(3) | city adjacency |
Keyword(4) | subtour |
1st Author's Name | Toshio TANAKA |
1st Author's Affiliation | Electrotechnical Laboratory() |
2nd Author's Name | Satoshi MATSUDA |
2nd Author's Affiliation | Tokyo Electric Power Company |
3rd Author's Name | Tatsumi FURUYA |
3rd Author's Affiliation | Toho University |
4th Author's Name | Tetsuya HIGUCHI |
4th Author's Affiliation | Electrotechnical Laboratory |
Date | 1996/10/28 |
Paper # | NC96-39 |
Volume (vol) | vol.96 |
Number (no) | 331 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |