Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUse of hybrid methods to contribute in solving the Vehicle Routing Problem
استخدام الطرق الهجينة للمساهمة في حل مسألة توجيه المركبة
2683
1 122
0
(
0
)
Authors
وسيم بلال( باحث )
Created by
Shamra Editor
Ask ChatGPT about the research
في هذا البحث ندرس إمكانية المساهمة في حلّ مسألة توجيه المركبة Vehicle Routing Problem (VRP)، وهي واحدة من مشاكل الأمثلية التي أخذت الكثير من الاهتمام في الوقت الحاضر بسبب تطبيقاتها ذات الطابع اليومي ، والتي هي مشكلة من النوع NP-hard . ولا توجد حتى الآن خوارزمية تقدم لنا الحلّ الأمثل لهذه المشكلة بسبب تعقيد الزمن متعدد الحدود ، فكل الخوارزميات المستخدمة تعطي حلولاً قريبة من الحلّ الأمثل . سنعرض في بحثنا الخوارزمية الهجينة ( HA) Hybrid Algorithm على مرحلتين : في المرحلة الأولى يتم تطبيق خوارزمية المسح Sweep Algorithm (SW) ، وفي المرحلة الثانية يتم تطبيق خوارزمية نظام مستعمرة النمل (AC) Ant Colony Algorithm , مع خوارزمية البحث المحلي local search 3-opt ، ثم مقارنة الحلّ الناتج من هذا النهج الهجين مع نتائج تجارب قياسية معروفة لتحديد فعالية النهج المقدم .
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 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 . 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 .
Artificial intelligence review:
Research summary
تناقش هذه الورقة البحثية مسألة توجيه المركبة (VRP)، وهي مشكلة أمثلية من النوع NP-hard، حيث لا توجد خوارزمية تقدم الحل الأمثل بسبب تعقيد الزمن متعدد الحدود. تقدم الورقة خوارزمية هجينة تتكون من مرحلتين: في المرحلة الأولى يتم تطبيق خوارزمية المسح (SW)، وفي المرحلة الثانية يتم تطبيق خوارزمية مستعمرة النمل (ACO) مع خوارزمية البحث المحلي 3-opt. تهدف الورقة إلى مقارنة الحل الناتج من هذا النهج الهجين مع نتائج تجارب قياسية لتحديد فعالية النهج المقدم. أظهرت النتائج التجريبية أن الخوارزمية الهجينة المقترحة أكثر كفاءة من خوارزمية مستعمرة النمل بمفردها، وخصوصاً للمسائل ذات القياس الكبير، حيث زادت الأداء وخفضت الكلفة لحل مشكلة توجيه المركبة. توصي الورقة بتطبيق الخوارزمية الهجينة على أنواع أخرى من مسألة توجيه المركبة واقتراح طرق هجينة أخرى لمسائل الأمثلية.
Critical review
دراسة نقدية: تقدم هذه الورقة البحثية مساهمة قيمة في مجال حل مسألة توجيه المركبة باستخدام الخوارزميات الهجينة. ومع ذلك، يمكن توجيه بعض الملاحظات النقدية لتحسين البحث. أولاً، لم يتم التطرق بشكل كافٍ إلى تأثير العوامل البيئية والمتغيرات الخارجية على أداء الخوارزمية الهجينة، مما قد يؤثر على نتائج التطبيق العملي. ثانياً، على الرغم من أن النتائج التجريبية أظهرت فعالية النهج المقدم، إلا أن الورقة لم تقدم تحليلًا شاملاً لأداء الخوارزمية في بيئات مختلفة أو مع مجموعات بيانات متنوعة. أخيرًا، كان من الممكن تعزيز البحث بمزيد من الدراسات المقارنة مع خوارزميات هجينة أخرى لتحسين فهم الأداء النسبي للنهج المقترح.
Questions related to the research
-
ما هي مسألة توجيه المركبة (VRP)؟
مسألة توجيه المركبة (VRP) هي مشكلة أمثلية من النوع NP-hard تتعلق بتوجيه عدد من المركبات لخدمة مجموعة من الزبائن بأقل تكلفة ممكنة، مع احترام قيود معينة مثل سعة المركبة والمسافات بين العقد.
-
ما هي الخوارزمية الهجينة المقترحة في هذه الورقة؟
الخوارزمية الهجينة المقترحة تتكون من مرحلتين: في المرحلة الأولى يتم تطبيق خوارزمية المسح (SW)، وفي المرحلة الثانية يتم تطبيق خوارزمية مستعمرة النمل (ACO) مع خوارزمية البحث المحلي 3-opt لتحسين الحلول.
-
ما هي النتائج الرئيسية التي توصلت إليها الورقة؟
أظهرت النتائج التجريبية أن الخوارزمية الهجينة المقترحة أكثر كفاءة من خوارزمية مستعمرة النمل بمفردها، وخصوصاً للمسائل ذات القياس الكبير، حيث زادت الأداء وخفضت الكلفة لحل مشكلة توجيه المركبة.
-
ما هي التوصيات التي قدمتها الورقة لمزيد من البحث؟
توصي الورقة بتطبيق الخوارزمية الهجينة المقترحة على أنواع أخرى من مسألة توجيه المركبة، واقتراح طرق وأساليب هجينة أخرى لمسائل الأمثلية، ودعوة البحوث والدراسات التطبيقية لتحديد أفضل الطرق فعالية لدمج هذه الأساليب.
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 of Operational Research," Vol. 59, No. 3, 1992, pp. 345-358
FISHER .M., "Vehicle Routing. Handbooks of Operations Research and Management Science," chap.1, 1995, pp.8:1-31
GILLETT, B.E.; L.R. MILLER, "A Heuristic Algorithm for the Vehicle Dispatch Problem," Oper Res, 1974, pp.22: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 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.
In this research, we are studying the possibility of contribution in solving the Vehicle
Routing Problem with Time Windows(VRPTW),that is one of the optimization problems
of the NP-hard type.
Moreover, Hybrid algorithm (HA) provided that integrate
s between Tabu Search
Algorithm and Guided Local Search algorithm And existence 2- Opt Local Search, based
on the savings algorithm in terms of continued of a particular objective to provide a lot of
savings. As we will compare the presented approach with standard tests to demonstrate
the efficiency, and their impact on the quality of the solution in terms of speed of
convergence and the ability to find better solutions.
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.
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 ).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
