مقارنة بين خوارزمية التفريع والقطع ، وخوارزمية مستعمرة النمل ، للمساهمة في حل مسألة ساعي البريد

الملخص

في هذا البحث ندرس إمكانية الإسهام في حل مسألة ساعي البريد ، حيث وجدنا أنّ  لها القيود نفسها والهدف ذاته لمسألة  البائع المتجول Traveling Salesman Problem (TSP)، التي هي مسألة من النوعNP-hard    ولا توجد حتى الآن خوارزمية تقدم لنا الحل الأمثل لهذه المسألة، فكل الخوارزميات المستخدمة  تعطي حلولاً قريبة من الحل الأمثل  .

سنعرض في بحثنا خوارزمية التفريع والقطع المستعملة  في حل هذه المسألة، وكذلك خوارزمية مستعمرة النمل (ACO)Ant Colony Optimization ، التي تعتمد على الفورمون والمعلومات الإرشادية ،ثم مقارنة نوعية الحل الناتج عن هذه الخوارزمية مع الخوارزمية المضبوطة (B&C)  Branch and Cut ، وخوارزمية الجار الأقرب الإرشادية ( Algorithm (NNA  Nearest  Neighbor.

واكدت النتائج النهائية التي تم الحصول عليها من أجل هدف واحد ( أقصر مسافة ) أنَّ كفاءة الخوارزمية المقترحة أفضل من الخوارزميات التقليدية لأنها زادت الأداء وخفضت الكلفة لحل المسألة المدروسة .