الگوریتم ژنتیک و نتایج محاسبات


Widget not in any sidebars

در مدل ارائه شده به دنبال خدمت دهی به تمامی مشتریان موجود در سیستم و همینطور مسیریابی وسایل حمل و نقل و تخصیص تیم‌های با ویژگی‌های منعطف به هر یک از مشتریان هستیم به طوری که هزینه‌های کل جابجایی، خدمت دهی و جریمه‌ها، حداقل شود.
برای تست مدل و حل دقیق آن از برنامه (CPLEX11) استفاده شده است. برای حل مسائل مختلف در اندازه‌های کوچک، نتایج حاصل از این برنامه مبنای مقایسه و نتیجهگیری قرار گرفته شده است. برای مسائل با اندازه بزرگ‌تر با توجه به زمان بر بودن برنامه‌های مبتنی بر روش‌های حل دقیق، از الگوریتم ژنتیک سود برده شده است.
1-4. جنبههای نوآوری و کاربردی تحقیق
در مدلهای مسائل کلاسیک مسیریابی وسایل حمل و نقل، عموما انتقال حجمی از کالا توسط وسیله نقلیه به عنوان خدمت نهایی در نظر گرفته میشود و وسیله نقلیه به عنوان خدمتدهنده عمل مینماید. در ادبیات موضوعی، تحقیقات اندکی مولفههای انسانی را چه در قالب رانندگان وسایل نقلیه و یا تیمهای کاری در نظر گرفتهاند. در این تحقیق، تیمهای کاری با تواناییهای گوناگون به عنوان عوامل خدمتدهی در نظر گرفته شدهاند که میتوانند خدمات مختلفی را در مدت زمانهای متفاوت ارائه نمایند. همچنین هر تیم یا وسیله نقلیه ممکن است توانایی لازم جهت ارائه خدمت به تعدادی از مشتریان را نداشته باشد. تابع هدف مدل ارائه شده نیز به گونهایی در نظر گرفته شده که بین هزینههای جابجایی، خدمتدهی و دیرکرد، تعادل به وجود آید.
کاربرد مساله طراحی شده را میتوان در حوزههایی که برنامهریزی همزمان ارائه خدمتها و جابجاییها پرداخته میشود، در نظر گرفت. از این دست موارد میتوان به حوزههای مدیریت تیمهای نصب و تعمیرات تجهیزات، مدیریت بحران، برنامهریزی تیمهای بیمارستانی، خدمات سالمندان درون شهری و غیره اشاره نمود.
1-5. محتویات تحقیق
در این فصل مقدمهای از بحث حمل و نقل و مساله مسیریابی وسایل حمل و نقل ارائه شد. سایر فصول پایاننامه به این شرح میباشند: فصل دوم به ادبیات موضوع پیرامون مسائل مرتبط با CMVRP میپردازد. در فصل سوم مسأله CMVRP مدل سازی شده و الگوریتم ژنتیک برای حل آن پیشنهاد شده است. درفصل چهارم نتایج محاسباتی و تحلیل حساسیت پارامترهای الگوریتم پیشنهادی مورد بررسی قرار می‌گیرد. و بالاخره در فصل پنجم نتیجهگیری کلی و ارایه پیشنهاد‌ها برای تحقیقات آتی بیان شده است.
فصل دوم
مرور ادبیات
2-1. مقدمه
یکی از بنیادی‌ترین و مشهور‌ترین مسائل در زمینه حمل و نقل مسأله فروشنده دوره گرد (TSP) میباشد.در مسأله فروشنده دوره گرد هدف یافتن یک دوره مسیر کامل (تور) برای یک فروشنده دوره گرد است که در آن تمامی شهر‌ها (مشتریان) با کمترین هزینه ممکن ملاقات شوند و فروشنده از هر کدام تنها و تنها یکبار عبور نماید، و سپس این تور در‌‌ همان شهر اولیه که سفر از آنجا آغاز شده بود پایان یابد. نمایی از مسأله فروشنده دوره گرد در شکل (2-1) نشان داده شده است.
شکل 2-1. نمایی از مسأله فروشنده دورهگرد TSP [2]
حال اگر همین مسأله را با چندین فروشنده در نظر بگیریم مسأله ما تبدیل به مسأله چندین فروشنده دوره گرد (MTSP) خواهد شد که در واقع چند فروشنده از یک شهر حرکت کرده و پس از ملاقات چندین شهر دوباره به همان شهر اولیه باز میگردند. در این حالت نیزهر کدام از شهرها باید فقط یکبار مورد ملاقات قرار گیرند. در شکل (2-2) نمایی از مسأله MTSP نشان داده می شود.
شکل 2-2. نمایی ساده از MTSP [2]
حال اگر پیچیدگیهای دنیای واقعی در نظر گرفته شود در عمل با مسائل گستردهتری مواجه هستیم که از آن جمله می‌توان به مسائل مسیریابی وسایل حمل و نقل VRP اشاره کنیم که در واقع تعمیم مسائل فروشنده دورهگرد TSP و مسأله چندگانه فروشنده دوره گرد MTSP میباشد با این تفاوت که در مساله مسیریابی وسایل حمل و نقل ما یک مبدأ مشخص داریم و برخلاف مسأله چندگانه فروشنده دوره گرد ظرفیت وسایل نقلیه بی نهایت نیست و همچنین در VRP مشتریان مشخص با میزان تقاضای مشخصی وجود دارد. در اینگونه مسائل هدف این است که تقاضای تمامی مشتریان تأمین شود و هزینه کل مسیر شامل هزینه وسایل و حمل و نقل کمینه شود. بنابر این توضیحات مشخص می‌شود که بنیان مساله مسیریابی وسایل حمل و نقل بر TSP و بطور دقیقتر بر MTSP استوار است. در شکل زیر نمایی از مسأله مسیریابی وسایل حمل و نقل نشان داده شده است. در این شکل q ها میزان تقاضای مشتریان را نشان می دهد.
شکل 2-3. نمایی ساده از مساله مسیریابی وسایل حمل و نقل VRP [2]
در ادبیات ثابت شده است که مسأله TSP مربوط به کلاس مسائل NP-HARD است و به این علت مسأله VRP نیز که تعمیمی از مسأله TSP می‌باشد نیز متعلق به همین کلاس مسائل می‌باشد [6]، از اینرو برای حل اینگونه مسائل از روش‌های ابتکاری و فرا ابتکاری بهره جسته می‌شود و تا کنون روش‌های زیادی برای حل اینگونه مسائل توسعه داده شده است.
2-2. مساله مسیریابی وسایل حمل و نقل VRP
مسأله مساله مسیریابی وسایل حمل و نقل به معنای یافتن مجموعه‌ای از مسیرهایی که توسط یک ناوگان حمل و نقل از وسایل نقلیه با ظرفیت مشخص و ثابت به منظور رساندن خدمات و یا کالا‌ها به دسته‌ای از مشتریان با میزان تقاضای مشخص با کمترین هزینه ممکن می‌باشد. در طول این مسیر‌ها مشتریان تنها و تنها یک بار ملاقات می‌شوند و تمام تقاضاهای آنها تنها توسط یک وسیله نقلیه دریافت میگردد. از سوی دیگر تمام مسیر‌ها از یک نقطه مشخص (مبدا بارگیری) آغاز می‌شوند و پس از آنکه وسیله نقلیه یک سلسله از مشتریان را ملاقات نمود به‌‌ همان نقطه اولیه باز می‌گردد و مسیر در همان مکان به پایان می‌یابد.
این گونه مسائل به طور کلی به عنوان مسائل میسریابی وسایل حمل و نقل (VRPs) یا مسائل برنامه ریزی وسایل حمل و نقل، شناخته شده‌اند. مدل‌ها و الگوریتم‌های معرفی شده برای حل مسائل برنامه ریزی و مسیریابی ارائه شده را، نه تنها برای استفاده در مسائل مربوط به پخش و جمع آوری کالا‌ها بلکه برای بسیاری از مسائل مختلف صنعت حمل و نقل در دنیای واقعی، نیز می‌توان استفاده نمود. به طورعمده مورد استفاده از این دست مسائل، به عنوان مثال، در جمع آوری زباله‌های خشک، پاکیزه سازی خیابان‌ها، مسیریابی اتوبوس مدرسه، سیستم‌های جابه جایی معلولین، مسیریابی فروشنده دوره گرد و واحد‌های نگهداری و تعمیرات، می‌باشد.
پخش کالا‌ها در برگیرنده خدمتدهی به دستهایی از مشتریان، در یک بازه زمانی داده شده، توسط دستهایی از وسایل حمل و نقل می‌شود که در یک یا چند مرکز قرار دارند و توسط دستهایی از رانندگان هدایت می‌شوند و جابجایی‌ها در یک شبکه مسیر مناسب انجام می‌شود. به طور خاص، یک حل مساله میسریابی وسایل حمل و نقل تعیین کننده دستهایی از مسیرهاست که هرکدام توسط یک واحد وسیله حمل و نقل انجام می‌شود و از مرکز مربوط به خودش شروع می‌شود و به آن پایان می‌پذیرد، به طوری که نیاز مشتریان برآورده شود، محدودیت‌های عملیاتی ارضا شود و هزینه‌های کلی حمل و نقل حداقل شود.
شبکه مسیری است که برای انتقال کالا‌ها استفاده می‌شود، معمولا به صورت یک گراف معرفی می‌شود که کمان‌های آن مسیر‌ها را نمایش می‌دهند. کمان‌ها بر اساس یک طرفه یا دو طرفه بودن به ترتیب به دو دسته مستقیم یا غیر مستقیم تقسیم می‌شوند. به هر کمان هزینهایی مربوط است که معمولا بر اساس طول مسیر یا زمان طی کردن آن مسیر بیان می‌شود که می‌تواند به نوع وسیله حمل و نقل یا دوره زمانی که در آن مسیر طی می‌شود، مربوط باشد.