Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComparison between branch and cutting algorithm and ant colony algorithm in order to contribute solving the problem of postman Traveling Salesman Problem
مقارنة بين خوارزمية التفريع و القطع ، وخوارزمية مستعمرة النمل ، للمساهمة في حل مسألة البائع المتجول
2943
7 136
0
(
0
)
Authors
ثناء موسى( باحث )
Created by
Shamra Editor
Ask ChatGPT about the research
في هذا البحث ندرس إمكانية المساهمة في حل مسألة البائع المتجول 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 .
References used
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
rate research
Read More
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 ).
In the Multi-objective Traveling Salesman Problem (moTSP)
simultaneous optimization of more than one objective functions is
required. This paper proposes hybrid algorithm to solve the multiobjectives
Traveling Salesman problem through the integration of
the ant colony optimization algorithm with the Genetic algorithm.
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.
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 .
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
