از آنجائیکه مسأله مسیریابی وسیله نقلیه یک مسأله متعلق به کلاس 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

http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%da%a9%d8%a7%d8%b1%d8%b4%d9%86%d8%a7%d8%b3%db%8c-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b1%d8%b4%d8%ahttp://zusa.ir/%d8%b3%d9%85%db%8c%d9%86%d8%a7%d8%b1-%d8%a7%d8%b1%d8%b4%d8%af-%d9%85%d9%87%d9%86%d8%af%d8%b3%db%8c-%d8%b4%db%8c%d9%85%db%8c-%d8%b7%d8%b1%d8%a7%d8%ad%db%8c-%d9%81%d8%b1%d8%a2%db%8c%d9%86%d8%af-%d8%a8-3/http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a8%d8%b1%d8%b1%d8%b3%db%8c-%d8%b9%d9%88%d8%a7%d9%85%d9%84-%d9%85%d8%a4%d8%ab%d8%b1-%d8%a8%d8%b1-%d9%87%d9%85%d8%b3%d9%88%db%8c%db%8c-2/http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%ad%d9%82%d9%88%d9%82-%d8%a8%d8%a7-%d9%85%d9%88%d8%b6%d9%88%d8%b9%d8%aa%d9%82/http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d9%85%d9%82%d8%a7%db%8c%d8%b3%d9%87-%d8%a7%d8%b6%d8%b7%d8%b1%d8%a7%d8%a8%d8%8c-%d8%b3%d8%a8%da%a9%d9%87%d8%a7%db%8c-%d9%88%d8%a7/a%d9%87-%d9%85%d9%87-44/http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%b4%d9%86%d8%a7%d8%b3%d8%a7%d9%8a%d9%8a-%d9%88-%d8%b1%d9%8a%d8%b4%d9%87-%d9%8a%d8%a7%d8%a8%d9%8a-%d8%b9%d9%88%d8%http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8http://zusa.ir/%d8%b3%d9%85%db%8c%d9%86%d8%a7%d8%b1-%d8%a7%d8%b1%d8%b4%d8%af-%d9%85%d9%87%d9%86%d8%af%d8%b3%db%8c-%d8%b4%db%8c%d9%85%db%8c-%d9%85%d9%87%d9%86%d8%af%d8%b3%db%8c-%d9%81%d8%b1%d8http://zusa.ir/%d8%af%d8%a7%d9http://zusa.ir/%d9%be%d8http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%ad%d9%84-%d9%85%d8%b3%d8%a6%d9%84%d9%87-%d9%85%d8%b3%db%8c%d8%b1%db%8c%d8%a7/ %a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%dhttp://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b1%d8%a7%d8%a8%d8%b7%d9%87-%d8%a8%db%8c%d9%86-%d8%b1%d8%b6%d8%a7%db%8c%d8%aa/ 9%87-%d8http://zusa.ir/48551-2/ %a7%d8%b1%d8%b4%d8%af-%d9%be%d8%b1%d8http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%aa%d8%a7%d8%b1%db%8c%d8%ae-%d8%b1%d9%88%d8%a7%d8%a8%d8%b7-%d8%b5%d9%88%d9%81%db%8c%d8%a7%d9%86-%da%af%d9%86%d8%a7%d8%a8%d8%a7%d8%af%db%8c/ %a7%da%a9%d9%86%d8%b4-%d9%85%da%a9%d8%http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%aa%d8%a8%d8%a7%d8%b7-%d8%a8%db%8c%d9%86-%d8%aa%d9%88%d8%a7%d9%86-%d9%87%d9%88%d8%a7%d8%b2%db%8c-%d8%a8%d8%a7-%d8%aa%d9%88%d8%a7/ a7%d9%86%db%8c-%d9%88-%d8%b2%d9%85%d8%a7%d9%86%db%8c-%da%af/ %86%d9%84%d9%88%d8%af-%d9%be%d8http://zusa.ir/%d9%85%d9http://zusa.ir/%d8%af%d8%a7%d9http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%a8%d8%b1%d8%b1%d8%b3%db%8c-%d8%b1%d8%a7%d8%a8%d8%b7%d9%87-%d8%a8%db%8c-28/ %86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87%d8%a8%d8%b1%d8%b1%d8%b3%db%8c-%d8%a7%d8%ab%d8%b1-%d8%b9%d8%b3%d9%84-%d9%88-%d8%b2%d9%86%d8%ac%d8%a8%db%8c/ %82%d8%a7%d9%84%d9%87-%d8%b1%d8%a7%db%8c%da%af%d8%a7%d9%86%d8%b1%db%8c%d8%b2%d8%a7%d8%b2%d8%af%db%8c%d8%a7%d8%af%db%8c-%d8%ae%d8%aa%d9%85%db%8c-%da%86%db%8c%d9%86%db%8c-%d8%af%d8%b1-%d8%b4/ %a7%db%8c%d8%a7%d9%86-%d9http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%da%a9%d8%a7%d8%b1-%d8%aa%d8%ad%d9%82%db%8c%d9%82%db%8c-%d9%88%da%a9%d8%a7%d9%84%d8%aa-%d8%a8%d8%a7-%d9%85%d9%88%d8%b6%d9%88%d8%b9-%d8%af%d8%a7%d8%af%d8%b1%d8%b3/ %86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%a8%d8%b1%d8%b1%d8%b3%d9%http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a8%d8%b1%d8%b1%d8%b3%db%8c-%d8%a7%d8%ab%d8%b1-%d8%a8%d8%ae%d8%b4%db%8c-%d8%af%d8%b1%d9%85%d8%a7%d9%86-%d8%b4%d9%86%d8%a7%d8%ae%d8%aa%db%8c/ 8a-%d8%a7%d8%ab%d8%b1-%d8%http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b1%d8%b4%d8%aa%d9%87-%d9%81%d9%82%d9%87-%d9%88-%d9%85%d8%a8%d8%a7%d9%86%db%8c-%d8%ad%d9%82%d9%88%d9%82-%d8%a7%d8%b3/ b3%d8%b7%d9%88%d8%ad-3/ %a2%db%8c%d9%86%d8%af-6/http://zusa.ir/%d8%af%d8%a7%d9http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b7%d8%b1%d8%a7%d8%ad%d9%8a%d8%8c-%d8%aa%d9%87%d9%8a%d9%87-%d9%88-%d8%a7%d8%b3%d8%aa%d8%a7%d9%86%d8%af%d8%a7%d8%b1/ %af-%da%a9%d8%a7%d8%b1-%d8%aa%d8%ad%d9http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b1%d8%b4%d8%aa%d9%87-%d9%85%d8%af%db%8c%d8%b1%db%8c%d8%aa-%d8%a2%d9%85%d9%88%d8%b2%d8%b4%db%8c-%d8%a7%d8%b1%d8%b2/ %82%db%8c%d9%82%db%8c-%d9%88%da%a9%d8%a7%d9%84%d8%aa-%d8%a8%d8%a7-%d9%85%d9%88%d8%b6%d9%88%d8%b9-%d9%84%d8%a7-%d8%b6%d8%b1/ %86%d9%84%d9%88%d8%af-%d9%be%d8http://zusa.ir/%d8%af%d8%a7%d9http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%a8%d8%af%d8%a7%d8%b9-%d8%af%d8%b3%d8%aa%da%af%d8%a7%d9%87-%d8%ac%d8%af%db%8c%d8%af-%d8%a7%d8%b3%d8%a7%d9%86%d8%b3-%da%af%db%8c%d8%b1/ %86%d8%a7%d9%85%d9%87-%d8%af%d8%b1-%d9%85%d9%88%d8%b1%d8%af-%d9%be%db%8c%d8%a7%d8%af%d9%87-%d8%b1%d8%a7%d9%87/ %86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b1%d8%b4%d8%aa%d9%87-%d9%85%da%a9%d8%a7%d9%86%db%8c%da%a9-%d8%a8%d8%b1%d8%b1-2/ %a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d9%be%d9%8a%d8%b4-%d8%a8%d9%8a%d9%86%d9%8a-%d9%82%d9%8a%d9%85%d8%aa-%d8%b3/ %a7%d8%b1%d8%b4%d8%af-%d8%b4%d9%86%d8%a7%d8http://zusa.ir/%d9%be%d8http://zusa.ir/%d9%be%d8http://zusa.ir/%d9%be%d8http://zusa.ir/%d9%be%d8http://zusa.ir/%d9%be%d8http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d9%85%d9%87%d9%86%d8%af%d8%b3%db%8c-%d8%b5%d9%86%d8%a7%db%8c%d8%b9-%da%af%d8%b1%d8%a7%db%8c%d8%b4-%d8%b5%d9%86%d8%a7%db%8c%d8%b9-%d8%b2%d9%85-6/ %a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%af%da%a9%d8%aa%d8%b1%db%8c-%d8%a7%d8%ab%d8%b1%d8%a8%d8%ae%d8%b4%db%8c-%d9%85%d8%af%d8%a7%d8%ae%d9%84%d8%a7%d8%aa-%d8%b1%d9%88%d8%a7%d9%86/ %a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d9%85%d9%87%d9%86%d8%af%d8%b3%db%8c-%d8%b5%d9%86%d8%a7%db%8c%d8%b9-%da%af%d8%b1%d8%a7%db%8c%d8%b4-%d8%b5%d9%86%d8%a7%db%8c%d8%b9-%d8%b7%d8%b1-2/%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%b1%d8%b4%d8%aa%d9%87-%d8%b2%d8%a8%d8%a7%d9%86-%d8%a7%d9%86%da%af%d9%84%db%8c%d8%b3%db%8cinvestigation-on-rheological-behaviour-of-dually-mo/%a7%db%8c%d8%a7%d9%86-%d9http://zusa.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d9%85%d8%b7%d8%a7%d9%84%d8%b9%d9%87-%d9%87%db%8c%d8%b3%d8%aa%d9%88%d9%85%d9%88/%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%b1%d8%b4%d8%aa%d9%87-%d8%b2%db%8c%d8%b3%d8%aa-%d8%b4%d9%86%d8%a7%d8%b3%db%8c-%d8%a7%d8%b1%d8%b2%db%8c%d8%a7%d8%a8-2/%a7%db%8c%d8%a7%d9%86-%d9http://zusa.ir/%d8%af%d8%a7%d9http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-40/%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%a8%d8%b1%d8%b1%d8%b3%db%8c-%d8%b9%d9%88%d8%a7%d9%85%d9%84-%d8%aa%d8%a7%d8%ab/%86%d8%a7%d9%85%d9%87-%d8http://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-91/%a7%d8%b1%d8%b4%d8%af-%d8%a8%d8%b1%d8%b1%d8%b3%d9%8a-%d8%aa%d8%b7%d8%a8%d9%8a%d9%82%d9%8a-%d9%85%d8%b3%d8%a6%d9%88%d9%84%d9%8a%d8%aa-%d9%83-2/%b3%d8%a7%d9%8a%d9%8a-%da%af%d9%88%d9%86%d9%87%e2%80%8c%d9%87%d8%a7%d9%8ahttp://zusa.ir/%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d9%85%d9%87%d8%a7%d8%b1%d8%aa%d9%87%d8%a7%db%8c-%d8%b2%d9%86%d8%af%da%af%db%8c-%d8%af%d8%b1-%da%a9%d8%a7%d9%87%d8%b4-%da%af%d8%b1%d8%a7%db%8c/-%d8%ac%d9%86%d8%b3-lar-2/a7%d9%85%d9%84-%d8%a8-2/

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

فصل پنجم:نتیجه گیری.. 103

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

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

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

– مقدمه