محدودیت‌ها و شرایط جدیدی به مسأله اضافه گردید که باعث تنوع اینگونه مسائل گردید که به عنوان نمونه همان طور که در این تحقیق بیان شده است، تیمهای کاری با تواناییهای منعطف به عنوان عوامل خدمتدهی در نظر گرفته شده اند. همچنین محدودیتهای خدمتدهی به مشتریان بر روی تیمها و وسایل اعمال شده است که این موضوع بر پیچیدگی مساله مسیریابی وسایل حمل و نقل خواهد افزود.
1-3. اهدف تحقیق
در این تحقیق یک مدل ترکیبی نیروی انسانی- مسیریابی وسایل حمل و نقل ارائه شده است که به طور همزمان به کمینه سازی هزینه‌های تخصیص نیروهای انسانی در قالب تیم‌هایی با ویژگی‌های متفاوت و همینطور هزینه‌های مسیریابی و جابجایی وسایل حمل و نقل پرداخته شده است. هریک از مشتریان موجود در سیستم به ارائه خدمت مخصوص به خود نیاز دارند و برای هر یک از این مشتری‌ها موعد زمانی مشخصی وجود دارد که درصورتی که خدمت دهی بعد از این موعد زمانی انجام شود، جریمه ایی به صورت هزینه مخصوص برای هریک از مشتریان در نظر گرفته شده است. در ابتدا فرض می‌شود که تمامی وسایل حمل و نقل و انواع مختلف تیم‌ها با ویژگی‌های متفاوت و منعطف، در مرکز8 قرار دارند و از آنجا به مکان مشتریان منتقل میشوند.
در مدل ارائه شده به دنبال خدمت دهی به تمامی مشتریان موجود در سیستم و همینطور مسیریابی وسایل حمل و نقل و تخصیص تیم‌های با ویژگی‌های منعطف به هر یک از مشتریان هستیم به طوری که هزینه‌های کل جابجایی، خدمت دهی و جریمه‌ها، حداقل شود.
براي تست مدل و حل دقیق آن از برنامه (CPLEX11) استفاده شده است. برای حل مسائل مختلف در اندازه‌های کوچک، نتایج حاصل از این برنامه مبنای مقایسه و نتیجهگیری قرار گرفته شده است. برای مسائل با اندازه بزرگ‌تر با توجه به زمان بر بودن برنامه‌های مبتنی بر روش‌های حل دقیق، از الگوریتم ژنتیک سود برده شده است.
1-4. جنبههای نوآوری و کاربردی تحقیق
در مدلهای مسائل کلاسیک مسیریابی وسایل حمل و نقل، عموما انتقال حجمی از کالا توسط وسیله نقلیه به عنوان خدمت نهایی در نظر گرفته میشود و وسیله نقلیه به عنوان خدمتدهنده عمل مینماید. در ادبیات موضوعی، تحقیقات اندکی مولفههای انسانی را چه در قالب رانندگان وسایل نقلیه و یا تیمهای کاری در نظر گرفتهاند. در این تحقیق، تیمهای کاری با تواناییهای گوناگون به عنوان عوامل خدمتدهی در نظر گرفته شدهاند که میتوانند خدمات مختلفی را در مدت زمانهای متفاوت ارائه نمایند. همچنین هر تیم یا وسیله نقلیه ممکن است توانایی لازم جهت ارائه خدمت به تعدادی از مشتریان را نداشته باشد. تابع هدف مدل ارائه شده نیز به گونهایی در نظر گرفته شده که بین هزینههای جابجایی، خدمتدهی و دیرکرد، تعادل به وجود آید.
کاربرد مساله طراحی شده را میتوان در حوزههایی که برنامهریزی همزمان ارائه خدمتها و جابجاییها پرداخته میشود، در نظر گرفت. از این دست موارد میتوان به حوزههای مدیریت تیمهای نصب و تعمیرات تجهیزات، مدیریت بحران، برنامهریزی تیمهای بیمارستانی، خدمات سالمندان درون شهری و غیره اشاره نمود.
1-5. محتویات تحقیق
در این فصل مقدمهای از بحث حمل و نقل و مساله مسیریابی وسایل حمل و نقل ارائه شد. سایر فصول پایاننامه به این شرح میباشند: فصل دوم به ادبیات موضوع پیرامون مسائل مرتبط با CMVRP میپردازد. در فصل سوم مسأله CMVRP مدل سازی شده و الگوریتم ژنتیک برای حل آن پیشنهاد شده است. درفصل چهارم نتایج محاسباتی و تحلیل حساسیت پارامترهای الگوریتم پیشنهادی مورد بررسی قرار می‌گیرد. و بالاخره در فصل پنجم نتیجهگیری کلی و ارایه پیشنهاد‌ها برای تحقیقات آتی بیان شده است.
فصل دوم
مرور ادبیات
2-1. مقدمه
یکی از بنیادی‌ترین و مشهور‌ترین مسائل در زمینه حمل و نقل مسأله فروشنده دوره گرد (TSP) میباشد.در مسأله فروشنده دوره گرد هدف یافتن یک دوره مسیر کامل (تور) 9براي یک فروشنده دوره گرد است که در آن تمامی شهر‌ها (مشتریان) با کمترین هزینه ممکن ملاقات شوند و فروشنده از هر کدام تنها و تنها یکبار عبور نماید، و سپس این تور در‌‌ همان شهر اولیه که سفر از آنجا آغاز شده بود پایان یابد. نمایی از مسأله فروشنده دوره گرد در شکل (2-1) نشان داده شده است.
شکل 2-1. نمایی از مسأله فروشنده دورهگرد TSP [2]
حال اگر همین مسأله را با چندین فروشنده در نظر بگیریم مسأله ما تبدیل به مسأله چندین فروشنده دوره گرد10 (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) یا مسائل برنامه ریزی وسایل حمل و نقل، شناخته شده‌اند. مدل‌ها و الگوریتم‌های معرفی شده برای حل مسائل برنامه ریزی و مسیریابی ارائه شده را، نه تنها برای استفاده در مسائل مربوط به پخش و جمع آوری کالا‌ها بلکه برای بسیاری از مسائل مختلف صنعت حمل و نقل در دنیای واقعی، نیز می‌توان استفاده نمود. به طورعمده مورد استفاده از این دست مسائل، به عنوان مثال، در جمع آوری زباله‌های خشک، پاکیزه سازی خیابان‌ها، مسیریابی اتوبوس مدرسه، سیستم‌های جابه جایی معلولین، مسیریابی فروشنده دوره گرد و واحد‌های نگهداری و تعمیرات، می‌باشد.
پخش کالا‌ها در برگیرنده خدمتدهی به دستهایی از مشتریان، در یک بازه زمانی داده شده، توسط دستهایی از وسایل حمل و نقل می‌شود که در یک یا چند مرکز قرار دارند و توسط دستهایی از رانندگان هدایت می‌شوند و جابجایی‌ها در یک شبکه مسیر مناسب انجام می‌شود. به طور خاص، یک حل مساله میسریابی وسایل حمل و نقل تعیین کننده دستهایی از مسیرهاست که هرکدام توسط یک واحد وسیله حمل و نقل انجام می‌شود و از مرکز مربوط به خودش شروع می‌شود و به آن پایان می‌پذیرد، به طوری که نیاز مشتریان برآورده شود، محدودیت‌های عملیاتی ارضا شود و هزینه‌های کلی حمل و نقل حداقل شود.
شبکه مسیری است که برای انتقال کالا‌ها استفاده می‌شود، معمولا به صورت یک گراف معرفی می‌شود که کمان‌های آن مسیر‌ها را نمایش می‌دهند. کمان‌ها بر اساس یک طرفه یا دو طرفه بودن به ترتیب به دو دسته مستقیم یا غیر مستقیم تقسیم می‌شوند. به هر کمان هزینهایی مربوط است که معمولا بر اساس طول مسیر یا زمان طی کردن آن مسیر بیان می‌شود که می‌تواند به نوع وسیله حمل و نقل یا دوره زمانی که در آن مسیر طی می‌شود، مربوط باشد.
2-2-1. تاریخچه VRP
براي اولین بار مسأله مسیریابی وسایل حمل و نقل توسط دانتزیگ و رامسر11[7] بصورت فرمول ریاضی ارائه شد و براي حل آن از روش هاي دقیق سود جسته شد، در سال 1954 اولین مقاله در مورد موضوع VRP توسط دانتزیگ، فالکرسون12 [8] به ثبت رسید، این مقاله یک مسأله نسبتاٌ بزرگ TSP را مورد مطالعه قرار داده و براي مدل VRP ارایه شده یک روش حل صفر و یک پیشنهاد داد شد که توسط تعداد زیادي از مقالات پیرامون TSP مورد پیروي قرار گرفت.
در سال 1964 رایت و کلارك[9] مقالهاي ارایه دادند که مسأله TSP را با بیش از یک وسیله نقلیه در فرمولبندي مسأله به کار گرفتند، در نتیجه این مطالعه را میتوان به عنوان اولین مقاله در ادبیات VRP آنگونه که شناخته میشود، به حساب آورد. اولین مقالهایی که در خود عبارت (مسیریابی وسایل نقلیه) را یدك می کشد منسوب به گلدن، مگناتی و انگاین [10] می باشد. نسخههاي دیگر VRP در اوایل دهه ي 1970 پدیدار شدند که به عنوان نمونه میتوان به آثاري که در مقالات جندرئو و همکاران و اوسوالد و همکاران و غیره [13،11،12] آورده شده است اشاره کرد.
در طی سالهاي دهي 1990 تحقیقات در مورد VRP شتاب گرفت. عواملی چون قابلیت و در دسترس بودن ریز محاسبه گره‌ها، این توانایی را در اختیار محققین قرار داد که الگوریتم‌های جستجوی بیشتری را ارایه و توسعه دهند. طی این دوره متدهای فرا ابتکاری جهت حل کردن اینگونه مسائل و همینطور مسائل بهینه سازي پیچیده ي دیگر، به عنوان الگوریتمهاي جستجو معرفی شدند. جندرئو و همکاران [14]، کاربردهاي الگوریتمهاي فرا ابتکاري همچون شبیه سازی تبرید، الگوریتم ژنتیک، کلونی مورچگان و غیره را در حل مسائل مسیریابی وسایل نقلیه مورد مطالعه قرار دادند. از دیگر تحقیقات انجام شده در این زمینه می توان به آثار واسرمن13، عثمان و کلی14 ، عثمان و لاپورته15، دوریگو، مونیزو و کلونی16، آرتس و لنسترا17 ، گلوور و لاگونا [15] وعثمان و واسمن [16] اشاره نمود.
2-2-2. مشخصات کلی مساله مسیریابی وسایل حمل و نقل
– مشخصات کلی مشتریان:
نقاط موجود در شبکه مسیر که مکان مشتری در آن قرار دارد.
مقدار کالا (تقاضا) ، که می تواند چند نوع باشد ، و باید به مشتری تحویل داده شود و یا از آن تحویل گرفته شود.
دورههای روز (پنجره های زمانی) که در آنها میتوان به مشتری خدمتدهی کرد( برای مثال، به علت محدودیتهای ترافیکی و یا به این علت که در زمانهای خاصی مکان مشتری باز است).
زمان مورد نیاز برای تحویل گرفتن و یا تحویل دادن کالا به مشتری(به ترتیب، زمانهای بارگیری یا باردهی) ، که میتواند به نوع وسیله حمل و نقل مربوط باشد؛
زیرمجموعهایی از وسایل ممکن که میتوانند برای خدمتدهی ب

دسته‌ها: No category

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

background