……………. 13

2-4- تقسیم بندی مساله VRP کلاسیک ……………………………………………………………………………. 13

2-4-1- مسیریابی وسیله ی نقلیه با دیدگاه ظرفیت (CVRP) ………………………………………… 14

2-4-2- مسیریابی وسیله ی نقلیه با حمل در بازگشت (VRPB) …………………………………… 15

2-4-3- مسیریابی وسیله ی نقلیه با چنجره ی زمانی(VRPTW) …………………………………… 15

2-4-4- مسیریابی وسیله ی نقلیه با تقاضای دریافت و تحویل (VRPPD) ……………………… 16

2-4-5- مسیریابی دوره ای وسیله ی نقلیه(PVRP) …………………………………………………….. 16

2-4-6- مسیریابی وسیله ی نقلیه با چهارچوب اتفاقی (SVRP) ……………………………………. 17

2-5-ادبیات مسیریابی وسایل نقلیه با تقاضای تحویل و دریافت همزمان (VRPSPD) ……. 18

2-6-ی بر تحقیقات انجام شده در مورد مساله مسیریابی وسایل نقلیه دارای چند مرکز تامین (MDVRP) …………………………………………………………………………………………………………………… 24

2-7- جمع بندی ……………………………………………………………………………………………………………. 27

فصل سوم:مدل ریاضیپیشنهادی …………………………………………………………………………….. 28

3-1- مقدمه …………………………………………………………………………………………………………………… 29

3-2- تعریف مسئله ………………………………………………………………………………………………………… 29

3-2-1- مفروضات مسئله ……………………………………………………………………………………….. 30

3-3- مدل ریاضی پیشنهادی ……………………………………………………………………………………………. 30

3-3-1- اندیس ها ………………………………………………………………………………………………….. 31

3-3-2- پارامترهای ورودی مدل ……………………………………………………………………………… 31

3-3-3- متغیر های تصمیم گیری …………………………………………………………………………….. 31

3-3-4- تابع هدف ………………………………………………………………………………………………… 32

3-3-5- محدودیت ها ……………………………………………………………………………………………. 32

3-4-اعتبارسنجیمدل ……………………………………………………………………………………………………. 35

3-5- پیچیدگی مدل مورد بررسی …………………………………………………………………………………….. 36

3-6- جمع بندی ……………………………………………………………………………………………………………. 39

فصل چهارم: الگوریتم فراابتکاری پیشنهادی ……………………………………………………………….. 40

4-1- مقدمه ای بر مسائل بهینه سازی ……………………………………………………………………………….. 41

4-1-1- تئوری پیچیدگی ………………………………………………………………………………………… 41

4-1-2- روش های بهینه سازی ……………………………………………………………………………….. 42

4-2- الگوریتم ژنتیک ……………………………………………………………………………………………………… 46

4-2-1- برخی از اصطلاحات الگوریتم ژنتیک …………………………………………………………… 48

4-2-2- روش های انتخاب کروموزوم ……………………………………………………………………… 50

4-2-3- تقاطع ……………………………………………………………………………………………………….. 52

4-2-4- جهش ………………………………………………………………………………………………………. 53

4-3- الگوریتم کلونی مورچگان ……………………………………………………………………………………….. 54

4-3-1- مزیت­های روش کلونی مورچگان ………………………………………………………………… 60

4-3-2- مراحل پیاده­سازی الگوریتم کلونی مورچگان …………………………………………………. 61

4-4- الگوریتم مورچگان پیشنهادی ………………………………………………………………………………….. 62

4-4-1- تبدیل مسئله به یک گراف جهت­دار ………………………………………………………………. 62

4-4-2- نحوه­ی ساختن پاسخ برای مسئله …………………………………………………………………… 62

4-4-3- بروزرسانی فرومون ها …………………………………………………………………………………. 63

4-5- ارزیابی الگوریتم ها ………………………………………………………………………………………………… 63

4-5-1- مجموعه داده ها ………………………………………………………………………………………… 64

4-5-2- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد کوچک …………………………………. 65

4-5-3- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد متوسط تا بزرگ ……………………… 67

4-6- مطالعه موردی ……………………………………………………………………………………………………….. 69

4-7- جمع بندی ……………………………………………………………………………………………………………. 72

فصل پنجم: نتیجه گیری و پیشنهادات ………………………………………………………………………… 73

5-1- مقدمه …………………………………………………………………………………………………………………… 74

5-2- نتیجه گیری …………………………………………………………………………………………………………… 74

5-3- پیشنهادات آتی ………………………………………………………………………………………………………. 75

فهرست منابع و مآخذ ………………………………………………………………………………………………………. 76

جدول 3-1 : داده های مسئله آزمایشی مربوط به هر گره …………………………………………………… 35

جدول 3-2: داده های مسئله آزمایشی مربوط به فواصل زمانی بین گره ها …………………………… 35

جدول 3-3 : زمان های تکمیل ویزیت هر گره در مسئله آزمایشی ……………………………………… 36

جدول 4-1 : مقادیرداده های ورودیبه مسائل آزمایشی …………………………………………………… 65

جدول 4-2 : نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک …………………………………….. 66

