حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده …

۲-۳- مسأله فروشنده دوره‌گرد
مسأله فروشنده دروه‌گرد (TSP)[9] یکی از بنیادی‌ترین و مشهورترین مسائل در زمینه حمل و نقل و مسأله مسیریابی می‌باشد. در مسأله فروشنده دوره‌گرد هدف یافتن یک دور، مسیر کامل(تور) برای یک فروشنده دوره‌گرد است که در آن تمامی شهرها (مشتریان) با کمترین هزینه ممکن ملاقات شوند و فروشنده از هر کدام تنها و تنها یک بار عبور نماید، سپس این تور در همان شهر اولیه که سفر از آنجا آغاز شده بود پایان یابد (تاث و همکاران،۲۰۰۲). نمایی از مسأله فروشنده دورهگرد در شکل ۲-۱ نشان داده شده است.
شکل ۲-۱: نمایی از مسأله فروشنده دوره گرد TSP(ظهره وند،۲۰۱۱)
حال اگر همین مسأله را با چند فروشنده در نظر بگیریم، مسأله ما تبدیل به مسأله چندین فروشنده دوره گرد (MTSP)[10] خواهد شد که در واقع چند فروشنده از یک شهر حرکت کرده و از ملاقات چندین شهر دوباره به همان شهر اولیه باز می‌گردند. در این حالت نیز هر کدام از شهرها باید فقط یکبار مورد ملاقات قرار گیرند (تاث و ویگو،۲۰۰۲). در شکل ۲-۲ نمایی از مسأله MTSP نشان داده می‌شود.
شکل ۲-۲: نمایی ساده از مسأله MTSP(ظهره وند،۲۰۱۱)
حال اگر پیچیدگی‌های دنیای واقعی در نظر گرفته شود در عمل با مسائل گسترده‌تری مواجه هستیم که از آن جمله می‌توان به مسائل مسیریابی وسایل نقلیه[۱۱]VRP اشاره کنیم که در واقع تعمیم مسائل فروشنده دوره گرد TSP، مسأله چندگانه فروشنده دوره گرد MTSP می‌باشد با این تفاوت که در مسأله مسیریابی وسایل نقلیه مایک مبدأ مشخص داریم و برخلاف مسأله چندگانه فروشنده دوره‌گرد ظرفیت وسایل نقلیه بی‌نهایت نیست و همچنین در VRP مشتریان مشخص با میزان تقاضای مشخصی وجود دارد. در اینگونه مسائل هدف این است که تقاضای تمامی مشتریان تأمین شود و هزینه کل مسیر شامل هزینه وسایل نقلیه کمینه شود. بنابراین توضیحات مشخص می‌شود که بنیان مسأله مسیریابی وسایل نقلیه TSP و به طور دقیق تر بر MTSP استوار است. در شکل زیر نمایی از مسأله مسیریابی وسایل نقلیه VRP نشان داده شده است در این شکل qها میزان تقاضای مشتریان بوده و فلش‌های مسیر خودروهای مختلفی را نشان می‌دهند که از انبار مرکزی حرکت کرده و پس از سرویس‌دهی به آن باز می‌گردند.
 
