کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4958869 | 1445458 | 2018 | 33 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A hybrid dynamic programming and memetic algorithm to the Traveling Salesman Problem with Hotel Selection
ترجمه فارسی عنوان
برنامه ریزی پویای هیبرید و الگوریتم مامیتی به مشکل فروشندگان مسافر با انتخاب هتل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه نویسی دینامیک، مشکل فروشندگان مسافرتی، جستجوی محلی نامناسب،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
The Traveling Salesman Problem with Hotel Selection (TSPHS) is a variant of the classic Traveling Salesman Problem. It arises from a number of real-life applications where the maximum travel time for each “day trip” is limited. In this paper, we present a highly effective hybrid between dynamic programming and memetic algorithm for TSPHS. The main features of the proposed method include a dynamic programming approach to find an optimal hotel sequence for a given tour, three dedicated crossover operators for solution recombination, an adaptive rule for crossover selection, and a two-phase local refinement procedure that alternates between feasible and infeasible searches. Experiments on four sets of 131 benchmark instances from the literature show a remarkable performance of the proposed approach. In particular, it finds improved best solutions for 22 instances and matches the best known results for 103 instances. Additional analyses highlight the contribution of the dynamic programming approach, the joint use of crossovers and the two local search phases to the performance of the proposed algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 90, February 2018, Pages 193-207
Journal: Computers & Operations Research - Volume 90, February 2018, Pages 193-207
نویسندگان
Yongliang Lu, Una Benlic, Qinghua Wu,