کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1133619 | 1489083 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem
ترجمه فارسی عنوان
ترکیب الگوریتم بهینه یابی کلونی مورچه و تکنیک برنامهنویسی پویا برای حل مسئله فروشنده پوششی
همین الان دانلود کنید
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسئله فروشنده دوره گرد - پوشش مسئله فروشنده دوره گرد - بهینه سازی کلونی مورچه - برنامه نویسی پویا - بحی اکتشافی
فهرست مطالب مقاله
چکیده
کلید واژه ها
1. مقدمه
2. بیان مسئله
3. روش حل
الگوریتم1- چارچوب کلی الگوریتم ACO پیوندی پیشنهادی.
3-1- قالببندی فرومن
3-2- تولید مورچهها و بهروزرسانی فرومن محلی
3-3- فرآیند اصلاح
3-3-1- اضافه کردن رأس
3-3-2- حذف رأس
3-3-3- انتخاب اکتشافی سهتایی
3-3-4- برنامهنویسی پویای اکتشافی
الگوریتم2- چارچوب کلی فرآیند اصلاح.
3-4- بهروزرسانی فرومن جهانی
4. نتایج محاسباتی
شکل 1- مثال نمایشی از فرآیند DP اکتشافی.
جدول 1- مقادیر انتخابی برای پارامترهایACO
جدول 2- مقایسه الگوریتمهای مختلف برای نمونههای با اندازه کوچک.
جدول 3- مقایسه الگوریتمهای مختلف برای نمونههای بااندازه متوسط.
جدول 4- مقایسه الگوریتمهای مختلف برای نمونههای بااندازه بزرگ.
5. نتیجهگیری
کلید واژه ها
1. مقدمه
2. بیان مسئله
3. روش حل
الگوریتم1- چارچوب کلی الگوریتم ACO پیوندی پیشنهادی.
3-1- قالببندی فرومن
3-2- تولید مورچهها و بهروزرسانی فرومن محلی
3-3- فرآیند اصلاح
3-3-1- اضافه کردن رأس
3-3-2- حذف رأس
3-3-3- انتخاب اکتشافی سهتایی
3-3-4- برنامهنویسی پویای اکتشافی
الگوریتم2- چارچوب کلی فرآیند اصلاح.
3-4- بهروزرسانی فرومن جهانی
4. نتایج محاسباتی
شکل 1- مثال نمایشی از فرآیند DP اکتشافی.
جدول 1- مقادیر انتخابی برای پارامترهایACO
جدول 2- مقایسه الگوریتمهای مختلف برای نمونههای با اندازه کوچک.
جدول 3- مقایسه الگوریتمهای مختلف برای نمونههای بااندازه متوسط.
جدول 4- مقایسه الگوریتمهای مختلف برای نمونههای بااندازه بزرگ.
5. نتیجهگیری
ترجمه چکیده
مسئله فروشنده پوششی (CSP) تعمیمی از مسئله معروف فروشنده دورهگرد است که در آن میتوانیمبعضی از رئوس را بدون بازدید رها کنیم. هدف CSP ساخت چرخه همیلتونی با حداقل طول روی زیرمجموعهای از رئوس است درجایی که آن رئوسی که بهوسیله تور بازدید نشدهاند نیاز است تا در داخل یک اندازه از پیش تعیینشده از حداقل یک رأس بازدید شده قرار داشته باشند. در این مقاله، فرمولی ریاضی و الگوریتمی اکتشافی پیوندی بهوسیله ترکیب الگوریتم بهینه یابی کلونی مورچه و تکنیک برنامهنویسی پویا برای به دست آوردن پاسخهای باکیفیت بالا پیشنهاد میکنیم. مقایسه نتایج الگوریتم پیشنهادی با روشهای موجود در متون مختلف بهوضوح کارایی الگوریتم اکتشافی پیشنهادشده ما را نشان میدهد.
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مهندسی صنعتی و تولید
چکیده انگلیسی
The covering salesman problem (CSP) is an extension of the well-known traveling salesman problem in which we are allowed to leave some vertices unvisited. The goal of the CSP is to construct a minimum length Hamiltonian cycle over a subset of vertices where those vertices not visited by the tour need to be within a pre-determined distance from at least one visited vertex. In this paper, we propose a mathematical formulation and a hybrid heuristic algorithm by combining ant colony optimization algorithm and dynamic programming technique to obtain high quality solutions. Comparing the results of the proposed algorithm with available methods in the literature clearly indicates the effectiveness of our proposed heuristic algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 83, May 2015, Pages 244–251
Journal: Computers & Industrial Engineering - Volume 83, May 2015, Pages 244–251
نویسندگان
Majid Salari, Mohammad Reihaneh, Mohammad S. Sabbagh,