مقاله حل مدل مسأله مسیریابی وسائط نقلیه در حالت باز دو هدفه در محیط رقابتی

بخشی از مقاله

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

.1 مقدمه

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

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

.2 مرور ادبیات

مدل مسیر یابی وسائط نقلیه در حالت باز براي اولین بار توسط اسکراچ [1] بدون ارائه هیچ راه حلی مطرح شد. کائو و همکاران [2] مدل مسیریابی وسائط نقلیه در حالت باز را با هدف کمینه کردن هزینه و با فازي در نظر گرفتن تقاضاي مشتریان ارائه دادند. در ادامه رپوسیس و همکاران [3] یک مسئله مسیریابی وسائط نقلیه با پنجره زمانی را در نظر گرفتند که هدف از آن بهینه کردن هزینه حمل و نقل بود.

از کاربرد هاي این بخش میتوان به سرویس مدارس اشاره نمود فو و همکاران [4] این مسأله را در نظر گرفتند. در این مسأله هر وسیله نقلیه بایستی تعداد از پیش مشخص شده دانش آموز را در بازههاي زمانی خاصی سوار نماید و در ایستگاه پایانی پیاده نماید؛ مسیر برگشت نیز به صورت عکس مسیر قبلی اتفاق میافتد. برایسی [5] یک مسأله مسیریابی وسائط نقلیه با پنجره زمانی به همراه مکانیابی را گسترش داد. همچنین رپوسیس و همکاران [3] به کاربرد این نوع مدل سازي در توزیع مواد روانکار اشاره نمودند. به نظر میرسد کاربرد این مسأله براي مواد فاسد نشدنی رو به افزایش است.

این مسأله در مورد توزیع روزنامه نیز کاربرد دارد. راسل و همکاران [6] نیز از این مسأله براي مدل کردن حمل و نقل در صنعت روزنامه نگاري استفاده نمودند. تابع هدف در این مسأله با مسأله مسیریابی وسائل نقلیه سنتی متفاوت است. در این نوع مسأله تابع هدف اصلی مسأله کاهش ناوگان حمل و نقل است و تابع هدف دوم کاهش هزینههاي سفر است. ثابت شده است که مسأله مسیریابی وسائط نقلیه یک مسأله NP-Hard است [7] و استفاده از روش هاي دقیق درمورد مسائل با ابعاد به نسبت بزرگ نمیتواند توجیهپذیر باشد و با افزایش ابعاد مسأله بایستی از الگوریتم هاي فراابتکاري استفاده گردد.

.3 تعریف مسأله

در فضاي رقابتی فرض بر آن است که یک و یا بیش از یک رقیب در مناطق جغرافیایی تحت پوشش شرکت توزیع در حال فعالیت هستند و محصولات شرکتهاي رقیب براي کالاي شرکت مورد نظر کالاي جایگزین به حساب میآیند. در این محیط زمان سرویسدهی به مشتري داراي اهمیت فراوانی است به این صورت که اگر زودتر از رقبا سرویس به مشتري شروع گردد سود مناسبی عاید شرکت توزیع میگردد این سود را میتوان به دو دسته تقسیم نمود:

.1 دسته اول ناشی از فروش بیشتر محصولات است. این میزان بستگی به نشان تجاري محصول، منطقه جغرافیایی که توزیع در آن در حال انجام است، نشان تجاري رقیب و نحوه فروش دارد.

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

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

.4 نتایج

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

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

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

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

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

.2 مروري بر ادبیات موضوعی تحقیق

.1.2 انواع گوناگون مسئله مکانیابی-تخصیص

براي شرح مسئله مکان یابی-تخصیص چند مشتري را در نظر بگیرید که هر یک داراي تقاضاي معینی است و قرار است که تقاضاي این مشتریان توسط چند خدمت دهنده تأمین شود.در حل این مسئله مواردي که براي تعیین جواب بهینه باید معلوم شود عبارتند از: تعداد خدمتدهندگان،ظرفیت هر خدمتدهنده ،محل استقرار هر خدمت دهنده ومقدار تقاضاي هر مشتري که توسط هر خدمتدهنده باید تأمین شود.

.2.2 کارهاي انجام شده

با توجه منابع ارایه شده، میتوان روشهاي حل براي مسئله مکانیابی- تخصیص در حالت ظرفیت محدود تسهیلات را به سه دسته تقسیم نمود:

-1روشهاي حل دقیق : [5]و[25]و[24]و[23] از منابع ، الگوریتمهاي دقیق براي حل این مدل استفاده کردهاند که در بیشتر آنها از الگوریتم انشعاب و تحدید استفاده شده است.

-2 روشهاي حل غیردقیق : این روشهاي حل شامل روشهاي ابتکاري میباشد کهمعمولاً جواب نزدیک به جواب بهینهي کلی میدهند اما تضمینی براي بهترین جواب را نمیدهند. موارد [1]و[19]و[6]و[27] از منابع ،از این دسته هستند.

-3 روش شبیه سازي :در مسائل احتمالی و فازي، با توجه به پیچیده شدن مسئله، براي حل مدل نیاز به شبیه سازي است که مقالات [13]و[27] و[17] از این روش استفاده کردهاند.در مدلهاي فازي ، از شبیه سازي فازي استفاده میکنیم.

.3 مدل مکانیابی-تخصیص پیشنهادي

فرضیات مدل:

.1  مسئله مکان یابی-تخصیص بر روي سطح قرار دارد و فضاي حل بهصورت پیوسته است.

.2  ظرفیت خدمتدهندهها محدود فرض میشود.

.3  مسئله از نوع مطلوب بوده و هدف آن کمینه کردن هزینه حمل و نقل براي تأمین تقاضا میباشد.

.4  تقاضاي مشتریانالزاماً برآورده نمی شود و وابسته به هزینه عدم تامین میباشد.