اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدمقارنة بين خوارزمية التفريع و القطع ، وخوارزمية مستعمرة النمل ، للمساهمة في حل مسألة البائع المتجول
Comparison between branch and cutting algorithm and ant colony algorithm in order to contribute solving the problem of postman Traveling Salesman Problem
3174
7 136
0
(
0
)
تأليف
ثناء موسى( باحث )
تمت اﻹضافة من قبل
Shamra Editor
اسأل ChatGPT حول البحث
في هذا البحث ندرس إمكانية المساهمة في حل مسألة البائع المتجول Traveling Salesman Problem (TSP , التي هي مسألة من النوع NP-hard و لا توجد حتى الآن خوارزمية تقدم لنا الحل الأمثل لهذه المسألة ، فكل الخوارزميات المستخدمة تعطي حمولاً تقريبية .
In this research we are studying the possibility of contributing in solving the problem of the Traveling Salesman Problem, which is a problem of the type NP-hard . And there is still no algorithm provides us with the Optimal solution to this problem . All the algorithms used to give solutions which are close to the optimal one .
المراجع المستخدمة
DANTZIG, G.B., FULKERSON, D.R., JOHNSON, S.M, 1959 Solution of a large scale traveling salesman problem, Operation Research, vol. 2, 1954,pp.393-395
WILLIAM ,C. 2012 . In Pursuit of the Traveling Salesman ,Mathematics at the Limits of Computation , 245 P
APPLEGATE. D.L, R. BIXBY, V. CHVÁTAL, COOK .W.J, ESPINOZA. D , GOYCOOLEA .M, ANDHELSGAUN. K 2009 . Certification of an optimal tsp tour through 85,900 cities. pp ,1-3
قيم البحث
اقرأ أيضاً
ندرس في هذا البحث إمكانية المساهمة في حلّ مسألة توجيه المركبة Vehicle Routing Problem (VRP) باستخدام خوارزمية نظام مستعمرة النمل المحسنة Improved Ant Colony System (IACS) ، وهي واحدة من مشاكل الأمثلية , التي أخذت الكثير من الاهتمام في الوقت الحاضر بس
بب تطبيقاتها ذات الطابع اليومي ، و هي مشكلة تعقيدها الخوارزمي من النوع NP-hard , ولا توجد حتى الآن خوارزمية تقدم لنا الحل الأمثل لهذه المشكلة بسبب تعقيد الزمن متعدد الحدود ، فكل الخوارزميات المستخدمة تعطي حلولاً قريبة من الحل الأمثل .
إن خوارزمية نظام مستعمرة النمل المحسنة المقترحة تعتمد على خوارزمية نظام مستعمرة النمل التي تمتلك قاعدة انتقال جديدة ، وقاعدة تحديث فورمون جديدة ، ونهج بحث محلي متنوع .
تمت مقارنة النتائج التطبيقية للخوارزمية المقترحة مع نتائج اختبارات قياسية معروفة وموثقة , إذ تظهر النتائج بأنّ الخوارزمية المحسنة المقترحة تنتج حلولاً أفضل من خوارزميات مستعمرات النمل الأخرى و خوارزميات ما وراء الإرشادية الأخرى , من حيث الجودة ( زمن التنفيذ وعدد الحلول الجيدة )
يعد إيجاد الحلول الأمثلية لمسألة البائع المتجول أمرًا مطلوباً في كثير من الأبحاث و التطبيقات العملية على اعتبار وجود مجموعة من الأهداف في وقت واحد.
نقدم في هذا البحث خوارزمية هجينة لحل مسألة البائع من خلال دمج خوارزمية مستعمرة النمل مع الخوارزمية الجينية.
ندرس في هذا البحث إمكانية المساهمة في حل مسألة توجيه المركبة مع نوافذ زمنية ، و هي واحدة من مشاكل الأمثلية من النوع NP-hard حيث أخذت كثير من اهتمام الباحثين في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، إذ لا توجد حتى الآن خوارزمية تقدم الحل الأ
مثل لهذه المشكلة بسبب تعقيد زمن كثيرة الحدود و هذا يعني أن زمن الحل لمسألة توجيه المركبة مع نوافذ زمنية ينمو باطراد مع زيادة عدد العقد ، و كل الخوارزميات المستخدمة تعطي حلولاً تقريبية .
سنعرض في بحثنا خوارزمية نظام مستعمرة النمل المحسن القادرة على استكشاف مناطق بحث متنوعة في فضاء الحل ، و خوارزمية محاكاة التعدين ، و هي تقنية بحث محلي يتم تطبيقها بنجاح في العديد من مسائل NP-hard .
نقدم أيضاً خوارزمية تدعى بالهجينة تعتمد على مبدأ الدمج بين خوارزمية نظام النمل المحسن و خوارزمية محاكاة التعدين ، و مقارنة الحل الناتج عن هذا النهج الهجين مع نتائج تجارب قياسية لاختبار فعالية النهج المقدم .
ندرس في هذا البحث إمكانية المساهمة في حل مسألة توجيه المركبة مع نوافذ زمنية متعددة الأهداف ، و هي واحدة من مشاكل الأمثلية من النوع NP-hard,
حيث أخذت كثيرًا من اهتمام الباحثين في الوقت الحاضر بسبب تطبيقاتها المتعددة ذات
الطابع اليومي .
و سنقدم أيضا
ً خوارزمية تدعى بالهجينة تعتمد على مبدأ التكامل بين خوارزمية مستعمرة
النمل متعددة الأهداف و خوارزمية البحث المحظور ، و المستندة على أمثلية باريتو و
مقارنة الحل الناتج عن هذا النهج الهجين المطور و المستند على أمثلية باريتو مع نتائج
تجارب قياسية لاختبار فعالية هذه الخوارزمية المقدمة.
في هذا البحث ندرس إمكانية المساهمة في حلّ مسألة توجيه المركبة Vehicle Routing Problem (VRP)، وهي واحدة من مشاكل الأمثلية التي أخذت الكثير من الاهتمام في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، والتي هي مشكلة من النوع NP-hard . ولا توجد ح
تى الآن خوارزمية تقدم لنا الحلّ الأمثل لهذه المشكلة بسبب تعقيد الزمن متعدد الحدود ، فكل الخوارزميات المستخدمة تعطي حلولاً قريبة من الحلّ الأمثل .
سنعرض في بحثنا الخوارزمية الهجينة ( HA) Hybrid Algorithm على مرحلتين : في المرحلة الأولى يتم تطبيق خوارزمية المسح Sweep Algorithm (SW) ، وفي المرحلة الثانية يتم تطبيق خوارزمية نظام مستعمرة النمل (AC) Ant Colony Algorithm , مع خوارزمية البحث المحلي local search 3-opt ، ثم مقارنة الحلّ الناتج من هذا النهج الهجين مع نتائج تجارب قياسية معروفة لتحديد فعالية النهج المقدم .
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
