Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Ant Colony System Algorithm To Solve The Vehicle Routing Problem
خوارزمية نظام مستعمرة النمل المحسنة لحل مسألة توجيه المركبة
4398
2 419
0
(
0
)
Authors
وسيم بلال( باحث )
Created by
Shamra Editor
Ask ChatGPT about the research
ندرس في هذا البحث إمكانية المساهمة في حلّ مسألة توجيه المركبة 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 ).
Artificial intelligence review:
Research summary
تتناول هذه الورقة البحثية إمكانية حل مسألة توجيه المركبة (VRP) باستخدام خوارزمية نظام مستعمرة النمل المحسنة (IACS). تعتبر مسألة توجيه المركبة من مسائل الأمثلية الصعبة (NP-hard) التي لا توجد لها خوارزمية تقدم الحل الأمثل بسبب تعقيدها الزمني. تعتمد الخوارزمية المقترحة على تحسين خوارزمية نظام مستعمرة النمل التقليدية من خلال إضافة قاعدة انتقال جديدة، وقاعدة تحديث للفورمون، ونهج بحث محلي متنوع. تم مقارنة النتائج التطبيقية للخوارزمية المقترحة مع نتائج اختبارات قياسية معروفة، وأظهرت النتائج أن الخوارزمية المحسنة تقدم حلولًا أفضل من الخوارزميات الأخرى من حيث الجودة وزمن التنفيذ وعدد الحلول الجيدة. تعتمد أهمية البحث على صعوبة المسألة وتعقيدها الخوارزمي، حيث أن حلها يعتبر مفتاحًا لحل العديد من مسائل الأمثلية في المجال الاقتصادي، وتساهم في تحسين كفاءة وسائل النقل والتوزيع. تهدف الورقة إلى المساهمة في حل مسألة توجيه المركبة باستخدام خوارزمية مستعمرة النمل المحسنة، وتقديم نتائج تجريبية تثبت فعالية الخوارزمية المقترحة مقارنة بخوارزميات أخرى. توصي الورقة بتطبيق الخوارزمية المقترحة على أنواع أخرى من مسائل توجيه المركبة واقتراح طرق وأساليب محسنة أخرى للمساهمة في حل مسائل الأمثلية.
Critical review
دراسة نقدية: تعتبر الورقة البحثية مساهمة قيمة في مجال حل مسائل الأمثلية الصعبة باستخدام خوارزميات مستوحاة من الطبيعة. ومع ذلك، يمكن توجيه بعض الملاحظات النقدية لتحسين العمل المستقبلي. أولاً، على الرغم من أن الخوارزمية المحسنة أظهرت نتائج جيدة، إلا أن الورقة لم تتناول بشكل كافٍ تحليل التعقيد الزمني للخوارزمية المقترحة مقارنة بالخوارزميات الأخرى. ثانياً، يمكن تحسين الورقة من خلال تقديم دراسة مقارنة أكثر تفصيلاً تشمل مجموعة أوسع من الخوارزميات الحديثة. ثالثاً، قد يكون من المفيد تضمين تحليل حساسية لمعرفة تأثير تغيير المعلمات المختلفة على أداء الخوارزمية. أخيراً، يمكن توسيع نطاق البحث ليشمل تطبيقات عملية في مجالات أخرى مثل الخدمات اللوجستية وإدارة سلسلة التوريد.
Questions related to the research
-
ما هي مسألة توجيه المركبة (VRP)؟
مسألة توجيه المركبة هي مسألة أمثلية تهدف إلى إيجاد أقل تكلفة لتوجيه مجموعة من المركبات لخدمة مجموعة من الزبائن مع مراعاة قيود معينة مثل استطاعة المركبات والمسافات بين العقد.
-
ما هي التحسينات التي أدخلت على خوارزمية نظام مستعمرة النمل التقليدية في هذه الورقة؟
تم إدخال قاعدة انتقال جديدة، وقاعدة تحديث للفورمون، ونهج بحث محلي متنوع لتحسين أداء خوارزمية نظام مستعمرة النمل التقليدية.
-
ما هي أهمية حل مسألة توجيه المركبة؟
حل مسألة توجيه المركبة يعتبر مفتاحًا لحل العديد من مسائل الأمثلية في المجال الاقتصادي، ويساهم في تحسين كفاءة وسائل النقل والتوزيع، ويؤثر بشكل كبير على اتخاذ القرارات الإستراتيجية في الشركات.
-
ما هي النتائج التي توصلت إليها الورقة بخصوص أداء الخوارزمية المحسنة؟
أظهرت النتائج أن الخوارزمية المحسنة تقدم حلولًا أفضل من خوارزميات مستعمرات النمل الأخرى وخوارزميات ما وراء الإرشادية الأخرى من حيث الجودة وزمن التنفيذ وعدد الحلول الجيدة.
References used
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
rate research
Read More
In this research, we are studying the possibility of contribution in solving the Vehicle Routing Problem With Time Windows(VRPWTW), that is one of the optimization problems of the NP-hard type. This problem has attracted a lot of attention at the pre
sent time because of its real life applications. However, there is still no algorithm that provides us with the perfect solution to this problem because of the complexity of polynomial time. This means that the time of the solution to the Vehicle VRPWTW is growing steadily with the increase in the number of nodes .All the used algorithms have given solutions that are close to the optimal one . We'll introduce two algorithms , the first is Improved Ant Colony System algorithm (IACS) that is capable of searching multiple search areas simultaneously in the solution space is good in diversification ,and the second Simulated Annealing algorithm (SA) is a local search technique that has been successfully applied to many NP-hard problems. Moreover, we will present the In this research Hybrid algorithm (HA) Hybrid Algorithm provided (IACS-SA) that integrate between improved ant algorithm and Simulated Annealing algorithm . We will known standard tests are given to demonstrate the applicability and efficiency of the presented approach and comparisons with other available results are presented.
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 .
In this research, we are studying the possibility of
contribution in solving the Vehicle Routing Problem With Time
Windows(VRPWTW), that is one of the optimization problems of
the NP-hard type. This problem has attracted a lot of attention now
be
cause of its real life applications. However, there is still no
algorithm that provides us with the perfect solution to this problem
because of the complexity of polynomial time. This means that the
time of the solution to the VRPWTW is growing steadily with the
increase in the number of nodes .All the used algorithms have just
given solutions that are close to the optimal one.
n this research, we are studying the possibility of contribution in solving the Vehicle Routing Problem (VRP), which is one of the optimization problems that, because of its Real Life applications, has attracted a lot of attention at the present tim
e. 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 .
In this research, we will present the Hybrid Algorithm (HA) in two phases .In the first phase the Sweep Algorithm (SW) is applied, and in the second one the Ant Colony Algorithm and the local search 3-opt are applied. we will then compare the quality of the solution resulted from this hybrid approach with the results of well-known standard tests to determine the effectiveness of the presented approach .
In this research, we are studying the possibility of contribution
in solving the multi-objective vehicle Routing problem with time
windows , that is one of the optimization problems of the NP-hard
type , This problem has attracted a lot of attenti
on now because of
its real life applications.
Moreover, We will also introduced an algorithm called hybrid
algorithm (HA) which depends on integrates between Multiple
objective ant colony optimisation (MOACO) and tabu search (TS)
algorithm based on the Pareto optimization , and compare the
presented approach is the developer with standard tests to
demonstrate the applicability and efficiency.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