شکل ۲-۳: مسأله VRP(ظهره وند،۲۰۱۱)
در ادبیات ثابت شده است که مسأله TSP مربوط به کلاس مسائل NP-Hard است و به این علت مسأله VRP نیز که تعمیمی از مسأله TSP می‌باشد نیز متعلق به همین کلاس مسائل می باشد از اینرو برای حل اینگونه مسائل از روشهای ابتکاری و فرابتکاری بهره جسته می‌شود و تاکنون روش‌های زیادی برای حل اینگونه مسائل توسعه داده شده است.
۲-۴- مسأله مسیریابی وسایل نقلیه
موضوع مسیریابی وسیله‌نقلیه، یکی از مفاهیم آشنا در زمینه تحقیق در عملیات است که در دو دهه اخیر تلاش‌ها و به دنبال آن پیشرفت‌های بزرگی در این زمینه انجام گرفته است. مسأله مسیریابی وسایل نقلیه به مجموعه‌ای از مسائل اطلاق می‌شود که در آن ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند انبار به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی میپردازند و این امر را به نحوی انجام می‌دهند که هزینه‌های انجام این کار به حداقل برسد. در طول این مسیرها مشتریان تنها و تنها یک بار ملاقات می‌شوند و تمام تقاضاهای آنها تنها توسط یک وسیله نقلیه دریافت می‌گردد، هر وسیله دارای ظرفیت معینی است و از سویی تمام مسیرها از یک نقطه مشخص (مبدأ بارگیری) آغاز می‌شوند و پس از آنکه وسیله نقلیه یک سلسله از مشتریان را ملاقات نمود به همان نقطه اولیه باز می‌گردد و مسیر در همان مکان پایان می‌یابد. این‌گونه مسائل به طور کلی به عنوان مسائل مسیریابی وسایل نقلیه ( VRP) یا مسائل برنامه‌ریزی حمل‌ونقل، شناخته شده‌اند. مدل‌ها و الگوریتم‌های معرفی شده برای حل مسائل برنامه‌ریزی و مسیریابی ارائه شده را، نه تنها برای استفاده در مسائل مربوط به پخش و جمع‌آوری کالاها بلکه برای بسیاری از مسائل مختلف صنعت حمل‌ونقل در دنیای واقعی، نیز می‌توان استفاده نمود و به طور عمده مورد استفاده از این دست مسائل به عنوان مثال، در جمع‌آوری زباله‌های خشک، پاکیزه سازی خیابان‌ها، مسیریابی اتوبوس مدرسه، سیستم‌های جابه‌جایی معلولین، مسیریابی فروشنده دوره‌گرد و واحدهای نگهداری و تعمیرات می‌باشد. پخش کالاها در برگیرنده خدمت‌دهی به دسته‌ای از مشتریان، در یک بازه زمانی داده شده توسط دسته‌ایی از وسایل‌نقلیه می‌شود که در یک یا چند مرکز قرار دادند و توسط دسته‌ایی از رانندگان هدایت می‌شوند و جابجایی‌ها در یک شبکه مسیر مناسب انجام می‌شود. به طور خاص، یک حل مسأله مسیریابی وسایل نقلیه تعیین کننده دسته‌ای از مسیرهاست که هر کدام توسط یک واحد وسیله نقلیه انجام می‌شود و از مرکز مربوط به خودش شروع می‌شود و به آن پایان می‌پذیرد. به طوری که نیاز مشتریان برآورده شود، محدودیت‌های عملیاتی ارضا شود و هزینه‌های کلی حمل و نقل حداقل شود. شبکه مسیری است که برای انتقال کالاها استفاده می‌شود. معمولاً به صورت یک گراف معرفی می‌شود که کمانهای آن مسیرها را نمایش می‌دهند. کمانها بر اساس یک طرفه یا دو طرفه‌بودن به ترتیب به دو دسته مستقیم یا غیر‌مستقیم تقسیم می‌شوند به هر کمان هزینه‌ای مربوط است که معمولا بر اساس طول مسیر یا زمان طی‌کردن آن مسیر بیان می‌شود که می‌تواند به نوع وسیله نقلیه یا دوره زمانی که در آن مسیر طی می‌

برای دانلود فایل متن کامل پایان نامه به سایت 40y.ir مراجعه نمایید.

