Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach
المؤلفون المشاركون
Chen, Zhenyu
Xiang, Zuoyong
Gao, Xingyu
Wang, Xinjun
Di, Fangchun
Li, Lixin
Liu, Guangyi
Zhang, Yi
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2015، العدد 2015 (31 ديسمبر/كانون الأول 2015)، ص ص. 1-8، 8ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2015-11-09
دولة النشر
مصر
عدد الصفحات
8
التخصصات الرئيسية
الملخص EN
A new partitioning method, called Wedging Insertion, is proposed for solving large-scale symmetric Traveling Salesman Problem (TSP).
The idea of our proposed algorithm is to cut a TSP tour into four segments by nodes’ coordinate (not by rectangle, such as Strip, FRP, and Karp).
Each node is located in one of their segments, which excludes four particular nodes, and each segment does not twist with other segments.
After the partitioning process, this algorithm utilizes traditional construction method, that is, the insertion method, for each segment to improve the quality of tour, and then connects the starting node and the ending node of each segment to obtain the complete tour.
In order to test the performance of our proposed algorithm, we conduct the experiments on various TSPLIB instances.
The experimental results show that our proposed algorithm in this paper is more efficient for solving large-scale TSPs.
Specifically, our approach is able to obviously reduce the time complexity for running the algorithm; meanwhile, it will lose only about 10% of the algorithm’s performance.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Xiang, Zuoyong& Chen, Zhenyu& Gao, Xingyu& Wang, Xinjun& Di, Fangchun& Li, Lixin…[et al.]. 2015. Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach. Mathematical Problems in Engineering،Vol. 2015, no. 2015, pp.1-8.
https://search.emarefa.net/detail/BIM-1074900
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Xiang, Zuoyong…[et al.]. Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach. Mathematical Problems in Engineering No. 2015 (2015), pp.1-8.
https://search.emarefa.net/detail/BIM-1074900
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Xiang, Zuoyong& Chen, Zhenyu& Gao, Xingyu& Wang, Xinjun& Di, Fangchun& Li, Lixin…[et al.]. Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach. Mathematical Problems in Engineering. 2015. Vol. 2015, no. 2015, pp.1-8.
https://search.emarefa.net/detail/BIM-1074900
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1074900
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر