فصل………………………………………………………………………………………………………….21

فصلسوم:مدلریاضیوالگوریتم های پیشنهادی

3-1- مقدمه………………………………………………………………………………………………………………………..23

3-2- مکانیابی- مسیریابی انبار عبوری……………………………………………………………………………………23

3-3- فرضیات مسأله……………………………………………………………………………………………………………24

3-4- مدل پیشنهادی…………………………………………………………………………………………………………….25

3-4-1- مجموعه ها و اندیس ها…………………………………………………………………………………………..25

3-4-2- پارامتر های ورودی…………………………………………………………………………………………………25

3-4-4- متغیرهای تصمیم…………………………………………………………………………………………………….26

3-4-5- تابع هدف و محدودیتها……………………………………………………………………………………………27

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

3-8- پیچیدگی مسأله…………………………………………………………………………………………………………..34

3-9- بر الگوریتم ژنتیک…………………………………………………………………………………………….35

3-9-1- مقدمه…………………………………………………………………………………………………………………….35

3-9-2- مکانیزم الگوریتم ژنتیک……………………………………………………………………………………………36

3-9-3- عملگرهای الگوریتم ژنتیک………………………………………………………………………………………38

3-9-4- کد کردن………………………………………………………………………………………………………………..40

3-9-5- ایجاد جمعیت اولیه………………………………………………………………………………………………….42

3-9-6- تابع برازندگی…………………………………………………………………………………………………………43

3-9-7- انتخاب…………………………………………………………………………………………………………………..43

3-9-8- ترکیب……………………………………………………………………………………………………………………46

3-9-9- احتمال ترکیب………………………………………………………………………………………………………..48

3-9-10- جهش………………………………………………………………………………………………………………….49

3-9-11- استراتژی برخورد با محدودیت ها…………………………………………………………………………..49

3-9-12- شرایط توقف الگوریتم…………………………………………………………………………………………..51

3-10- هوش ازدحامی(SI)…………………………………………………………………………………………………..51

3-11- الگوریتم ازدحام ذرات (PSO)……………………………………………………………………………………53

3-11-1- مقدمه………………………………………………………………………………………………………………….53

3-11-2- مراحل تکامل الگوریتم………………………………………………………………………………………….55

3-11-2- مکانیزم الگوریتم ازدحام ذرات ……………………………………………………………………………..57

3-12- خلاصه فصل…………………………………………………………………………………………………………..59

فصلچهارم:روشحلوتجزیهوتحلیلمحاسباتی

4-1-مقدمه………………………………………………………………………………………………………………………..61

4-2-تشریح ساختار GA بکار گرفته شده………………………………………………………………………………61

4-2-1-نحوه نمایش جواب­ها………………………………………………………………………………………………61

4-2-2-نحوه نمایش جواب الگوریتم ژنتیک پیشنهادی……………………………………………………………64

4-2-3- عملكرد كلی الگوریتم ژنتیك……………………………………………………………………………………68

4-2-4-نحوه تولید جمعیت اولیه………………………………………………………………………………………….69

4-2-5-ارزیابی جواب­ها………………………………………………………………………………………………………69

4-2-6-مکانیزم انتخاب………………………………………………………………………………………………………..69

4-2-7-عملگرهای ژنتیک……………………………………………………………………………………………………70

4-2-7-1-عملگرهای تقاطعی……………………………………………………………………………………………….70

4-2-7-2-عملگرهای جهشی………………………………………………………………………………………………70

4-2-8-تکرار الگوریتم……………………………………………………………………………………………………….70

4-2-9-شرط توقف الگوریتم………………………………………………………………………………………………71

4- 3- تشریح ساختار الگوریتم ازدحام ذرات ارائه شده…………………………………………………………..71

4-3-1- نحوه نمایش ذرات………………………………………………………………………………………………….74

4-3-2- تولید جواب­های اولیه…………………………………………………………………………………………….74

4-3-3- محاسبه مقادیر شایستگی………………………………………………………………………………………..75

4-3-4- تکرار الگوریتم………………………………………………………………………………………………………75

4-3-5- شرط توقف الگوریتم……………………………………………………………………………………………..75

4-4- تولید مسئله نمونه……………………………………………………………………………………………………..76

4-5-ابعادمدل ریاضیپیشنهادی و نتایج محاسباتی لینگو……………………………………………………….77

4-6- مفروضات و پارامترهای الگوریتم­ها……………………………………………………………………………..79

4-7-بررسی همگرایی الگوریتم ارائه شده……………………………………………………………………………..80

4-8- مقایسه نتایج الگوریتم ژنتیک و الگوریتم ازدحام ذرات و لینگو………………………………………81

4-8-خلاصه فصل……………………………………………………………………………………………………………..85

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

5-1-نتیجه گیری……………………………………………………………………………………………………………..87

5-2-پیشنهادهای آتی………………………………………………………………………………………………………..88

منابع و مآخذ……………………………………………………………………………………………………………………90

فهرست جداول

جدول 2-1 : راهنمای استفاده از انبار عبوری…………………………………………………………………………..11

جدول 3-1 اطلاعات مکانهای کاندید انبار عبوری……………………………………………………………………31

جدول 3-2- تعداد ماشینهای موجود در هر انبار عبوری وظرفیت هر نوع وسیله نقلیه…………………31

جدول 3-3- حجم هر نوع کالا……………………………………………………………………………………………..31

جدول 3-4- ماتریس قابلیت حمل هر وسیله نقلیه بسته به نوع کالا……………………………………………31

جدول 3-5- ظرفیت هر تأمین کننده از هر نوع کالا…………………………………………………………………31

جدول 3-6- تقاضا هر مشتری از هر نوع کالا………………………………………………………………………….31

جدول 3-7- فاصله نقاط………………………………………………………………………………………………………32

جدول 3-8- هزینه حمل بین نقاط…………………………………………………………………………………………32

جدول 3-9- مقدار کالای بارگیری شده توسط وسایل نقلیه در تأمین کنندگان و انبارهای عبوری…34

جدول 3-9- مقدار کالای تخلیه شده توسط وسایل نقلیه در مشتریان و انبارهای عبوری……………..34

جدول 4-1. سطوح پارامترهای مسئله در سایز کوچک……………………………………………………………..76

جدول4-2- ابعاد مدل به ازای مقادیر مختلف و نتایج محاسباتی لینگو………………………………………..78

جدول 4-3-مقادیر پارامترهای الگوریتمGA……………………………………………………………………………79

جدول 4-4-مقادیر پارامترهای الگوریتمPSO………………………………………………………………………….79

جدول4-5-نماد های به کار رفته برای مقایسه الگوریتم ها………………………………………………………….81

جدول4-6- مقادیر به دست آمده از اجراهای متفاوت برای هر دو الگوریتم و لینگو…………………….82

جدول4-7-مقادیرRPDو متوسط زمان محاسبه………………………………………………………………………84

فهرست اشکال

شکل2-1- تصویر شماتیک از یک انبارعبوری………………………………………………………………………..9

شکل 2-2- کنترل مواد در نوعی از انبار عبوری……………………………………………………………………..9

شکل 2-3 : انبار عبوری تک مرحله ای………………………………………………………………………………..13

شکل 2-4 : انبار عبوری دو مرحله ای………………………………………………………………………………….13

شکل 3-1- نمایی از مسیر حرکت وسیله نقلیه………………………………………………………………………33

شکل3-2- دیاگرام بلوکی الگوریتم ژنتیک ساده……………………………………………………………………..40

شکل 3-3- نمایش ترکیب یک نقطه ای ………………………………………………………………………………47

شکل 3-4- نمایش ترکیب دو نقطه ای…………………………………………………………………………………47

شکل 3-5- نمایش وارونه سازی بیت…………………………………………………………………………………..49

شکل 3-6- نمایش تغییر ترتیب قرار گیری…………………………………………………………………………..49

شکل3-7- دیاگرام بلوکی الگوریتم ازدحام ذرات ساده……………………………………………………………..57

شکل4-1- فضای جواب و کدینگ مسأله……………………………………………………………………………..62

شکل4-2- ارتباط بین فضای کدینگ و جواب……………………………………………………………………….62

شکل4-3- نمونه نحوه پردازش 4 کار روی یک ماشین…………………………………………………………..63

شکل 4-4- کروموزوم مرحله اول………………………………………………………………………………………..64

شکل 4-5- کروموزوم مرحله دوم……………………………………………………………………………………….65

شکل 4-6-کروموزوم مرحله دوم در حالتی که انبار عبوری 1 برقرار نشود………………………………..65

شکل 4-7- کروموزوم مرحله سوم………………………………………………………………………………………66

شکل4-8- کروموزوم مرحله چهارم…………………………………………………………………………………….67

شکل 4-9- ساختار الگوریتم ژنتیک ساده……………………………………………………………………………..68

• VDM-SL 22

• شبکه های پتری 23

  • خصوصیات رفتاری 25

    • Reachability 26
    • Boundedness 26
    • Liveness 26
    • Reversibility 28
    • Coverability 28

  • زیر مجموعه های شبکه های پتری 29

    • State Machine (SM) 30
    • Marked Graph (MG) 30
    • Free-choice net (FC) 31
    • Extended Free-choice net (EFC) 31
    • Asymmetric choice net (AC) 31
  • قضایا و فرضیات 32

• مقایسه و جمع بندی 35

فصل سوم: بررسی معماری دیتا سنترها 38

• Microsoft Hyper-V 39

  • بررسی اجزاء معماری Hyper-V 42

    • APIC 43
    • Child Partition43
    • Hypercall43
    • Hypervisor43
    • IC 43
    • I/O stack44
    • Root Partition 44
    • VID44
    • VMBus44
    • VMMS 44
    • VMWP 44
    • VSC 45
    • VSP 45
    • WinHv45
    • WMI45
  • نقاط ضعف 46

• Xen 46

  • بررسی اجزاء معماری Xen 48

    • Xen Hypervisor 48
    • Domain 0 48
    • Domain U 49
    • Xenstored 50
  • ارتباطات مابین دامنه صفر و دامنه های U 50

• VMware ESXi 50

  • بررسی اجزاء معماری VMware ESX 52

    • VMkernel 52
    • File System 52
    • CIM 53
  • طراحی یک معماری برای دیتا سنتر 54

  • مختصری درباره vSphere 56

    • سرویس های زیر ساختی vSphere 58

    • سرویس های کاربردی vSphere 59

      • سرور VMware vCenter 59
      • Client ها 59
      • ESX 59
      • vCenter Server 59
      • VMFS 59
      • SMP 60
      • VCMS 60
      • VI Client 60
      • VMware VMotion 60
      • Storage VMotion 60
      • VMware HA 61
      • DRS 62
      • Consolidated Backup 63
      • vSphere SDK 63
      • Fault Tolerance 64
    • سرویس های توزیع شده در vSphare 64
    • معماری شبکه 64
    • معماری محل ذخیره سازی داده ها 66

    • معماری سرور مدیریت VirtualCenter 69

      • User Access Control 70
      • Core Service 71
    • جمع بندی 71

فصل چهارم: ارائه مدل فرمال برای دیتا سنتر و تحلیل آن 72

• تشریح دیتا سنتر نمونه 73

• ارائه مدلی از رفتار کلی دیتا سنتر 77

  • ارزیابی و تحلیل مدل فرمال 87

4.2.1.1. Liveness 87

4.2.1.2. Safeness 87

4.2.1.3. Reversibility 89

• بررسی لایه های پایینتر مدل فرمال 90

• بررسی نحوه کار سرویس HA 91

  • شرح سرویس VMware HA 91
  • ارائه مدل فرمال از نحوه کار سرویس HA 95
  • تحلیل و ارزیابی مدل 98

4.3.3.1. Liveness 99

4.3.3.2. Safeness 101

4.3.3.3. Reversibility 102

• بررسی نحوه کار سرویس Fault Tolerance 106

  • تشریح ساختار سرویس Fault Tolerance 106
  • ارائه مدل فرمال از نحوه کار سرویس Fault Tolerance 110
  • تحلیل و ارزیابی مدل 111

4.4.3.1. Liveness 112

4.4.3.2. Safeness 113

4.4.3.3. Reversibility 113

• بررسی نحوه کار سرویس VMotion 114

  • تشریح ساختار سرویس VMotion 114
  • ارائه مدل فرمال از نحوه کار سرویس VMotion 118
  • تحلیل و ارزیابی مدل 119

4.5.3.1. Liveness 120

4.5.3.2. Safeness 121

4.5.3.3. Reversibility 122

• بررسی ساختار داخلی ESX hypervisor 124

  • تشریح ساختار ESX 124
  • ارائه یک مدل فرمال از نحوه کار ESX 125
  • بررسی و تحلیل مدل 129

4.6.3.1. Liveness 129

4.6.3.2. Safeness 131

4.6.3.3. Reversibility 132

• تشریح ساختار سیستم ذخیره سازی در ESX 133

  • تشریح ساختار سیستم ذخیره سازی 133
  • ارائه یک مدل فرمال از نحوه کار سیستم ذخیره سازی در ESX 138
  • بررسی و تحلیل مدل 144

4.7.3.1. Liveness 144

4.7.3.2. Safeness 145

4.7.3.3. Reversibility 146

• معماری ساختار شبکه در ESX 148

  • تشریح ساختار شبکه 148
  • ارائه مدل فرمال برای ساختار شبکه در ESX 155
  • بررسی و تحلیل مدل 161

4.8.3.1. Reversibility 161

4.8.3.2. Liveness 163

4.8.3.3. Safeness 165

• معماری سوئیچ مجازی در ساختار شبکه 165

  • تحلیل ساختار سوئیچ مجازی 165
  • ارائه یک مدل فرمال برای سوئیچ مجازی 169
  • بررسی و تحلیل مدل 172

4.9.3.1. Liveness 172

4.9.3.2. Safeness 173

4.9.3.3. Reversibility 174

• جمع بندی 175

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

مراجع 180

پیوست: مجموعه کامل مدل های پتری طراحی شده در پایان نامه 186

چکیده به زبان انگلیسی 195

فهرست جدول ها

عنوان و شماره صفحه

جدول 2.1. خلاصه مقایسه ابزار توصیف فرمال 36

جدول 3.1. سیستم های عامل قابل پشتیبانی توسط Hyper-V R2 41

جدول 3.2. سیستم های عامل قابل پشتیبانی توسط Xen نسخه 3. 47

جدول 4.1. گزارهای فعال در وضعیت های M₀الی M₁₅از مدل پتری 4.30 164

جدول 5.1. خلاصه نتایج به دست آمده از تحلیل رفتار زیر سیستم ها و سرویس های VMware ESX 177

فهرست شکل ها

عنوان صفحه

شکل 1.1. نحوه قرارگیری لایه های نرم افزاری بر روی سرور 4

شکل 1.2. شمای کلی دیتا سنتر با معماری مجازی 5

شکل 2.1. مثال هایی از زبان های فرمال و تقسیم بندی آنها ]10[ 13

شکل 2.2. روال طراحی یک سیستم نمونه به کمک زبان های فرمال ]10[ 14

شکل 2.3. نقطه gate در جبر پروسه ها ]4[ 18

شکل 2.4. مدل تولید کننده- مصرف کننده به کمک LOTOS ]17[ 19

شکل 2.5. مثالی از مدل سازی یک پروتکل به کمک شبکه های پتری ]23[ 25

شکل 2.6. نمونه ای از شبکه پتری non-Live ]23[ 27

شکل 2.7. نشانه گزاری برای: a) مجموعه موقعیت های ورودی و خروجی برای t و b) مجموعه گزارهای ورودی و خروجی برای p ]23[ 30

شکل 2.8. مثال هایی از زیر مجموعه های شبکه های پتری ]23[ 32

شکل 2.9. یک شبکه پتری و گراف نشانه دار مربوط به آن ]23[ 33

شکل 3.1. معماری سطح بالای Hyper-V ]40[ 42

شکل 3.2. شمایی از معماری Xen ]51[ 47

شکل 3.3. نحوه سرویس دهی به ماشین میزبان توسط Qemu-DM ]51[ 49

شکل 3.4. شمایی از معماری VMware ESXi ]3[ 52

شکل 3.5. ساختار شماتیک مدیریت CIM ]3[ 54

شکل 3.6. مثالی از مفاهیم میزبان، کلاستر و مخزن منابع ]60[ 58

شکل 3.7. طرز کار سرویس HA ]61[ 62

شکل 3.8. شمایی از معماری شبکه در محیط مجازی ]60[ 65

شکل 3.9. شمایی از معماری ذخیره سازی ]60[ 66

شکل 3.10. طرز کار RDM ]60[ 68

شکل 3.11. شمایی از ساختار سرور مدیریت VirtualCenter ]60[ 70

شکل 4.1. زیر ساخت دیتا سنتر مجازی ]63[ 73

شکل 4.2. یک الگوی نمونه برای زیر ساخت دیتا فیزیکی سنتر ]60[ 75

شکل 4.3. ساختار شماتیک دیتا سنتر نمونه 76

شکل 4.4. مدل پتری طراحی شده برای دیتا سنتر نمونه 78

شکل 4.5. گراف پوشا برای مدل پتری شکل 4.4 88

شکل 4.6. نتیجه تحلیل فضای حالت به وسیله نرم افزار PIPE 89

شکل 4.7. مدل پتری نحوه کار سرویس HA 96

شکل 4.8. عضویت شبکه 4.7 در زیرکلاس های شبکه های پتری 100

شکل 4.9. گراف پوشای مدل 4.7 101

شکل 4.10. نتیجه تحلیل فضای حالت بر روی مدل 102

شکل 4.11. نحوه توزیع توکن در وضعیت S8 103

شکل 4.12. شبیه سازی شبکه پتری شکل 4.7 104

شکل 4.13. چندین نمونه از شبیه سازی اجرای شبکه پتری 105

شکل 4.14. مدل پتری نحوه کار سرویس Fault Tolerance 110

شکل 4.15. نحوه توزیع توکن ها در M₃و M₄ 112

شکل 4.16. گراف پوشای مدل پتری شکل 4.14 114

شکل 4.17 مدل پتری نحوه کار سرویس VMotion 118

شکل 4.18. گراف نشانه دار (G, ) مربوط به مدل 4.17 120

شکل 4.19. گراف پوشای مدل 4.17 123

شکل 4.20. مدل پتری طرز کار ESX 125

شکل 4.21. گراف جهت دار معادل شبکه پتری 4.20 130

شکل 4.22. گراف پوشای کدل پتری 4.20 132

شکل 4.23. نمای شماتیک مدل چند لایه ای سیستم ذخیره سازی در ESX ]63[ 134

شکل 4.24. مدل پتری ارائه شده از نحوه کار سیستم ذخیره سازی در ESX 139

شکل 4.25. گراف جهت دار متناظر با مدل پتری 4.24 144

شکل 4.26. گراف پوشای شبکه پتری 4.24 146

شکل 4.27. نرم افزار تحلیلگر گراف، در حال اجرای الگوریتم اول عمق 147

شکل 4.28. نحوه ارتباط کارت شبکه مجازی و سوئیچ مجازی ]62[ 149

شکل 4.29. شمای کلی از ساختار شبکه در سرور ESX 153

شکل 4.30. مدل پتری تهیه شده از ساختار شبکه در ESX 156

شکل 4.31. گراف پوشای مدل پتری شکل 4.30 162

شکل 4.32. جستجوی اول عمق گراف شکل 4.31 163

شکل 4.33 مدل فرمال از نحوه کار سوئیچ مجازی 170

شکل 4.34. گراف جهت دار متناظر با مدل پتری 4.33 173

شکل 4.35. گراف پوشای مدل پتری 4.33 174

فصل اول: مقدمه

1.1. بیان مسئله و ضرورت تحقیق

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

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

تعریف دیتا سنتر: مجموعه ای از سیستمهای پشتیبانی (از جمله زیر ساخت سخت افزاری passive، زیرساخت خنک کننده، زیر ساخت تامین انرژی، اطفاء حریق و غیره)، منابع پردازشی سخت افزاری شامل سرورها، تجهیزات زیرساخت شبکه، زیرساخت ذخیره سازی داده ها و زیرساخت نرم افزاری شامل ابزار یک پارچه سازی[2]، مجموعه ای از سیستم های عامل، مجموعه ای از نرم افزارهای کاربردی شامل سرویس ها، تعدادی پایگاه داده، مجموعه ای از ابزارهای امنیتی نرم افزاری و سخت افزاری و یک ساختار مدیریتی است. این سیستم به کمک خطوط پرسرعت به شبکه های خارجی (Intranet، Extranet یا اینترنت) متصل است ]1[.

با توجه به رشد نیازها و احتیاج کاربران به انعطاف پذیری و تحمل خطای بالا در این مراکز پردازشی، در سال های اخیر تکنولوژی مجازی سازی[3] به عنوان پاسخی به این نیازها و بهترین شیوه یکپارچه سازی ارائه شده و بسیار رشد کرده است. در حقیقت، این تکنولوژی به عنوان لایه مدیریت نرم افزاری و سیستم عاملی دیتا سنتر مورد استفاده قرار می گیرد. در ادامه به تشریح تکنولوژی مجازی سازی و نحوه استفاده از آن در این طرح خواهیم پرداخت.

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

معماری مجازی سازی، همه منابع پردازشی از جمله سرورها، منابع ذخیره سازی[4] و شبکه را به یک ساختار مجازی نگاشت می دهد. این زیر ساخت با گردآوری همه منابع و نمایش مجموعه ای ساده شده و یکپارچه از آنها، مدیر را در درک بهتر ساختار فنی دیتا سنتر و مدیریت و تغییر آن یاری می رساند. به کمک این ساختار می توان منابع توزیع شده در یک دیتا سنتر را به صورت مجموعه ای یکپارچه از ابزار مدیریت نمود. همچنین می توان از دیتا سنتر برای مصارف گوناگونی استفاده کرد بدون اینکه نگران گوناگونی سخت افزارها و نحوه اتصال آن ها به سیستم باشیم؛ ]2[ و ]3[.

از این تکنولوژی برای طراحیزیر ساخت نرم افزاریدیتا سنتر استفاده خواهد شد. با این توضیح که به جای نصب یک سیستم عامل بر روی هر دستگاه سرور، از یک نرم افزار مجازی سازی به نام Hypervisor استفاده می شود. این نرم افزار شبه سیستم عامل به مدیر سیستم اجازه می دهد که به تعداد دلخواه کامپیوتر مجازی[5] بر روی سرور مذکور راه اندازی کرده و سیستم عامل و سرویس های دلخواه را بر روی آن نصب نماید (شکل 1.1).

شکل 1.1. نحوه قرارگیری لایه های نرم افزاری بر روی سرور

با این ترکیب می توان امکانات بسیار زیادی از جمله قابلیت دسترسی دائمی به سرویس ها (HA)[6] و مقاوم سازی سرویس ها در مقابل خطا[7] که از ضروریات چنین دیتا سنتری می باشد را با کمترین هزینه میسر نمود. همچنین امکان انتقال این کامپیوترهای مجازی در حال کار از روی یک سرور به سرور دیگر را بدون تاخیر زمانی وجود دارد[8].

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

شکل 1.2. شمای کلی دیتا سنتر با معماری مجازی

 

با توجه به نیاز به این مراکز و پیچیدگی ذاتی آنها، ترسیم یک مدل فرمال از ماهیت یک دیتا سنتر، چه پیش از طراحی[9] و چه پس از آن[10]، می تواند در شناخت طرز کار و چگونگی فعالیت چنین مرکزی نقش به سزایی داشته باشد. از جمله این کاربردها می توان به تشخیص بن بست ها[11] و گلوگاه ها[12] قبل از طراحی و محک زدن[13] سیستم بعد از طراحی اشاره نمود. با در دست داشتن این مدل (تصویر فرمال) جریان کنترل در سیستم قابل رویت بوده و در نتیجه رفتار سیستم را می توان بررسی و پیش بینی نمود ]4[. البته باید توجه داشت که در سیستم های واقعی از جمله دیتا سنترها، به دست آوردن مدل جامع تقریبا غیر ممکن بوده و تنها می توان بخش هایی از سیستم را با نادیده گرفتن برخی از پارامترها مدل نمود. هرچقدر مدل به سیستم واقعی نزدیکتر باشد بررسی رفتار سیستم به کمک مدل حاصل دقیقتر و کاربردی تر خواهد بود. در بخش های بعدی با بررسی دقیقتر ماهیت مدل سازی فرمال، با انواع شیوه ها در این حوزه[14] بیشتر آشنا خواهیم شد.

به طور کلی متد های فرمال نوع خاصی از شیوه های بیان فرمال مسائل هستند که از آنها برای تشریح و تبیین[15] سیستم های کامپیوتری و همچنین اثبات رفتار آنها[16] در سطح سخت افزار و نرم افزار استفاده می شود. هدف از توضیح رفتار یک سیستم به کمک روش های فرمال، بررسی رفتار و خصوصیات سیستم از جمله میزان حد پذیری[17]، بازگشت پذیری[18] و نیز پارامترهای انتزاعی تر مانند میزان ثبات[19] و پایداری[20] می باشد ]5[.

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

در این تحقیق، از زبان شبکه های پتری که ابزاری گرافیکی برای تشریح رفتار سیستم ها می باشد بهره گرفته شده است. این زبان در واقع نوع خاصی از ماشین های متناهی (اتوماتا) می باشد که امکان ترسیم جریان کنترل در سیستم را به صورت ساختار گراف و تعریف مجموعه ها فراهم می کند.

[1] Local Farm Servers

[2] Consolidation

[3] Virtualization technilogy

[4] Storage

[5] Virtual Machine

2-3-2 روشهای تجزیه و تحلیل وابستگی 10

2-3-3 روشهای دسته بندی و پیشگویی.. 10

2-3-4 درخت تصمیم. 11

2-3-5 شبکه عصبی.. 12

2-3-6 استدلال مبتنی بر حافظه. 12

2-3-7 ماشین های بردار پشتیبانی.. 13

2-3-8 روشهای خوشه بندی 13

2-3-9 روش K-Means 13

2-3-10 شبکه کوهنن.. 14

2-3-11 روش دو گام. 14

2-3-12 روشهای تجزیه و تحلیل نویز. 14

2-4 دسته های نامتعادل]صنیعی آباده 1391[. 15

2-4-1 راهکار مبتنی بر معیار 15

2-4-2 راهکار مبتنی بر نمونه برداری.. 15

2-5 پیشینه تحقیق.. 16

2-6 خلاصه فصل. 19

 

فصل سوم:

3-1 انتخاب نرم افزار 21

3-1-1 Rapidminer 21

3-1-2 مقایسه RapidMiner با سایر نرم افزار های مشابه. 21

3-2 داده ها 25

3-2-1 انتخاب داده 25

3-2-2 فیلدهای مجموعه داده صدور 25

3-2-3 کاهش ابعاد. 25

3-2-4 فیلدهای مجموعه داده خسارت.. 29

3-2-5 پاکسازی داده ها 29

3-2-6 رسیدگی به داده های از دست رفته. 29

3-2-7 کشف داده دور افتاده 30

3-2-8 انبوهش داده 32

3-2-9 ایجاد ویژگی دسته. 32

3-2-10 تبدیل داده 32

3-2-11 انتقال داده به محیط داده کاوی.. 32

3-2-12 انواع داده تعیین شده 33

3-2-13 عملیات انتخاب ویژگیهای موثرتر. 34

3-3 نتایج اعمال الگوریتم PCA و الگوریتم های وزن دهی.. 34

3-4 ویژگی های منتخب جهت استفاده در الگوریتمهای حساس به تعداد ویژگی.. 36

3-5 معیارهای ارزیابی الگوریتمهای دسته بندی.. 37

3-6 ماتریس درهم ریختگی.. 37

3-7 معیار AUC. 38

3-8 روشهای ارزیابی الگوریتم های دسته بندی.. 39

3-8-1 روش Holdout 39

3-8-2 روش Random Subsampling. 39

3-8-3 روش Cross-Validation. 40

3-8-4 روش Bootstrap. 40

3-9 الگوریتمهای دسته بندی.. 41

3-9-1 الگوریتم KNN.. 42

3-9-2 الگوریتم Naïve Bayes 42

3-9-3 الگوریتم Neural Network. 43

خطی.. 45

3-9-5 الگوریتم رگرسیون لجستیک.. 46

3-9-6 الگوریتم Meta Decision Tree. 47

3-9-7 الگوریتم درخت Wj48. 49

3-9-8 الگوریتم درخت Random forest 51

3-10 معیارهای ارزیابی الگوریتم های مبتنی بر قانون(کشف قوانین انجمنی) 54

3-10-1 الگوریتم FPgrowth. 55

3-10-2 الگوریتم Weka Apriori 55

3-11 معیارهای ارزیابی الگوریتمهای خوشه بندی.. 55

3-12 الگوریتم های خوشه بندی.. 57

3-12-1 الگوریتم K-Means 57

3-12-2 الگوریتم Kohonen. 60

3-12-3 الگوریتم دوگامی.. 64

 

فصل چهارم:

4-1 مقایسه نتایج. 69

4-2 الگوریتمهای دسته بندی.. 69

4-3 الگوریتم های دسته بندی درخت تصمیم. 70

4-4 الگوریتم های خوشه بندی.. 79

4-5 الگوریتم های قواعد تلازمی(مبتنی بر قانون) 81

4-6 پیشنهادات به شرکت های بیمه. 81

4-7 پیشنهادات جهت ادامه کار 83

منابع و مأخذ

فهرست منابع فارسی.. 84

فهرست منابع انگلیسی.. 85

 

 

 

فهرست جدول ها

 

عنوان صفحه

 

جدول شماره 3-1: نتایج رای گیری استفاده از نرم افزارهای داده کاوی………………………………… 24

جدول شماره 3-2: فیلدهای اولیه داده های صدور…………………………………………………………………….. 26

جدول شماره 3-3: فیلدهای نهایی داده های صدور…………………………………………………………………… 27

جدول شماره 3-4: فیلدهای حذف شده داده های صدور و علت حذف آنها………………………… 28

جدول 3-5: فیلدهای استخراج شده از داده های خسارت……………………………………………………….. 28

جدول 3-6: نتایج نمودار boxplot………………………………………………………………………………………………. 31

جدول 3-7: انواع داده استفاده شده…………………………………………………………………………………………….. 33

جدول 3-8: نتایج حاصل از اجتماع فیلدهای با بالاترین وزن در الگوریتمهای مختلف…………… 37

جدول 3-9: ماتریس در هم ریختگی رکوردهای تخمینی(Predicted Records)…………………… 38

جدول 3-10: قوانین استخراج شده توسط الگوریتم Fpgrowth……………………………………………… 55

جدول 3-11: قوانین استخراج شده توسط الگوریتم Weka Apriori……………………………………….. 55

جدول 3-12: تنظیمات پارامترهای الگوریتم K-Means……………………………………………………………. 57

اجرا برای 9 خوشه در الگوریتم K-Means………………………………………………………………………………….. 60

جدول 3-13: تنظیمات پارامترهای الگوریتم Kohonen……………………………………………………………. 64

جدول 3-14: تنظیمات پارامترهای الگوریتم دوگامی………………………………………………………………… 69

جدول 4-1: مقایسه الگوریتم های دسته بند………………………………………………………………………………. 70

جدول 4-2: مقایسه الگوریتم های دسته بند درخت تصمیم…………………………………………………….. 70

جدول 4-3: ماتریس آشفتگی قانون شماره 1…………………………………………………………………………….. 71

جدول 4-4: ماتریس آشفتگی قانون شماره 2…………………………………………………………………………….. 72

جدول 4-5: ماتریس آشفتگی قانون شماره 3 الف……………………………………………………………………… 72

جدول 4-6: ماتریس آشفتگی قانون شماره 3 ب……………………………………………………………………….. 72

جدول 4-7: ماتریس آشفتگی قانون شماره 3 ج………………………………………………………………………… 73

عنوان صفحه

 

جدول 4-8: ماتریس آشفتگی قانون شماره 3 د…………………………………………………………………………. 73

جدول 4-9: ماتریس آشفتگی قانون شماره 3 ه………………………………………………………………………….. 73

جدول 4-10: ماتریس آشفتگی قانون شماره 3 و………………………………………………………………………. 74

جدول 4-11: ماتریس آشفتگی قانون شماره 3 ز………………………………………………………………………. 76

جدول 4-12: ماتریس آشفتگی قانون شماره 4………………………………………………………………………….. 76

جدول 4-13: ماتریس آشفتگی قانون شماره 5………………………………………………………………………….. 77

جدول 4-14: ماتریس آشفتگی قانون شماره 6 الف…………………………………………………………………… 77

جدول 4-15: ماتریس آشفتگی قانون شماره 6 ب…………………………………………………………………….. 78

جدول 4-16: ماتریس آشفتگی قانون شماره7……………………………………………………………………………. 78

جدول 4-17: ماتریس آشفتگی قانون شماره8……………………………………………………………………………. 79

جدول 4-18: مقایسه الگوریتم های خوشه بندی………………………………………………………………………. 79

جدول 4-19: فیلدهای حاصل از الگوریتم های خوشه بندی……………………………………………………. 80

جدول 4-20: نتایج الگوریتم های FpGrowth, Weka Apriori……………………………………………….. 81

فهرست شکل ها

عنوان صفحه

 

شکل شماره3-1: داده از دست رفته فیلد” نوع بیمه ” پس از انتقال به محیط داده کاوی…… 33

شکل 3-2: نتایج الگوریتمPCA …………………………………………………………………………………………………. 34

شکل 3-3: نتایج الگوریتم SVM Weighting در ارزشدهی به ویژگی ها………………………………. 35

شکل 3-4: نتایج الگوریتم Weighting Deviation در ارزشدهی به ویژگی ها………………………. 35

شکل 3-5: نتایج الگوریتم Weighting Correlation در ارزشدهی به ویژگی ها……………………… 36

شکل 3-6: نمای کلی استفاده از روشهای ارزیابی……………………………………………………………………… 41

شکل 3-7: نمای کلی استفاده از یک مدل درون یک روش ارزیابی………………………………………… 42

شکل 3-8: نمودار AUC الگوریتم KNN…………………………………………………………………………………..42

شکل 3-9: نمودار AUC الگوریتم Naïve Bayes……………………………………………………………………..43

شکل 3-10: تبدیل ویژگی های غیر عددی به عدد در الگوریتم شبکه عصبی……………………… 44

شکل 3-11: نمودار AUC و ماتریس آشفتگی الگوریتم Neural Net…………………………………….44

شکل 3-12: تبدیل ویژگی های غیر عددی به عدد در الگوریتم SVM خطی……………………. 45

شکل 3-13 : نمودار AUC الگوریتمSVM Linear………………………………………………………………..46

شکل 3-14 : نمودار AUC الگوریتمرگرسیون لجستیک………………………………………………………. 47

شکل 3-15 : نمودارAUCالگوریتمMeta Decision Tree……………………………………………………. 48

شکل 3-16 : قسمتی از نمودارtree الگوریتم Meta Decision Tree………………………………………49

شکل 3-17 : نمودار radial الگوریتمMeta Decision Tree…………………………………………………..49

شکل 3–18:نمودار AUC الگوریتم Wj48………………………………………………………………………………..50

شکل 3-19 : نمودار tree الگوریتمWj48…………………………………………………………………………………51

شکل 3-20 : نمودار AUC الگوریتمRandom forest……………………………………………………………52

شکل 3-21 : نمودار تولید 20 درخت در الگوریتمRandom Forest…………………………………..53

شکل 3-22 : یک نمونه درخت تولید شده توسط الگوریتمRandom Forest……………………..53

عنوان صفحه

 

شکل 3-23 : رسیدن درصد خطا به صفر پس از 8مرتبه………………………………………………………….. 57

شکل 3-24 : Predictor Importance for K-Means………………………………………………………………58

شکل 3-25 : اندازه خوشه ها و نسبت کوچکترین خوشه به بزرگترین خوشه در الگوریتم

K-Means……………………………………………………………………………………………………………………………………….59

شکل 3-26 : کیفیت خوشه ها در الگوریتمMeans K-……………………………………………………………..60

شکل 3-27:Predictor Importance for Kohonen………………………………………………………………61

شکل 3-28 : اندازه خوشه ها و نسبت کوچکترین خوشه به بزرگترین خوشه در الگوریتم

Kohonen……………………………………………………………………………………………………………………………………….62

شکل 3-29 : کیفیت خوشه ها در الگوریتمMeans K-……………………………………………………………..63

شکل 3-30 : تعداد نرون های ورودی و خروجی در Kohonen………………………………………………..63

شکل 3-31 : Predictor Importance forدوگامی…………………………………………………………………. 64

شکل 3-32 : اندازه خوشه ها و نسبت کوچکترین خوشه به بزرگترین خوشه در

الگوریتم دوگامی…………………………………………………………………………………………………………………………….. 65

شکل 3-33 : کیفیت خوشه ها در الگوریتم دوگامی………………………………………………………………….. 66

شکل4-1: نمودارنسبت تخفیف عدم خسارت به خسارت…………………………………………………………… 75

مقدمه

شرکتهای تجاری و بازرگانی برای ادامه بقا و حفظ بازار همواره بر سود دهی و کاهش ضرر و زیان خود تاکید دارند از این رو روشهای جذب مشتری و همچنین تکنیکهای جلوگیری یا کاهش زیان در سرلوحه کاری این شرکتها قرار می گیرد.

از جمله شرکتهایی که بدلایل مختلف در معرض کاهش سود و یا افزایش زیان قرار می گیرندشرکتهای بیمهای می باشند. عواملی همچون بازاریابی، وفاداری مشتریان، نرخ حق بیمه، تبلیغات، تقلب، می تواند باعث جذب یا دفع مشتری گردد که در سود و زیان تاثیر مستقیم و غیر مستقیم دارد.

پرداخت خسارت نیز به عنوان تعهد شرکتهای بیمه منجر به کاهش سود و در بعضی موارد موجب زیان یک شرکت بیمه می شود. خسارت می تواند بدلایل مختلف رخ دهد و یا عملی دیگر به گونه ای خسارت جلوه داده شود که در واقع اینچنین نیست.

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

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

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

………………………………………………………………………………………………………………….. 7

1-6- فرضیات یا سوالات پژوهش …………………………………………………………………………………………………………. 8

ا-7- مدل غذایی دوغ …………………………………………………………………………………………………………………………….. 8

فصل دوم: بر مطالعات پیشین

2-1- بیماری های ناشی از غذا ……………………………………………………………………………………………………………. 10

2-2- عوامل بیماری زای مواد غذایی……………………………………………………………………………………………………… 11

2-3- باکتری مورد مطالعه ……………………………………………………………………………………………………………………. 11

2-3-1- باکتری اشریشیا کلای ……………………………………………………………………………………………………………. 11

2-3-2- خصوصیات بیماری و مكانیسم بیماری زایی باكتری …………………………………………………………………… 12

2-3-3- گروه EPEC ………………………………………………………………………………………………………………………. 12

2-٣-4- گروه ETEC ……………………………………………………………………………………………………………………….. 13

2-٣-5- گروه EIEC ………………………………………………………………………………………………………………………… 13

2-٣-6- گروه EHEC ……………………………………………………………………………………………………………………… 14

2-3-7- ارتباط باكتری با مواد غذایی و كنترل آن ………………………………………………………………………………….. 14

2-4- آویشن ……………………………………………………………………………………………………………………………………….. 16

2-5- اسانس ها چه هستند؟ ………………………………………………………………………………………………………………….. 18

2-5-1- نقش اسانس ها در داخل گیاهان ……………………………………………………………………………………………… 19

2-5-2- ترکیبات شیمیایی اسانس ها ……………………………………………………………………………………………………… 20

2-5-2-1-هیدروکربن………………………………………………………………………………………………………………………… 20

2-5-2-2- ترپن ها …………………………………………………………………………………………………………………………….. 21

2-5-2-2-1- مونو ترپن ها …………………………………………………………………………………………………………………. 21

2-5-2-2-2- سزکوئی ترپن ها …………………………………………………………………………………………………………… 22

2-5-2-2-3- دی ترپن ها ………………………………………………………………………………………………………………….. 22

2-5-2-3- الکل ها …………………………………………………………………………………………………………………………….. 22

2-5-2-4- آلدهیدها ……………………………………………………………………………………………………………………………. 23

2-5-2-5- اسیدها ………………………………………………………………………………………………………………………………. 23

2-5-2-6- استرها ………………………………………………………………………………………………………………………………. 23

2-5-2-7- کتون ها ……………………………………………………………………………………………………………………………. 23

2-5-2-8- لاکتون ها ………………………………………………………………………………………………………………………… 24

2-6- روش های استخراج اسانس ………………………………………………………………………………………………………… 25

• فشار سرد …………………………………………………………………………………………………………………………… 25

• استخراج با حلال ………………………………………………………………………………………………………………… 26

• اینفلوریج ……………………………………………………………………………………………………………………………. 26

• تقطیر آبی ………………………………………………………………………………………………………………………….. 26

• استخراج با CO2 و یا CO2 فوق بحرانی ………………………………………………………………………….. 27

• تقطیر توربینی …………………………………………………………………………………………………………………….. 27

• تقطیر با بخار ……………………………………………………………………………………………………………………… 28

• تاریخچه استفاده از اسانس ……………………………………………………………………………………………………. 30

• کاربرد های امروزی اسانس ها ………………………………………………………………………………………………. 30

• آزمایشات فعالیت ضد میکروبی در سیستم های غذایی ……………………………………………………………. 31

  • گوشت و فرآورده های آن …………………………………………………………………………………………………… 33
  • ماهی ………………………………………………………………………………………………………………………………… 34
  • محصولات شیری ………………………………………………………………………………………………………………. 34
  • سبزیجات ………………………………………………………………………………………………………………………….. 34
  • برنج ………………………………………………………………………………………………………………………………….. 35
  • میوه ها ……………………………………………………………………………………………………………………………… 35

• طرز عمل فعالیت ضد باکتری ……………………………………………………………………………………………….. 35

• حساسیت ارگانیسم های گرم مثبت و گرم منفی …………………………………………………………………….. 37

• سینرژیسم و آنتاگونیسم بین ترکیبات اسانس ………………………………………………………………………….. 38

• سینرژیسم و آنتاگونیسم بین ترکیبات اسانس و نگه دارنده های مواد غذایی………………………………… 39

فصل سوم: مواد و روش ها

3-۱- مقدمه …………………………………………………………………………………………………………………………………….. 42

3-2- نوع مطالعه ……………………………………………………………………………………………………………………………… 42

3-3- جمع آوری و آماده سازی گیاه …………………………………………………………………………………………………… 42

3-4- تهیه اسانس ……………………………………………………………………………………………………………………………. 42

3-5- تعیین ترکیبات شیمیایی اسانس گیاه کهلیک اوتی ………………………………………………………………………. 43

3-6- ارزیابی ترکیبات فنولیک …………………………………………………………………………………………………………… 44

3-7- میزان فلاونوییدها ……………………………………………………………………………………………………………………. 45

3-8- بررسی خواص آنتی اکسیدانی اسانس با روش DPPH ……………………………………………………………… 45

3-9- خصوصیات ضدمیکروبی و بهداشتی اسانس علیه باکتری اشرشیا…………………………………………………… 46

3-10- ارزیابیخصوصیات حسی……………………………………………………………………………………………………….. 47

3-11- آنالیز فیزیکوشیمیایی ……………………………………………………………………………………………………………… 48

3-11-1- Ph دوغ ……………………………………………………………………………………………………………………………. 48

3-11-2- اسیدیته قابل تیتراسیون …………………………………………………………………………………………………….. 48

3-11-3- مواد جامد کل …………………………………………………………………………………………………………………… 49

3-11-4- چربی دوغ ………………………………………………………………………………………………………………………… 49

3-12- متغییرها …………………………………………………………………………………………………………………………………. 50

فصل چهارم: یافته ها

4-1- نتایج آنالیز ترکیبات تشکیل دهنده ……………………………………………………………………………………………. 54

4-2- فعالیت آنتی اکسیدانی و ترکیبات فنولیک و فلاونوییدی اسانس …………………………………………………… 56

4-3- ارزیابی خصوصیت ضد میکروبی اسانس …………………………………………………………………………………….. 58

4-3-1- روش میکرودایلوشن ……………………………………………………………………………………………………………… 58

4-3-2- اثر ضد باکتریایی اسانس در مدل غذایی ……………………………………………………………………………… 58

4-4- ارزیابی حسی دوغ حاوی غلظت های مختلف اسانس ……………………………………………………………….. 59

4-5- بررسی خواص فیزیکو شیمیایی دوغ حاوی غلظت های مختلف اسانس ………………………………………. 60

 

فصل پنجم: بحث و نتیجه گیری

بحث ……………………………………………………………………………………………………………………………………………… 66

نتیجه گیری کلی …………………………………………………………………………………………………………………………….. 74

پیشنهادات ………………………………………………………………………………………………………………………………………. 75

منابع …………………………………………………………………………………………………………………………………………….. 76

چکیده انگلیسی ……………………………………………………………………………………………………………………………… 85

فهرست جداول

عنوانصفحه

جدول 2-1 روغن های بدست آمده از بخش های مختلف گیاهان ………………………………………………………………… 18

جدول 3-1 جدول متغییر ها …………………………………………………………………………………………………………………… 53

جدول 4-1 آنالیز ترکیبات اسانس کهلیک اوتی ………………………………………………………………………………………… 54

جدول 4-2 IC50 اسانس و کنترل ها ………………………………………………………………………………………………….. 56

جدول 4-3 ترکیبات فنولیک …………………………………………………………………………………………………………………… 57

جدول 4-4 ترکیبات فلاونوییدی …………………………………………………………………………………………………………….. 58

جدول 4-5 شمارش باکتری E.coli در نمونه های دوغ با غلظت های مختلف اسانس……………………………….. 59

جدول 4-6 میانگین داده های نمره دهی داورها به قابلیت پذیرش دوغ ……………………………………………………….60

جدول4-7 میانگین داده هایPh در دوغ با غلظت های مختلف اسانس در طول دوره 14روزه……………………… 61

جدول 4-8 میانگین داده های چربی در دوغ با غلظت های مختلف اسانس در طول دوره 14روزه…………………. 62

جدول 4-9 میانگین داده های مواد جامد کل در دوغ با غلظت های مختلف اسانس در طول دوره 14روزه…….. 63

جدول 4-10 میانگین داده های اسیدیته در دوغ با غلظت های مختلف اسانس در طول دوره 14روزه…………….. 64

نمودار 4-1 کروماتوگرام اسانس کهلیک اوتی …………………………………………………………………………………………… 55

نمودار 4-2 منحنی استاندارد اسید گالیک …………………………………………………………………………………………………. 57

نمودار 4-3 تغییرات Ph دوغ …………………………………………………………………………………………………………………. 61

نمودار 4-4 تغییرات مواد جامد کل دوغ …………………………………………………………………………………………………… 62

نمودار 4-5 تغییرات چربی دوغ ……………………………………………………………………………………………………………….. 63

نمودار4-6 تغییرات اسیدیته قابل تیتراسیون دوغ ………………………………………………………………………………………. 64

فهرست اشکال

عنوانصفحه

شکل 2-1 بوته گل دارکهلیک اوتی ………………………………………………………………………………………………………….. 16

شکل 2-2 گیاه بدون گل کهلیک اوتی ……………………………………………………………………………………………………… 17

شکل 2-3 بوته گیاه کهلیک اوتی …………………………………………………………………………………………………………….. 17

شکل 2-4 فرمول ساختاری ایزوپرن ………………………………………………………………………………………………………… 21

شکل 2-5 فرمول ساختاری بعضی از اجزای منتخب اسانس های روغنی ……………………………………………………….24

شکل 2-6 دیاگرام مربوط به تقطیر با بخار ……………………………………………………………………………………………….. 28

شکل 2-7 دیاگرام مربوط به تقطیر با بخار ……………………………………………………………………………………………….. 29

شکل 2-8 محل و مکانیسم فعالیت اسانس ها در سلول باکتری ………………………………………………………………….. 36

شکل 3-1 دستگاه GC-MS ……………………………………………………………………………………………………………….. 47

شکل 3-2 دستگاه اسپکتروفوتومتر ………………………………………………………………………………………………………….. 48

فهرست روابط ریاضی

فهرست صفحه

رابطه 3-1 درصد بازداری رادیکالی ……………………………………………………………………………………………………….. 49

رابطه 3-2 اسیدیته قابل تیتراسیون ……………………………………………………………………………………………………….. 52

…………………………………… 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 نشان داده شود که {V₀,V₁,V₂,… ,V_n}= V مجموعه ای از گره ها و {i : (V_i,V_j)} = A مجموعه ای از کمان های متصل کننده گره ها هستند. D نیز متناسب با فاصله بین این گره ها یا طول کمان هاست. نقطۀ نشانگر قرارگاه و تا مشتریان را نشان می دهد. که با هر کمان (i, j ) مرتبط است نشانگر مسافت یا زمان مسافرت و یا هزینه مسافرت است. برای هر مشتری Vi یک تقاضای qi و یک زمان خدمت در نظر گرفته شده است و هدف پیدا کردن حداقل هزینه ی مسیرهای حمل و نقل است که در آن :

• هر مشتری دقیقاً از یک وسیله ی نقلیه خدمت بگیرد