شود مربوط باشد.
۲-۵- اجزای مسأله VRP
اجزای مسأله VRP را در شکل معمول و شناخته شده آن می‌توان به مجموعه مشتریان، مجموعه وسیله نقلیه (ناوگان حمل و نقل)، و مسیرها تقسیم‌بندی کرد. هر یک از این اجزا دارای خصوصیاتی هستند که بعنوان فرضیات مسأله یا پارامترهای ورودی آن بایستی مورد توجه قرار گیرد. شرح این خصوصیات در زیر آورده شده است.
۲-۵-۱- خصوصیات کلی مشتریان
مکان هر مشتری: با گره در گراف شبکه مسیرها نشان داده می‌شود. مختصات مکان مشتری در صورت لزوم برای محاسبه فاصله-زمان و یا هزینه سفر بین گره‌ها استفاده می‌شود.
مقدار تقاضای مشتری: معرف مقدار کالایی است که باید به مشتری تحویل داده شود، یا از محل مشتری جمع‌آوری گردد.
زمان خدمت به مشتری : مدت زمانی است که وسیله نقلیه در محل مشتری برای ارائه خدمت به آن توقف می کند. زمان خدمت را می‌توان بصورت تابعی از تقاضای مشتری هم تعریف کرد.
مجموعه وسایل نقلیه قابل استفاده برای مشتری: زیر مجموعه ای از وسایل نقلیه است که امکان خدمت‌دهی به مشتری را دارند.
بازه زمانی سرویس: بازه زمانی است که خدمت‌دهی به مشتری بایستی انجام پذیرد.
۲-۵-۲- خصوصیات وسایل نقلیه
تعیین مبدا حرکت وسایل نقلیه: انبار محلی است که وسایل نقلیه از آنجا مسیر حرکت خود را آغاز کرده و در انتها نیز به انبار برمی‌گردند و امکان اینکه آیا در پایان به همان انبار یا به انبار دیگری بر‌می‌گردند.
ظرفیت وسیله نقلیه: بعنوان یکی از پارامترهای ورودی مسأله در محدودیت‌های مسأله مطرح می‌شود. ظرفیت خودروها می‌تواند یکسان یا متفاوت باشد (که به حداکثر وزن یا حجم یا تعداد دسته‌هایی که هر وسیله می‌تواند بارگیری نمایدمشخص می‌شود)
ابزار مورد نیاز برای عملیات بارگیری و تخلیه (بارگذاری) وسیله نقلیه
محدودیت‌های مربوط به میزان استفاده از خودرو (حداکثر زمان- مسافت استفاده)
زیر مجموعه‌ای از شبکه مسیرها که وسیله نقلیه می‌تواند آنها را طی می‌کند.
هزینه‌های مرتبط با استفاده از هر وسیله (بر اساس مسافت، واحد زمان، تعداد مسیرها،…)
۲-۵-۳- خصوصیات مسیرها
هزینه (زمان – مسافت) مربوط به سفر در طول مسیر از ابتدا تا انتها.
یکسان بودن یا نبودن هزینه سفر رفت و برگشت مسیرها.
بعضی از مواقع، ممکن است که به طور کامل تقاضای هر مشتری برآورده نشود، در این مواقع، می‌توان مقداری که باید تحویل داده یا گرفته شود، را کاهش داد و یا اینکه تقاضای زیر مجموعه‌ای از مشتریان را بی‌پاسخ گذاشت برای رویارویی با این مسأله، اولویت‌ها و یا جریمه‌های متفاوتی به کمبودهای کلی و جزئی هر مشتری، تخصیص می‌یابد.
شروع و پایان مسیرهای طی‌شده برای خدمت‌دهی به مشتریان می‌تواند در یک یا چند مرکز باشد هر مرکز با تعداد انواع وسایلی که به آن تخصیص داده شده و مقدار کل کالایی که به آن مربوط است شناخته می‌شود. در بعضی مسائل دنیای واقعی مشتریان از قبل بین مراکز تقسیم می‌شوند و وسایل حمل و نقل باید در انتهای مسیرهایشان به مرکز مربوط به خود باز گردند در این موارد مسأله مسیریابی وسایل نقلیه را می‌توان به چند مسأله مستقل تقسیم نمود که هر کدام به یک مرکز متفاوت مربوط است. حمل و نقل کالاها با به کارگیری دسته‌ایی از وسایل انجام می‌شود که ترکیب و اندازه‌شان می‌تواند ثابت باشد و یا اینکه بر‌اساس نیاز مشتریان تعیین شود.
۲-۵-۴- انواع توابع هدف در VRP
معمولی‌ترین و در عین حال مهم‌ترین هدف مسأله VRP حداقل‌کردن کل هزینه سیستم است. گاهی اوقات به جای حداقل‌کردن هزینه، از معادل‌های آن یعنی کل مسافت طی‌شده توسط وسایل نقلیه یا مجموع زمان استفاده از آنها در تابع هدف استفاده می‌شود. در عین حال در کاربردهای مختلف، اهداف دیگری نیز می‌توان برای مسأله در نظر گرفت. فهرست برخی اهداف مورد توجه برای مسأله در زیر آورده شده است:
حداقل‌کردن هزینه‌های مربوط به ناوگان و سرویس‌دهی شامل: هزینه مسافت کل طی‌شده توسط وسایل نقلیه، هزینه‌های ثابت و متغیر ناوگان مانند اجاره، حقوق، دستمزد، استهلاک،…
حداقل‌کردن تعداد وسایل نقلیه (یا رانندگان) مورد نیاز برای ارائه خدمت به همه‌ی مشتریان.
متعادل ساختن مسیر، از جهت زمان سفر و حجم بار وسیله نقلیه.
حداقل کردن خسارت دیر کرد یا زود کرد ارائه خدمت به مشتریان.
حداقل کردن زیان‌های ناشی از عدم برآورده شدن برخی خواسته‌های مشتریان.
حداقل کردن زیان ناشی از عدم استفاده از کل ظرفیت وسیله نقلیه.
حداقل کردن زیان‌های ناشی از اضافه‌کاری راننده – استفاده بیش از حد از وسیله نقلیه.
استفاده از حداقل تعداد وسایل نقلیه ممکن برای سرویس‌دهی به مشتریان.
توابع هدف می‌تواند ترکیب وزن داری از همه‌ی اهداف مذکور باشد.

مدیر سایت

Next Post

تخم نطفه دار بوقلمون

ج اکتبر 16 , 2020
امروزه در اغلب کشورها، بوقلمون را بصورت تجارتی و به تعداد زیادی نگه داری می کنند و تعداد معدودی از شرکتهای اصلاح نژادی، سویه های تجارتی مخصوص به خود را ارائه می دهند که از ضریب تبدیل و قدرت رشد بسیار بهتری نسبت به دیگر نژادها برخوردارند. در طریقه پرورش […]