کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10347299 | 699181 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Determination of the candidate arc set for the asymmetric traveling salesman problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Determination of the candidate arc set for the asymmetric traveling salesman problem Determination of the candidate arc set for the asymmetric traveling salesman problem](/preview/png/10347299.png)
چکیده انگلیسی
As size of the traveling salesman problem (TSP) increases, it is unreasonable to find efficiently an optimum or near-optimum. Instead of considering all arcs, if we select and consider only some arcs more likely to be included in an optimal solution, we can find efficiently an optimum or near-optimum. A candidate arc set is a group of some good arcs. For the lack of study in the asymmetric TSP, it needs to research systematically for the candidate arc set of the asymmetric TSP. In this paper, we suggest a regression function determining a candidate arc set for the asymmetric TSP. We established the regression function based on 2100 experiments, and we proved the goodness of fit for it through various 787 problems. Also, we applied it to the Out-of-Kilter heuristic. We tested it on 220 random instances and 23 real-world instances. Because the complexity of the heuristic depends on the number of arcs and we considered only the candidate arc set, we found good solutions about 2-5 fold faster than considering all arcs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 32, Issue 5, May 2005, Pages 1045-1057
Journal: Computers & Operations Research - Volume 32, Issue 5, May 2005, Pages 1045-1057
نویسندگان
Sang-Ho Kwon, Hun-Tae Kim, Maing-Kyu Kang,