بخشی از مقاله
چکیده:
امروزه بدلیل گسترش تقاضا از یک سو و افزایش رقابت بازار تجاري از سوي دیگر، لجستیک بهعنوان یک الزام، براي شرکتها مطرح میباشد. در این تحقیق مدل ریاضی مسئله مسیریابی بر مبناي رویکرد تحویل چندبخشی توسعه داده میشود. مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی، توسعهاي از مسئله مسیریابی وسایل نقلیه بوده که در آن امکان سرویسدهی به مشتریان با بیشتر از یک وسیله نقلیه میسر میباشد. از طرفی در مسائل مسیریابی با تحویل چندبخشی، تا کنون به مسئله حداکثرسازي تامین تقاضاي مشتري اشاره اي نگردیده است. این موضوع بسیار حائز اهمیت بوده و هرگونه عدم برآورد تقاضاي مشتري موجب از دست دادن فروش و سهم بازار خواهد شد. لذا پژوهش حاضر به دنبال یافتن مسیرهایی ست به گونه اي که حداکثر تقاضاي مشتریان برآورده شود. براي اعتبارسنجی مدل ریاضی پیشنهادي از روش دقیق گمز استفاده شده، که نتایج حاصل از حل مسائل تولیدي اعتبار مدل را اثبات میکند.
کلمات کلیدي: مسیریابی وسایل نقلیه؛ تحویل چندبخشی؛ حداکثرسازي تامین تقاضاي مشتري؛ حل دقیق.
.1 مقدمه
مسئله مسیریابی خودرو1 یک مسئله بهینهسازي ترکیبی و برنامهریزي گسسته است که هدف آن سرویس دهی به مشتریان با استفاده از ناوگانی از وسایل نقلیه است.VPRتوسط دانتزیگ و رامسر2 در سال 1959 ارائه شده است و یک مسئله مهم در زمینههاي حمل و نقل، توزیع و لجستیک میباشدVPR.[1] اغلب شامل انتقال کالاهاي واقع شده در یک ایستگاه مرکزي به سمت مشتریانی است که سفارش این کالاها را دادهاند. هدفVPR در حالت کلی کمینه کردن هزینه مسیر کل در انتقال کالا از ایستگاه مرکزي به سمت مشتریان است که در چند دهه اخیر با انجام پژوهش هاي بسیار در این زمینه اهداف دیگري همچون: ریسک، طول مسیر و زمان پاسخگویی و ماکزیمم کیفیت، رضایت مشتري، سود و پاسخگویی نیز مورد بررسی قرار گرفته است که اکثر محققان مینیمم هزینه و یا حداکثر دو تا از این اهداف را به عنوان اهداف مدل در نظر قرار می دهند.[2]
با توجه به دنیاي رقابتی کنونی، افزایش فروش و به طبع سهم بازار بسیار حائز اهمیت بوده، به گونه اي که هر گونه کاستی در تامین تقاضاي مشتریان موجب از دادن فروش و نیز بازار خواهد شد. مسئله اي که در این شرایط مطرح می گردد، این است که مسائل بهینه سازي مسیریابی وسایل نقلیه به دنبال یافتن مسیرهایی ست به گونه اي که حداکثر تقاضاي مشتریان برآورده شود که گاهی به دلیل عدم کفایت ظرفیت ماشین ها یا به دلیل هزینه بر بودن پیمودن مسیرها قادر به برآورده ساختن آنها نیست. لذا توسعه مدلی که بتواند همزمان علاوه بر کاهش هزینه هاي مسیریابی، عدم تامین تقاضاي مشتریان را حداقل سازد، بعنوان یک مهم باید در مسائل مسیریابی وسایل نقلیه مورد بررسی قرار گیرد.[3] از طرفی در مسئله مسیریابی وسایل نقلیه پایهاي فرض میشود که هر مشتري تنها توسط یک وسیله نقلیه و تنها در یک نوبت ملاقات میشود، اما این فرض همواره واقعی و درست نیست. در بسیاري از مواقع، تقاضاي برخی از مشتریان از ظرفیت وسایل نقلیه بیشتر میباشد. در چنین مواقعی میبایست این فرض برداشته شده و امکان سرویسدهی به بعضی از مشتریان را در بیشتر از یک مرحله فراهم نمود. مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی3، توسعهاي از مسئله مسیریابی وسایل نقلیه بوده که به این موضوع در آن پرداخته شده و امکان سرویسدهی به مشتریان با بیشتر از یک وسیله نقلیه میسر میباشد. این امر - هم از طریق کاهش مسافت کل طی شده و هم از طریق کاهش تعداد وسایل نقلیه بکار گرفته شده - باعث کاهش هزینهها میگردد.[4]
.2 پیشینه تحقیق
از سال 1950 تاکنون اهمیت رو به افزایش تحقیق در عملیات به طور عمده بر روي برنامه ریزي و زمانبندي تولید و توزیع بوده است. مسیریابی وسیله نقلیه و بارگیري کالاها در درون آنها، مبحثی محوري در حمل ونقل پشتیبانی و زنجیره ي تأمین است. مسئله مسیریابی وسایل نقلیه براي اولین بار توسط دانتزیگ و رامسر[5] در سال 1959 مطرح شد. این مسئله که حالت ترکیبی از دو مسئله فروشنده دورهگرد و بستهبندي صندوقها است، سعی در طراحی بهینه مجموعهاي از مسیرها براي ناوگان حملونقل به نحوي دارد که به تعداد معینی مشتري خدمترسانی شود و داراي محدودیتهاي جانبی مختلفی است.[6] ارجاعات بسیاري به این مقاله صورت گرفت. براي اولین بار که بیش از یک وسیله نقلیه در فرموله کردن مسأله در نظر گفته شد توسط کلارك و رایت [7]مورد مطالعه قرار گرفت که نتیجه ي آن را می توان اولین مطالعه ي شناخته شده در حوزه ي VRPمحسوب نمود.
مقاله اي که توسط گلدن و همکاران ارائه گردید، اولین مقاله اي بود که از عنوان مسیریابی وسیله نقلیه استفاده کرده بود. شایان ذکر است که نسخه هاي متنوع دیگري ازVRP در اوایل دهه ي 82 میلادي پدید آمدند. در ادامه به شرحی از پژوهش هاي صورت گرفته در این زمینه خواهیم پرداخت. مسئله مسیریابی با تحویل چندبخشی تقاضاي مشتریان با هدف عمده کاهش هزینه ها و نیز رفع مشکل محدودیت ظفیت ناوگان وسایل نقلیه براي نحستین بار توسط درور و ترودیو1 معرفی شد. در این نوع مسئله در صورتی که تقاضاي مشتریان بیش از ظرفیت وسایل نقلیه باشد، تحویل به چند بخش تقسیم شده و اصطلاحا برش یافته و در چند نوبت به مشتري تحویل داده خواهد شد.[8] در سال هاي اخیر تحقیقات بسیاري بر روي این دسته از مسائل مسیریابی وسایل نقلیه انجام پذیرفته که این نشان از اهمیت این موضوع دارد. سیلوا و همکاران[9]2 به بررسی مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی پرداخته و به حل آن با استفاده از الگوریتم جستجوي محلی نیز پرداختند. نویسندگان بر این باورند که تحویل چندبخشی توسعه اي از مسئله کلاسیک مسیریابی است که تأمین تقاضاي هر مشتري در یک نوبت سود بیشتري را نتیجه میدهد یا تحویل تقاضاي آنان در چند بخش منجر به افزایش سود میشود. ماهو و همکاران[10]3
به بررسی مسئله مسیریابی با تحویل چندبخشی و کاهش اندازه ناوگان پرداختند. اهدف بررسی شده در این مسئله عبارتند از: کاهش هزینه هاي مسیریابی و کاهش اندازه ناوگان. براي انجام این کار، این مسئله به دو زیر مسئله تقسیم شده است: یک جزء طراحی ناوگان و یک جزء مسیریابی. لذا در ابتدا، دو فرمولاسیون برنامه ریزي عدد صحیح مختلط براي هر مولفه تعریف شده است. نوآوري اصلی این مقاله، در مقایسه چهار مدل ریاضی براي مسئلهVRP توسعه یافته می باشد. قزوینی و همکاران [11] مسئله مکانیابی-مسیریابی سبز با انبارهاي چندگانه و تحویل چندبخشی و پنجره زمانی پرداختند. در این مطالعه، یک مدل خطی عدد صحیح ترکیبی براي مسئله مسیر سبز ارائه شده است. این یک مسئله چند گانه است که در آن مفروضات پنجره هاي زمان و تقسیم تحویل در نظر گرفته شده است. نتایج اجراي مدل نشان دهنده کارایی مدل است. بیانچسی و ایرنیچ[12]4 به مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی و پنجره زمانی پرداختند. محققان در این روش علاوه بر ملاقات بیش از یک مرحله مشتري، ناوگان را مقرر به سرویس دهی در بازه پنجره زمانی نموده و از این بعد داراي نوآوري می باشند. پس از فرمول بندي ریاضی آنها با استفاده از روش دقیق شاخه و کران به حل مدل پیشنهادي پرداختند. نتایج نشان دهنده کارایی و اعتبار مدل ریاضی پیشنهادي این محققین می باشد. آنوچ و همکاران[13]5 به بررسی مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی با محدودیت بارگیري دو بعدي پرداختند.
در این مقاله، مسئله توزیع گاز مایع مورد بررسی قرار گرفته است. به ویژه هدف این پژوهش قرار دادن بهینه سازي مسئله تحویل چندبخشی بطري هاي گاز به مجموعه اي از مشتریان با محدودیت هاي بارگیري است. این مسئله شامل بارگیري یک ناوگان ناهمگن وسایل نقلیه از طریق مجموعه اي از قفسه هایی با اندازه هاي مختلف و سپس ایجاد تحویل هاي قابل تقسیم است. مسئله مطرح شده در این مقاله به عنوان یک مسئله با تحویل تقسیم پذیر با بارگذاري هاي چندگانه با استفاده از ناوگان ناهمگن از وسایل نقلیه با پنجره زمانی و چند محصولی، ارائه شده است. پس از ارائه فرمول بندي ریاضی براي این مسئله، ابتدا با استفاده از نمونه هاي کوچک با استفاده از حل کننده CPLEX و با استفاده از آزمایش و بحث در مورد نتایج عددي، مدل پیشنهادي مورد بررسی قرار گرفته است که نتایج نشان دهنده کارایی مدل پیشنهادي می باشد. بیانچسی و همکاران[12]6 به بررسی موضوع جدیدي در حوزه مسیریابی وسایل نقلیه با تفکیک تقاضاي مشتري پرداختند. آنها به بررسی مسئله SDVRP در حالت پنجره زمانی و با محدودیت نارضایتی مشتري پرداختند.7 آنها در تحقیقشان به این نکته اشاره کردند که گرچه ملاقات مشتریان و سرویسدهی در بیش از یک مرحله برخلاف حالت کلاسیک موجب کاهش هزینهها میگردد اما از طرفی موجب نارضایتی مشتري نیز میشود، به این دلیل که مشتري در هر مرحله از سرویسدهی مجبور به قطع فعالیتهاي اصلیش و دریافت کالا از سرویسدهی دهنده میباشد. آنها در مقالهشان به تجزیه و تحلیل کامل نقاط قوت و ضعف استراتژي SDVRP پرداختند. در نهایت آنها به نتایج مفیدي در جهت کاهش نارضایتی مشتریان دست یافتند.
.3 بیان مسئله
براي ارائه مدل ریاضی مسئله دو هدفه مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی تقاضاي مشتریان با هدف کمینه سازي هزینه کل و حداکثر سازي تامین تقاضاي مشتري، از گراف G - ,A - استفاده می شود که در آن = {0,1,…,n} مجموعه گره و A ={ - i, j - | i, j ϵV and i ≠j} مجموعه یالهاي موجود در آن است. در این مسئله هر یک از گره ها مانند i، به جز گره صفر که نشان دهنده انبار است، نشان دهنده مشتري ها بوده و داراي مقدار تقاضاي می باشد. همچنین به هر کمان موجود در A فاصله متناظر شده است که در آن براي هر 0≤i≤n مقدار =0 است. از طرفی دیگر ناوگانی از K نوع وسیله یکسان در مبدا قرار گرفته است، به طوري که همه وسایل داراي ظرفیت یکسان بوده و ناوگان در نظر گرفته شده همگن میباشد. در مسئله مسیریابی وسایل نقلیه پایهاي فرض میشود که هر مشتري تنها توسط یک وسیله نقلیه و تنها در یک نوبت ملاقات میشود، اما این فرض همواره واقعی و درست نیست. در بسیاري از مواقع، تقاضاي برخی از مشتریان از ظرفیت وسایل نقلیه بیشتر میباشد.
در چنین مواقعی میبایست این فرض برداشته شده و امکان سرویسدهی به بعضی از مشتریان را در بیشتر از یک مرحله فراهم نمود. لذا این پژوهش که توسعه اي از مسئله مسیریابی وسایل نقلیه با تحویل چندبخشی بوده، به این موضوع در آن پرداخته شده و امکان سرویسدهی به مشتریان با بیشتر از یک وسیله نقلیه میسر میباشد. همان طور که بیان شد، یکی از نوآوري هاي این پژوهش، در نظرگرفتن دو تابع هدف به طور همزمان است. یکی کاهش هزینه هاي مسیریابی با در نظر گرفتن تحویل چندبخشی و دیگري حداکثرسازي تامین تقاضاي مشتري می باشد. کاهش هزینه طی کردن مسیرها در کنار برآوردن تقاضاي مشتریان بعنوان اصلی ترین هدف مسیریابی وسایل نقلیه به خوبی در مسائل مسیریابی با تحویل چندبخشی و لذا در این تحقیق نمود پیدا می کند. دلیل این امر آن است که با توجه به دنیاي رقابتی کنونی، افزایش فروش و به طبع سهم بازار بسیار حائز اهمیت بوده، به گونه اي که هر گونه کاستی در تامین تقاضاي مشتریان موجب از دادن فروش و نیز بازار خواهد شد.
مسئله اي که در این شرایط مطرح می گردد، این است که مسائل بهینه سازي مسیریابی وسایل نقلیه به دنبال یافتن مسیرهایی ست به گونه اي که حداکثر تقاضاي مشتریان برآورده شود که گاهی به دلیل عدم کفایت ظرفیت ماشین ها یا به دلیل هزینه بر بودن پیمودن مسیرها قادر به تحویل آن نیست. لذا توسعه مدلی که بتواند همزمان علاوه بر کاهش هزینه هاي مسیریابی، تامین تقاضاي مشتري را حداکثر سازد، بعنوان یک مهم باید در مسائل مسیریابی وسایل نقلیه مورد بررسی قرار گیرد.
.4 مدل ریاضی
در این بخش، ابتدا به معرفی پارامترهاي مدل پرداخته خواهد شد. سپس مدل ریاضی مسئله مورد نظر مطرح میگردد:
.1,4 مجموعه ها، پارامترها و متغیرهاي مدل
