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

 

– مدل ریاضی پیشنهادی ……………………………………………………………………………………………. 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 : داده های مسئله آزمایشی مربوط به هر گره ……………………………………………………   3

 

جدول 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

 

1-1- مقدمه  ……………………………………………………………………………………………………………………  2

 

1-2- تعریف موضوع  ………………………………………………………………………………………………………  3

 

1-3- بیان مساله………………………………………………………………………………………………………………..  5

 

1-4- ضرورت انجام تحقیق……………………………………………………………………………………………….  6

 

1-5- اهداف تحقیق………………………………………………………………………………………………………….. 6

 

1-6- مفروضات مساله ……………………………………………………………………………………………………… 7

 

1-7- روش پژوهش …………………………………………………………………………………………………………. 7

 

1-7-1- مطالعات مورد کاوی و تجربی ………………………………………………………………………. 8

 

1-7-2- چهار چوب­ها ، دسته بندی و مرور ادبیات ……………………………………………………… 8

 

1-7-3- مدل­های کمی ……………………………………………………………………………………………… 8

 

1-8- مراحل اجرای تحقیق و روش های گرد آوری اطلاعات ………………………………………………… 8

 

1-9- جامعه آماری و روش های گرد آوری اطلاعات …………………………………………………………… 9

 

فصل دوم: ادبیات و پیشینه تحقیق …………………………………………………………………………….. 10

 

2-1- مقدمه …………………………………………………………………………………………………………………… 11

 

2-2- بر مسائل VRP …………………………………………………………………………………………… 12

 

2-3- تاریخچه VRP ………………………………………………………………………………………………………. 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

 

– مدل ریاضی پیشنهادی ……………………………………………………………………………………………. 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 استفاده  شده است.

 

سیاست های اجرایی در این پایان نامه عبارت است از :

 

 

    1. بهبود مسیر ویزیت فروشندگان

 

    1. یکنواختی بار کاری فروشندگان

 

    1. افزایش سطح رضایتمندی فروشندگان

 

  1. افزایش سطح درصد تحقق اهداف و افزایش فروش سازمان

 

1-2- تعریف موضوع

 

مسائل مسیریابی وسایل نقلیه یکی از مفاهیم مورد توجه در زمینۀ تحقیق در عملیات است که در دو دهۀ اخیر تلاش‌ها و به تبع آن پیشرفت های عظیمی در این زمینه انجام گرفته است. مسأله مسیر یابی وسایل نقلیه به مسائلی گفته می­شود که در آن ناوگانی از چندین وسیلۀ نقلیه از یک یا چند تسهیل (قرارگاه) به سرویس­دهی مشتریان در نقاط تقاضا می پردازند. به نحوی که هزینه­های انجام کار حداقل گردد. وسیلۀ نقلیه با شروع از قرارگاه­های مرکزی پس از ارائه خدمت به متقاضیان باز می­گردد.

 

هر وسیله می­تواند دارای ظرفیت محدود بوده و همۀ مسیرهای مربوط از مبدأ (قرارگاه مرکزی) شروع و بعد از خدمت­رسانی به آن باز می­گردد. تابع هدف این مسائل می­تواند ارائه خدمت به مشتریان با کمترین تعداد خودرو،  برآورده شدن همۀ تقاضاها و حداقل مسافت طی شده تعریف گردد.

 

مسأله مسیر­یابی وسیله‌ی نقلیه، تعمیم یافته‌ی مدل فروشنده‌ دوره گرد است. مسأله فروشنده‌ی دوره گرد یکی از بنیادی ترین مسائل مسیر یابی و برنامه ریزی حمل و نقل است. در مسأله فروشنده دوره گرد هدف یافتن کوتاه ترین مسیری است که از همه‌ی شهرها عبور کند و از هر شهر فقط یک بار ملاقات به عمل آید و سپس به شهر اولیه که از آن شروع به حرکت کرده است، باز گردد.

 

این در حالی است که مسأله مسیر یابی وسیلۀ نقلیه می تواند به وسیلۀ یک گراف (V ,A ,D )=G نشان داده شود که {V0 ,V1 ,V2 ,… ,Vn}= V مجموعه ای از گره‌ ها و {i  : (Vi ,Vj)} =  A مجموعه ای از کمان های متصل کننده گره ها هستند. D نیز متناسب با فاصله بین این گره ها یا طول کمان هاست. نقطۀ  نشانگر قرارگاه و  تا  مشتریان را نشان می دهد.  که با هر کمان (i, j ) مرتبط است نشانگر مسافت یا زمان مسافرت و یا هزینه مسافرت است.  برای هر مشتری Vi یک تقاضای qi  و یک زمان خدمت در نظر گرفته شده است و هدف پیدا کردن حداقل هزینه‌ی مسیرهای حمل و نقل است که در آن :

 

 

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...