جدول 4-3 : زمان های محاسباتی و میانگین جواب های حاصل از حل مسائل با ابعاد کوچک… 66

جدول 4-4 : نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط تا بزرگ ………………………….. 68

جدول 4-5 : نتایج محاسباتی حاصل از حل مسئله کاربردی ……………………………………………….. 71

شکل 1-1 : مسأله فروشنده دوره گرد ………………………………………………………………………………… 4

شکل 1-2 : مسأله مسیریابی وسیله نقلیه …………………………………………………………………………….. 4

شکل 1-3 : نشان دهنده ی ارتباط بین نمونه های مختلف VRP …………………………………………….. 5

شکل 3-1 : سلسله مراتب پیچیدگی محیط های کارگاهی در مسائل زمانبندی ………………………. 38

شکل 3-2 : سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ……………………………………. 38

شکل 4-1 : انواع روش های بهینه سازی ………………………………………………………………………….. 43

شکل 4-2 : مکانیزم انجام عملگر تقاطع یک نقطه ای در مسائل جایگشتی ……………………………. 53

شکل 4-3 : نحوه انجام عملگر تعویض در مسائل جایگشتی ……………………………………………… 54

شکل 4-4 : رفت و برگشت مورچگان به آشیانه و منبع غذایی ……………………………………………. 56

شکل 4-5 : ایجاد یک مانع در مسیر آشیانه تا منبع غذایی مورچگان …………………………………….. 57

شکل 4-6 : ادامه حرکت مورچگان علی رغم حضور مانع ……………………………………………………. 57

شکل 4-7 : انتخاب مسیر کوتاهتر توسط همه­ی مورچه ها …………………………………………………… 58

شکل 4-8 : مقایسه زمان­های محاسباتی مورد نیاز نرم افزار لینگو و الگوریتم­های پیشنهادی ……… 67

شکل 4-9 : عکس هوایی از 161 سوپر مارکت مورد بررسی ……………………………………………….. 70

چکیده

در این تحقیق، مسئله مسیریابی ویزیتورها با در نظر گرفتن مهارت ویزیتورها و زمان­های ویزیت متفاوت و زمان­های حمل و نقل بین سوپر مارکت­ها به منظور ایجاد بهترین تعادل بار کاری بین ویزیتورها با توجه به مهارت و تجربه آن­ها در نظر گرفته شده است. در این پایان نامه برای حل این مسئله از دو رویکرد استفاده شده است. در رویکرد اول یک مدل برنامه­ریزی عدد صحیح مختلط برای مسئله یاد شده اردئه شده است. اما از آنجاییکه که مدل ریاضی ارائه شده تنها قادر به حل مسائل با ابعاد کوچک می­باشد، که این موضوع کاربرد الگوریتم­های فراابتکاری را اجتناب ناپذیر می­سازد. دو رویکرد دوم برای مسئله فوق دو الگوریتم­ فراابتکاری شامل « الگوریتم ژنتیک » و « الگوریتم بهینه سازی کلونی مورچگان » به منظور حل مدل در مقیاس­های کاربردی ارائه شده است. نتایج محاسباتی نشان دهنده برتری الگوریتم مورچگان نسبت به الگوریتم ژنتیک در حل مسائل با ابعاد واقعی را دارد. در ادامه مسئله­ی فوق را در بخش فروش شرکت تولیدی بریان گوشت پیاده سازی کرده ایم.

مقدمه

از آنجا­ییکه فروش کالا به عنوان شریان اصلی هر سازمان محسوب می­شود. بنابراین بهبود کارایی در عملکرد کاری فروشندگان و افزایشسطح رضایتمندیآن­ها کمک بسزایی در افزایش سطج تحقق اهداف تعیین شده فروش سازمان می­نماید. . بیشتر مسایل حوزه تخصیص مسیر مناسب و بهینه می­توانند به صورت مساله مسیریابی وسیله نقلیه[1] (VRP) درنظر گرفته شوند که تعمیم مساله فروشنده دوره گرد[2] است و یکی از مسایل مهم در محدوده مسایل بهینه سازی ترکیبی است که روش­های مکاشفه­ای زیادی برای حل آن ایجاد شده است.

مساله مسیریابی وسیلهء نقلیه، شامل تعدادی مشتری است که هر یک به میزان خاصی کالا نیاز دارند که باید به آنها تحویل گردد. هدف، تعیین مجموعه­ای از مسیرها (یا تورها) است که کمترین مجموع هزینه را دارا بوده، در انبار آغاز شده و در آن پایان یابند، هر مشتری دقیقا یکبار و توسط یک فروشنده بازدید شود و کل تقاضای گره­های هر مسیر از ظرفیت وسیله تجاوز نکند.که در این پژوهش فروشنده نقش وسیله نقلیه را در مدل VRP بازی می کند.

از آنجا که VRP یک مساله بهینه سازی ترکیبی است و حل آن با روشهای دقیق به زمان نمایی نیاز دارد، روشهای مکاشفه­ای زیادی برای حل آن به کاررفته است. در این پژوهش از الگوریتم ژنتیک(GA) و مورچگان(ACO) برای حل VRP استفاده شده است.