| Presentation | 2009-05-15 A Solution-Space Reduction Method for Traveling Salesman Problem Using Geographical Threshold Graph with Neighbor Information Yusuke KAWAMURA, Takafumi MATSUURA, Tohru IKEGUCHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Traveling Salesman Problem (TSP) is one of the most typical combinatorial optimization problems which belong to a class of NP-hard. Each edge in an optimal tour tends to connect two cities locally. Thus, to reduce the solution-space of the TSP, the nearest neighbor method is used for constructing a short tour. On the other hand, to analyze the characteristics of real networks, many geographical complex network models are proposed recently. These networks have similar properties with optimal tours of the TSP: long-range edges are restricted and intersection of edges occurs rarely. In this report, we proposed a reduction method for the solution-space of the TSP using geographical threshold graph with near neighbor information. As a result, the proposed method can include all edges in the optimal tour with less edges than the conventional methods. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Traveling Salesman Problem (TSP) / Solution-Space / Complex Network / Geographical Threshold Graph |
| Paper # | NLP2009-12 |
| Date of Issue |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2009/5/8(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 | Nonlinear Problems (NLP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Solution-Space Reduction Method for Traveling Salesman Problem Using Geographical Threshold Graph with Neighbor Information |
| Sub Title (in English) | |
| Keyword(1) | Traveling Salesman Problem (TSP) |
| Keyword(2) | Solution-Space |
| Keyword(3) | Complex Network |
| Keyword(4) | Geographical Threshold Graph |
| 1st Author's Name | Yusuke KAWAMURA |
| 1st Author's Affiliation | Graduate School of Science and Engineering, Saitama University() |
| 2nd Author's Name | Takafumi MATSUURA |
| 2nd Author's Affiliation | Graduate School of Science and Engineering, Saitama University |
| 3rd Author's Name | Tohru IKEGUCHI |
| 3rd Author's Affiliation | Graduate School of Science and Engineering, Saitama University |
| Date | 2009-05-15 |
| Paper # | NLP2009-12 |
| Volume (vol) | vol.109 |
| Number (no) | 30 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |