در طی سال‌های گذشته، تلاش‌های زیادی به جهت کاهش هزینه حمل و نقل با بهره گرفتن از مدل‌های متفاوت مسأله مسیریابی وسیله نقلیه صورت گرفت. در واقع افزایش در هزینه های حمل و نقل بسیاری را تشویق کرد که هزینه حمل و نقل مرتبط با حرفه خود را با بهره‌گیری از سیستم مسیریابی وسیله نقلیه کاهش دهند. در این تحقیق ما مسأله مسیریابی وسیله نقلیه چند انبار با پنجره زمانی را مورد بررسی قرار می‌دهیم.

مسأله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی شامل ناوگانی از وسایل نقلیه می‌باشد که از انبارها حرکت نموده، دسته‌ای از مشتریان را ملاقات کرده و به انبار بر می‌گردند. ما در این تحقیق حالتی را در نظر گرفته ایم که دیگر نیازی نمی‌باشد هر وسیله نقلیه بعد از ملاقات مشتریان به انبار شروع حرکت برگردد بلکه ممکن است انبار ابتدای مسیر با انبار انتهای مسیر متفاوت از یکدیگر باشند. هر وسیله نقلیه دارای یک ظرفیت ثابت است، و هر مشتری دارای تقاضای مشخص است که باید کاملا ارضا شود. مسأله شامل ترکیب انتخاب ملاقات برای هر مشتری و تعیین مسیرهای وسایل نقلیه براساس قوانین مسأله مسیریابی وسیله نقلیه است؛ بطوریکه کل مسافت طی شده توسط هر وسیله نقلیه و کل زمان‌های زودکرد و دیرکرد و در مجموع کل هزینه کمینه شود.

از آنجائیکه مسأله مسیریابی وسیله نقلیه یک مسأله متعلق به کلاس NP-Hard است مسأله مسیریابی وسیله نقلیه چند انباره با پنجره زمانی نیز به عنوان تعمیمی از VRP جزء مسائل پیچیده و متعلق به کلاس NP-Hard است و برای حل آن از رویکردهای فراابتکاری استفاده می‌شود. در این پایان‌نامه الگوریتم ژنتیک برای حل مسأله مسیریابی وسیله نقلیه چند انباره با پنجره زمانی پیشنهاد شده است. وسعی شده است با بهره گرفتن از روش خوشه بندی ژنتیک، مشتریان را دسته‌بندی کرده تا فضای جستجوی مسأله را کاهش داده و سپس با بهره گرفتن از الگوریتم ژنتیک مجموعه جواب و تابع هدف مسأله را بدست می‌آ‌وریم.

کلمات کلیدی: مسیریابی وسایل نقلیه، چند‌انبار، پنجره زمانی، خوشه‌بندی، الگوریتم ژنتیک

 

فهرست مطالب

عنوان                    صفحه

:… 1

1-1مقدمه. 2

1-2- ضرورت و اهمیت برنامه ریزی حمل‌ونقل.. 3

1-3- حمل‌ونقل در ایران.. 4

1-4- هدف از انجام مطالعه. 5

1-5- تعریف مسأله. 6

1-6- جمع‌بندی و ساختار ارائه مطالب… 7

:… 9

2-1-مقدمه. 10

2-2- مسأله مسیریابی.. 10

2-3- مسأله فروشنده دوره‌گرد. 10

2-4- مسأله مسیریابی وسایل نقلیه. 13

2-5- اجزای مسأله VRP. 14

2-5-1- خصوصیات کلی مشتریان.. 14

2-5-2 خصوصیات  وسایل نقلیه. 15

2-5-4- انواع توابع هدف در VRP. 16

2-5-6 برخی مشکلات مدل‌سازی VRP در شرایط واقعی.. 16

2-6- تعریف ریاضی مسأله مسیریابی وسیله نقلیه در حالت کلی.. 17

2-6-1  مدل عمومی مسأله VRP. 18

2-7-روش های حل مسأله مسیریابی وسایل نقلیه کلاسیک… 20

2-7-1-روش‌های دقیق.. 20

2-7-2-روش های ابتکاری.. 22

2-7-3-روش های فراابتکاری.. 24

2-8- انواع اصلی مسأله مسیریابی وسیله نقلیه. 26

2-8-1 مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه. 27

2-8-2-مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن.. 28

2-8-3-مسأله مسیریابی وسایل نقلیه با تقسیم تحویل.. 30

2-8-4- مسیریابی وسیله نقلیه با تحویل و جمع آوری.. 33

2-8-5- مسأله مسیریابی دورهای وسایل نقلیه. 34

2-8-5-1 تعریف ریاضی مسأله مسیریابی دوره ای وسایل نقلیه (PVRP) 35

2-8-5-2- مدل ریاضی PVRP. 37

2-8-6- مسأله مسیریابی وسایل نقلیه با چند انبار. 41

2-8-6-1-تعریف ریاضی مسأله MDVRP. 42

2-8-7- مسأله مسیریابی وسایل نقلیه با پنجره زمانی.. 44

2-8-7-1 تقسیم بندی مسأله VRPTW… 45

2-8-7 -1-1 مدل های پنجره‌‌های زمانی سخت… 46

2-8-7-1-2-  مدل های پنجره‌های زمانی نرم. 46

 

 

2-9- جمع‌‌بندی.. 53

:… 55

3-1 مقدمه. 56

3-2 خصوصیات و فرضهای مدل.. 56

3-2-1-فرضیات.. 56

3-2-2 تعریف علائم و پارامترها 56

3-2-2-1 اندیسها 57

3-2-2-2 پارامترها 57

3-2-2-3 متغیرهای تصمیم‌گیری.. 58

3-2-2-4 مدل ریاضی.. 58

3-3 مروری بر الگوریتم ژنتیک (GA) 60

3-3-1 تعریف… 60

3-3-2 گذری بر ژنتیک طبیعی.. 61

3-3-3 واژگان الگوریتم ژنتیک… 66

3-3-4 ساختار کلی الگوریتم ژنتیک… 67

3-3-5 مفاهیم کلیدی الگوریتم ژنتیک… 68

3-3-6 کدینگ… 69

3-3-7 ایجاد جمعیت اولیه. 71

3-3-8 اعمال ژنتیک… 71

3-3-8 -1 عمل تحول.. 72

3-3-8 -1 -1فضای نمونه گیری.. 72

3-3-8 -1 -2مکانیسم نمونه‌گیری.. 73

3-3-8 -1-4 نخبه گرایی.. 75

3-3-8 -2 عملگرهای ترکیبی.. 75

3-3-8 -2 -1 انواع عملگرهای ترکیبی.. 75

3-3-8 -2 -2 احتمال ترکیب… 78

3-3-8 -3 عملگرهای جهشی.. 79

3-3-8 -3 -1 انواع عملگرهای جهشی.. 80

3-3-9 تابع برازش… 81

3-3-10 روش اجرای الگوریتم ژنتیک… 82

3-4 ساختار پیشنهادی الگوریتم ژنتیک… 84

3-4 -1خوشه بندی ژنتیک… 84

3-4 -1-1 نمایش رشته(کروموزوم) 84

3-4-1 -2 ساخت جمعیت اولیه. 85

3-4-1 -3 محاسبه تابع برازش… 85

3-4 -1-3 انتخاب.. 85

3-4 -1-4 ترکیب… 86

3-4 -1-5 جهش…. 86

3-4 -1-6 شرط توقف… 87

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

3-4-2 -1 نحوه نمایش جواب‌ها 87

3-4-2 -2 تعریف میزان برازندگی.. 88

3-4-2 -3 مکانیزم انتخاب.. 89

3-4-2 -3 عملگر ترکیب… 89

3-4-2 -4 عملگر جهش…. 91

3-5 الگوریتم K-Mean. 92

3-6 الگوریتم خوشه‌بندی فازی  (FCM) Fuzzy c-mean. 92

: 95

4-1 مقدمه. 96

4-2 ویژگی های نرم افزار. 96

4-3 مشخصات مسائل نمونه. 96

4-4 تعیین پارامترها 97

4-5 نتایج محاسباتی.. 97

4-6 جمع بندی.. 102

:

5-1 نتیجه گیری.. 104

5-2 تحقیقات آتی.. 104

منابع ومآخذ. 106

– مقدمه

توسعه روز‌افزون شهر نشینی، صنایع و بخصوص صنایع پشتیبانی، جابجایی انسان و کالا را به صورت مسأله‌ای در آورده است که پیچیدگی آن دائماً در حال افزایش می‌باشد. رشد شهری باعث افزایش تقاضا در صنعت حمل و نقل شده که به تبع آن شهرها و صنایع بزرگ را دست به گریبان مشکلات زیادی در زمینه‌های تراکم ترافیکی، آلودگی هوا، اتلاف وقت‌های طولانی در مسیر سفرهای روزانه افراد، افزایش مصرف سوخت و استهلاک وسایل نقلیه و غیره کرده است.

برای حل مشکلات ترافیکی و مسایل اقتصادی، اجتماعی و زیست محیطی ناشی از آن در شهرهای بزرگ، صنایع تولیدی و بخش خدمات نیاز به یک سیستم مجهز و کارآمد حمل و نقل می‌باشد. در نتیجه تقاضای رو به افزایش برای راه ‌حل ‌هایی که اجرایی باشند و بتوانند تمامی منافع پیش‌بینی شده از جمله صرفه‌جویی در هزینه‌ها را با در نظر گرفتن حداکثر سرویس و استفاده بهینه از سرمایه و تجهیزات را حاصل نمایند وجود دارد. حمل و نقل داخل سازمانی، مسیر حرکت اتوبوس‌ها، سرویس‌های مدارس، سیستم‌های توزیع و نگهداری پخش پول و سرویس‌های بانکی و جمع‌ آوری ضایعات صنعتی و غیره از جمله مسایلی هستند که می‌توان به آنها اشاره کرد.

برنامه ریزی حمل و نقل، امروزه یکی از زمینه‌های اساسی و مطرح در شاخه‌های مختلف علوم همانند تحقیق در عملیات، مهندسی صنایع و مهندسی عمران می‌باشد. هدف عمده این رشته، کمینه‌سازی هزینه حمل و نقل کالا و مواد بین دو سطح تولیدکننده و مصرف کننده می‌باشد، به طوری که تقاضای هر مصرف‌کننده باید توسط تولیدکنندگان ارضاء گردد. در این حالت با توجه به نوع مسأله مورد نظر عواملی همانند طول مسیر، کیفیت مسیر از لحاظ ساختاری و محیطی، ترافیک مسیر، گنجایش وسایل نقلیه و غیره مد نظر قرار می‌گیرند. چنانچه علاوه بر دو سطح تولید کننده و مصرف کننده، سطوح میانی نیز وجود داشته باشند، به آن شبکه حمل و نقل گفته می‌شود. به عنوان نمونه مسیریابی اتوبوس‌های داخل شهری حالت خاصی از شبکه حمل و نقل می‌باشد.

1-2- ضرورت و اهمیت برنامه‌ریزی حمل‌ونقل

حمل و نقل یکی از بخش‌های عمده و مهم، از اقتصاد هر کشوری به شمار می‌رود و همچنین یکی از مهمترین بخش‌های تشکیل دهنده هزینه تمام شده محصولات نهایی است. توسعه روز افزون شهر‌نشینی، صنایع و بخصوص صنایع پشتیبانی، جابجایی انسان و کالا را بصورت مسأله‌ای در آورده‌است که پیچیدگی آن دائماً در حال افزایش است. رشد شهری باعث افزایش فزاینده تقاضا در صنعت حمل‌ونقل شده که به تبع آن شهرها و صنایع بزرگ را دست به گریبان مشکلات زیادی در زمینه‌های تراکم ترافیکی، آلودگی هوا، اتلاف وقت طولانی در مسیر سفرهای روزانه افراد، افزایش مصرف سوخت و استهلاک وسایل نقلیه و غیره کرده است. برای حل مشکلات ترافیکی و مسایل اقتصادی، اجتماعی و زیست محیطی ناشی از آن در شهرهای بزرگ، صنایع تولیدی و بخش خدمات نیاز به یک سیستم مجهز و کارآمد حمل‌ونقل دارند. در نتیجه تقاضای رو به افزایش برای راه ‌حل ‌هایی که اجرایی بوده و بتواند تمامی منافع پیش‌بینی‌شده از جمله صرفه‌جویی در هزینه‌ها را با در نظر گرفتن حداکثر سرویس و استفاده بهینه از سرمایه و تجهیزات حاصل نماید، وجود دارد. نظافت خیابان‌ها، حمل‌ونقل داخل سازمانی، مسیرحرکت اتوبوس ها، سرویس مدارس، سیستم‌های توزیع و نگهداری پخش پول و سرویسهای بانکی و جمع آوری ضایعات صنعتی و غیره ازجمله مسایلی است که می توان به آن اشاره کرد.

در دهه‌ های اخیر نتایج سودمندی در پروژه‌های بهینه‌سازی، بر مبنای روش‌های تحقیق در عملیات و برنامه‌ریزی ریاضی، در مدیریت موثر تدارک کالا و خدمت‌رسانی سیستم‌های توزیع دیده شده است. تعداد زیادی از کاربردهای واقعی جهانی، هم در آمریکای شمالی و هم در اروپا، بطور وسیع نشان داده که استفاده از روال‌های کامپیوتری برای برنامه‌ریزی فرایند توزیع، صرفه‌جویی قابل توجهی را (معمولاً بین 5% تا 25%) در هزینه‌های عمومی حمل‌ونقل موجب می‌شود.