اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدخوارزمية نظام مستعمرة النمل المحسنة لحل مسألة توجيه المركبة
Improved Ant Colony System Algorithm To Solve The Vehicle Routing Problem
4505
2 419
0
(
0
)
تأليف
وسيم بلال( باحث )
تمت اﻹضافة من قبل
Shamra Editor
اسأل ChatGPT حول البحث
ندرس في هذا البحث إمكانية المساهمة في حلّ مسألة توجيه المركبة Vehicle Routing Problem (VRP) باستخدام خوارزمية نظام مستعمرة النمل المحسنة Improved Ant Colony System (IACS) ، وهي واحدة من مشاكل الأمثلية , التي أخذت الكثير من الاهتمام في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، و هي مشكلة تعقيدها الخوارزمي من النوع NP-hard , ولا توجد حتى الآن خوارزمية تقدم لنا الحل الأمثل لهذه المشكلة بسبب تعقيد الزمن متعدد الحدود ، فكل الخوارزميات المستخدمة تعطي حلولاً قريبة من الحل الأمثل . إن خوارزمية نظام مستعمرة النمل المحسنة المقترحة تعتمد على خوارزمية نظام مستعمرة النمل التي تمتلك قاعدة انتقال جديدة ، وقاعدة تحديث فورمون جديدة ، ونهج بحث محلي متنوع . تمت مقارنة النتائج التطبيقية للخوارزمية المقترحة مع نتائج اختبارات قياسية معروفة وموثقة , إذ تظهر النتائج بأنّ الخوارزمية المحسنة المقترحة تنتج حلولاً أفضل من خوارزميات مستعمرات النمل الأخرى و خوارزميات ما وراء الإرشادية الأخرى , من حيث الجودة ( زمن التنفيذ وعدد الحلول الجيدة )
We study in this paper the possibility of contribution in solving the vehicle routing problem (VRP) by using the improved ant colony system ( IACS) , which is one of the optimization problems that, because of its Real Life applications, has attracted a lot of attention at the present time. It is a problem of the NP-hard type. However, because of the complication of polynomial time there is still no algorithm providing us with the optimal solution of this problem. All the used algorithms give solutions that are close to the optimal one . We present the improved ant colony system algorithm that, based on ant colony system algorithm, possesses a new state transition rule, a new pheromone updating rule and diverse local search approaches . The experimental results of the proposed ( IACS) algorithm compared with the results of well-known standard tests show that our IACS yields better solutions than the other ant algorithms in the literature and is competitive with other meta-heuristic approaches in terms of quality(run time and number of good solutions ).
مراجعة الذكاء الصنعي:
ملخص البحث
تتناول هذه الورقة البحثية إمكانية حل مسألة توجيه المركبة (VRP) باستخدام خوارزمية نظام مستعمرة النمل المحسنة (IACS). تعتبر مسألة توجيه المركبة من مسائل الأمثلية الصعبة (NP-hard) التي لا توجد لها خوارزمية تقدم الحل الأمثل بسبب تعقيدها الزمني. تعتمد الخوارزمية المقترحة على تحسين خوارزمية نظام مستعمرة النمل التقليدية من خلال إضافة قاعدة انتقال جديدة، وقاعدة تحديث للفورمون، ونهج بحث محلي متنوع. تم مقارنة النتائج التطبيقية للخوارزمية المقترحة مع نتائج اختبارات قياسية معروفة، وأظهرت النتائج أن الخوارزمية المحسنة تقدم حلولًا أفضل من الخوارزميات الأخرى من حيث الجودة وزمن التنفيذ وعدد الحلول الجيدة. تعتمد أهمية البحث على صعوبة المسألة وتعقيدها الخوارزمي، حيث أن حلها يعتبر مفتاحًا لحل العديد من مسائل الأمثلية في المجال الاقتصادي، وتساهم في تحسين كفاءة وسائل النقل والتوزيع. تهدف الورقة إلى المساهمة في حل مسألة توجيه المركبة باستخدام خوارزمية مستعمرة النمل المحسنة، وتقديم نتائج تجريبية تثبت فعالية الخوارزمية المقترحة مقارنة بخوارزميات أخرى. توصي الورقة بتطبيق الخوارزمية المقترحة على أنواع أخرى من مسائل توجيه المركبة واقتراح طرق وأساليب محسنة أخرى للمساهمة في حل مسائل الأمثلية.
قراءة نقدية
دراسة نقدية: تعتبر الورقة البحثية مساهمة قيمة في مجال حل مسائل الأمثلية الصعبة باستخدام خوارزميات مستوحاة من الطبيعة. ومع ذلك، يمكن توجيه بعض الملاحظات النقدية لتحسين العمل المستقبلي. أولاً، على الرغم من أن الخوارزمية المحسنة أظهرت نتائج جيدة، إلا أن الورقة لم تتناول بشكل كافٍ تحليل التعقيد الزمني للخوارزمية المقترحة مقارنة بالخوارزميات الأخرى. ثانياً، يمكن تحسين الورقة من خلال تقديم دراسة مقارنة أكثر تفصيلاً تشمل مجموعة أوسع من الخوارزميات الحديثة. ثالثاً، قد يكون من المفيد تضمين تحليل حساسية لمعرفة تأثير تغيير المعلمات المختلفة على أداء الخوارزمية. أخيراً، يمكن توسيع نطاق البحث ليشمل تطبيقات عملية في مجالات أخرى مثل الخدمات اللوجستية وإدارة سلسلة التوريد.
أسئلة حول البحث
-
ما هي مسألة توجيه المركبة (VRP)؟
مسألة توجيه المركبة هي مسألة أمثلية تهدف إلى إيجاد أقل تكلفة لتوجيه مجموعة من المركبات لخدمة مجموعة من الزبائن مع مراعاة قيود معينة مثل استطاعة المركبات والمسافات بين العقد.
-
ما هي التحسينات التي أدخلت على خوارزمية نظام مستعمرة النمل التقليدية في هذه الورقة؟
تم إدخال قاعدة انتقال جديدة، وقاعدة تحديث للفورمون، ونهج بحث محلي متنوع لتحسين أداء خوارزمية نظام مستعمرة النمل التقليدية.
-
ما هي أهمية حل مسألة توجيه المركبة؟
حل مسألة توجيه المركبة يعتبر مفتاحًا لحل العديد من مسائل الأمثلية في المجال الاقتصادي، ويساهم في تحسين كفاءة وسائل النقل والتوزيع، ويؤثر بشكل كبير على اتخاذ القرارات الإستراتيجية في الشركات.
-
ما هي النتائج التي توصلت إليها الورقة بخصوص أداء الخوارزمية المحسنة؟
أظهرت النتائج أن الخوارزمية المحسنة تقدم حلولًا أفضل من خوارزميات مستعمرات النمل الأخرى وخوارزميات ما وراء الإرشادية الأخرى من حيث الجودة وزمن التنفيذ وعدد الحلول الجيدة.
المراجع المستخدمة
DANTZIG, G.B.; RAMSER, J. H., “The Truck Dispatching Problem," Management Science, Vol. 6, No. 1, 1959, pp. 79-89
LAPORTE, G., “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, Vol. 59, No. 3, 1992, pp. 345-358
FISHER .M., "Vehicle Routing. , editors. Network routing, Vol. 8, Handbooks of Operations Research and Management Science, Amsterdam: Elsevier, " chap.1, 1995, pp:1-31
GILLETT, B.E.; L.R. MILLER, "A Heuristic Algorithm for the Vehicle Dispatch Problem," Oper Res 22, 1974, pp :341–347
GOLEN, B.L; ASSAD,A.A., "Vehicle Routing: Methods and Studies," eds. North Holland, Amsterdam,1988
قيم البحث
اقرأ أيضاً
ندرس في هذا البحث إمكانية المساهمة في حل مسألة توجيه المركبة مع نوافذ زمنية ، و هي واحدة من مشاكل الأمثلية من النوع NP-hard حيث أخذت كثير من اهتمام الباحثين في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، إذ لا توجد حتى الآن خوارزمية تقدم الحل الأ
مثل لهذه المشكلة بسبب تعقيد زمن كثيرة الحدود و هذا يعني أن زمن الحل لمسألة توجيه المركبة مع نوافذ زمنية ينمو باطراد مع زيادة عدد العقد ، و كل الخوارزميات المستخدمة تعطي حلولاً تقريبية .
سنعرض في بحثنا خوارزمية نظام مستعمرة النمل المحسن القادرة على استكشاف مناطق بحث متنوعة في فضاء الحل ، و خوارزمية محاكاة التعدين ، و هي تقنية بحث محلي يتم تطبيقها بنجاح في العديد من مسائل NP-hard .
نقدم أيضاً خوارزمية تدعى بالهجينة تعتمد على مبدأ الدمج بين خوارزمية نظام النمل المحسن و خوارزمية محاكاة التعدين ، و مقارنة الحل الناتج عن هذا النهج الهجين مع نتائج تجارب قياسية لاختبار فعالية النهج المقدم .
في هذا البحث ندرس إمكانية المساهمة في حل مسألة البائع المتجول Traveling Salesman Problem (TSP , التي هي مسألة من النوع NP-hard و لا توجد حتى الآن خوارزمية تقدم لنا الحل الأمثل لهذه المسألة ، فكل الخوارزميات المستخدمة تعطي حمولاً تقريبية .
ندرس في هذا البحث إمكانية المساهمة في حل مسألة توجيه المركبة مع نوافذ
زمنية ، و ىي واحدة من مشاكل الأمثمية من النوع NP-hard حيث أخذت كثيرا من
اهتمام الباحثين في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، إذ لا توجد
حتى الآن خوارزمية تقدم ال
حل الأمثل لهذه المشكلة بسبب تعقيد زمن كثيرة الحدود و هذا
يعني أن زمن الحل لمسألة توجيه المركبة مع نوافذ زمنية ينمو باطراد مع زيادة عدد العقد
و كل الخوارزميات المستخدمة تعطي حلولاً تقريبية .
في هذا البحث ندرس إمكانية المساهمة في حلّ مسألة توجيه المركبة Vehicle Routing Problem (VRP)، وهي واحدة من مشاكل الأمثلية التي أخذت الكثير من الاهتمام في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، والتي هي مشكلة من النوع NP-hard . ولا توجد ح
تى الآن خوارزمية تقدم لنا الحلّ الأمثل لهذه المشكلة بسبب تعقيد الزمن متعدد الحدود ، فكل الخوارزميات المستخدمة تعطي حلولاً قريبة من الحلّ الأمثل .
سنعرض في بحثنا الخوارزمية الهجينة ( HA) Hybrid Algorithm على مرحلتين : في المرحلة الأولى يتم تطبيق خوارزمية المسح Sweep Algorithm (SW) ، وفي المرحلة الثانية يتم تطبيق خوارزمية نظام مستعمرة النمل (AC) Ant Colony Algorithm , مع خوارزمية البحث المحلي local search 3-opt ، ثم مقارنة الحلّ الناتج من هذا النهج الهجين مع نتائج تجارب قياسية معروفة لتحديد فعالية النهج المقدم .
ندرس في هذا البحث إمكانية المساهمة في حل مسألة توجيه المركبة مع نوافذ زمنية متعددة الأهداف ، و هي واحدة من مشاكل الأمثلية من النوع NP-hard,
حيث أخذت كثيرًا من اهتمام الباحثين في الوقت الحاضر بسبب تطبيقاتها المتعددة ذات
الطابع اليومي .
و سنقدم أيضا
ً خوارزمية تدعى بالهجينة تعتمد على مبدأ التكامل بين خوارزمية مستعمرة
النمل متعددة الأهداف و خوارزمية البحث المحظور ، و المستندة على أمثلية باريتو و
مقارنة الحل الناتج عن هذا النهج الهجين المطور و المستند على أمثلية باريتو مع نتائج
تجارب قياسية لاختبار فعالية هذه الخوارزمية المقدمة.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
