پاورپوینت مسأله فروشنده دوره گرد (pptx) 34 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 34 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
TSP & VRP
Routing Problem
مسأله فروشنده دوره گرد
مساله فروشنده دوره گرد يکي از بنيادي ترين مسائل مسيريابي و برنامه ريزي حمل و نقل است .هدف از حل اين مسأله ، پيدا کردن کوتاهترين مسيري است که از مجموعه اي از شهرها ( گره ها ) عبور کرده ، بطوريکه هر شهر فقط يکبار ملاقات شود و سپس به شهر اوليه که از آن حرکت را شروع کرده است ، برگردد.
در محدوده ی جغرافیایی فروشنده ی دوره گرد تعدادی شهر وجود دارد که فاصله بین هر زوج از شهر ها مشخص وعددی ثابت است. قرار است فروشنده از یکی از شهر ها شروع کند و کلیه ی شهر ها را ، هر یک را فقط یکبار ، ملاقات کند و در نهایت به نقطه ی شروع برگردد.
مساله فروشنده ی دوره گرد کاربرد های متنوعی دارد. مانند تخلیه ادواری صندوق های پستی به وسیله ی پستچی.
5
این مسئله اولین بار توسط دو دانشمند به نام های 1-هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد.
اولین نمونه شبیه به این مساله درسال 1759 مطرح شد و به این صورت بود که یک مهره اسب می بایست روی بردشطرنج حرکت کند و از هر خانه دقیقا یک بار عبور کند .
مسئله فروشنده دوره گرد جزو مسائل رام نشدنی می باشد و حل دقیق آن زمان زیادی می برد.
6
در این مساله میخواهیم دوری همیلتنی با حداقل هزینه را بیابیم .
در یک گراف جهت دار، یک تور، که به آن دور هامیلتونی نیز گفته می شود عبارت است از مسیری از یک راس به خودش که از تمام رئوس دیگر دقیقا یک بار عبور کند.
نکته: ممکن است گرافی اصلا تور نداشته باشد.
7
نکته: طول تور بهینه وابسته به انتخاب راس آغازین نیست.
این مساله را می توان به صورت ریاضی هم شبیه سازی کرد . به دوری فراگیر G(v,e) این ترتیب که ما در یک گراف وزن دار با مینیمم مجموع وزنهای یالهای گذرنده می خواهیم بیابیم .
در حالت عادی باید کلیه ی روش های ممکن بررسی شود.که در این حالت مرتبه ی زمانی ! n خواهد بود.
8
به روش ریاضی مساله با یافتن تعداد جایگشت ها وسپس ارزیابی هر حالت بررسی می شود .
تعداد جایگشتها n! است. برای یافتن مینیمم دورها نیز به حداکثرn! محاسبه احتیاج داریم. ولی اگر n را زیاد فرض کنیم تعداد محاسبات بسیار بالا خواهد بود
9