| المستخلص: |
انصب اهتمام هذا البحث على دراسة مسألة البائع المتجول والطرائق المستخدمة في إيجاد الحل للمسألة ، إذ تعد هذه المسألة إحدى مسائل الامثلية المركبـة التـي لاقـت شهرة واسعة واهتماماً كبيراً من لدن الباحثين وذلك لصياغتها البسيطة وتطبيقاتها المهمـة وارتباطها الممتع ببقية المسائل التركيبية ، إذ تقوم على إيجاد المسار الأمثل مـن خـلال عدد معلوم من المدن بحيث يزور البائع كل مدينة مرة واحدة فقط قبل العودة إلى المدينـة التي انطلق منها . تم في هذا البحث توظيف مزايا خوارزمية التفريع والتحديد باعتبارها احد الطرائق المثلى لحل مسألة البائع المتجول (TSP) وأدى تطبيق الخوارزمية بالارتباط مع إحـدى الطرائق الحدسية إلى تقليل عدد التفرعات في شجرة البحث ومن ثم الوصول إلى الحل الأمثل بسهولة ، وتم اقتراح بعض التحسينات للوصول إلى الحل الأمثل بيسر و بسهولة . كذلك اقترحت خوارزمية جينية لحل مسألة البائع المتجول وبالأخص فـي حـل المسائل الكبيرة والمعقدة ، وقد أدى استخدامها إلى إيجاد المسار الأمثل ( أو القريب إل ـى الأمثل ) في الجيل الأول والثاني مما يدل على كفاءتها .
The main focus of this research is to examine the Travelling Salesman Problem (TSP) and the methods used to solve this problem , where this problem is considered as one of the combinatorial optimization problems which met wide publicity and attention from the researches for to it's simple formulation and important applications and engagement to the rest of combinatorial problems , which is based on finding the optimal path through known number of cities where the salesman visits each city only once before returning to the city of departure . In this research , the benefits of Branch and bound algorithm is employed as one of the best methods to solve the (TSP) problem and the application of the algorithm in conjunction with one of the heuristic methods to reduce the number of the branches in the search tree and thus have access to the best solution easily , some improvements have been proposed to reach the best solution smoothly and easily . In addition , a genetic algorithm is proposed as well to solve the (TSP) problem , especially in solving large and complex issues , and this usage has led to find the optimal path ( or semi optimal ) in the first and second generation , which indicates it's efficiency
|
