پایان نامه مسیریابی حمل و نقل کالا در زنجیره تامین در شرایط عدم قطعیت با استفاده از الگوریتم ژنتیک

پایان نامه برای دریافت درجه کارشناسی ارشد "MSC"

رشته: کامپیوتر

   گرایش: نرم افزار

چکیده

یکی از مسائلی که امروزه در زنجیره تأمین بسیار مطرح است و مطالعاتِ گسترده­ای در زمینه­ی آن انجام شده، مسأله مسیریابی وسایل نقلیه حامل بار برای تحویل کالا به متقاضیان می­باشد. برای حل این مسأله باید تابع هدفی را بهینه سازی کرد به نحوی که معیارهایی از قبیل مسافتِ طی شده، زمان سفر و تعداد وسایل نقلیه کمینه شود و تابع هدف حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد. این مسأله از نوع NP-hard است و اغلب برای حل آن­ از روش­های فرا­ابتکاری استفاده می­شود. در دنیای واقعی، وجود برخی عوامل باعث می­شود که مسأله­ی مسیریابی وسایل نقلیه، یک مسأله­ی غیر قطعی باشد. یک نوع عدم قطعیت در این مسأله، وقوع تقاضایِ متغیرِ مشتریان می­باشد؛ یعنی میزان تقاضای برخی مشتریان، نامشخص است و تنها هنگامی که وسیله نقلیه به محل مشتری برسد، تقاضای او مشخص می­شود. در این مقاله، روشی بر اساس الگوریتم ژنتیکِ مقاوم برای حل مسأله مسیریابی وسایل نقلیه­ی حامل بار با تقاضای متغیر ارائه شده است. در این روش، سعی بر یافتن جواب­های مقاوم برای این مسأله است که در مواجه شدن با تغییرات، بهینگی خود را حفظ کنند. ارزیابی­های انجام شده و مقایسه نتایج، کارایی روش پیشنهادی را نشان داده است.

واژه­های کلیدی: مسیریابی وسایل نقلیه، عدم قطعیت، تقاضای متغیر، الگوریتم ژنتیک مقاوم ، جواب­های پایدار.

مقدمه

در دهه­های اخیر، برآورده کردن نیازهای مشتریان که مهمترین جزء زنجیره تأمین می­باشند یکی از اهداف کلیدی مدیریت زنجیره تأمین به شمار می­رود. مسأله  مسیریابی وسایل­نقلیه (VRP)[1] مهم­ترین و پرهزینه­ترین بخش در لجستیک می­باشد. در مسأله  VRP، مجموعه­ای از وسایل­نقلیه وجود دارند که موظفند برای برآورده کردن تقاضاهای مشتریان، از انبار[2] به سمت آن­ها حرکت نمایند و پس از خدمت به تمامی مشتریان دوباره به انبار بازگردند. محدودیت­ها و مفروضاتی به این مسأله  اضافه شده است که منجر به پیدایش گونه­های متفاوت آن گردیده و کاربرد آن را در حوزه­های مختلف توسعه داده است.

در مسائل کاربردی دنیای واقعی نیازهای متفاوتی وجود دارد که برآورده کردن هر چه بیشتر آن­ها باعث پیچیده­تر شدن مسأله  می­گردد؛ به­عبارت دیگر به­حساب آوردن محدودیت­های موجود، حاکی از افزایش قابل توجه پیچیدگی در مسأله  VRP است. در واقع وجود همین محدودیت­ها است که باعث می­شود VRP به یک مسأله  غیرقطعی و متغیر تبدیل شود؛ به بیانی دیگر تغییر اهداف، ماهیت مسأله  و یا عوامل دیگر در طول زمان، که همان عدم قطعیت­های موجود در پیرامون مسأله  می­باشند ممکن است باعث تغییر در بهینگی این مسائل گردد. چنانچه ما این عدم قطعیت­ها را در فرآیند بهینه­سازی لحاظ کنیم باعث می­شود که مسأله  به یک مسأله  پویا تبدیل شود. اکنون برای حل چنین مسائل پویایی نیاز به جواب­هایی احساس می­شود که در برخورد با شرایط عدم قطعیت مسأله ، بهینگی خود را از دست ندهند؛ به این جواب­ها عنوان «جواب­های پایدار»[3] داده می­شود. جواب­های پایدار در واقع آن دسته از جواب­هایی است که در بدترین شرایط مسأله  باز هم بتوانند عملکرد خوبی را از خود نشان دهند. به­جای عنوان «پایدار» ممکن است عناوینی همچون «استوار» و «مقاوم» نیز به­کار برده شود.

در این پژوهش هدف ما ارائه­ی روشی برای حل VRP بر اساس الگوریتم ژنتیک (GA)[4] است که بتواند به جواب­های مقاومی برای این مسأله  دست یابد که در شرایط عدم قطعیت نیز بتواند همچنان بهینگی خود را حفظ نمایند.

همان­طور که پیش­تر اشاره کردیم، اضافه شدن یکسری از محدودیت­ها باعث ایجاد انواع مختلف VRP می­گردد؛ در مطالعه­ی ما افزوده شدن عدم قطعیت به مسأله  به صورت «نامعلوم بودن تقاضای مشتریان»، سبب ایجاد VRP با تقاضای تصادفی (VRPSD)[5] گردیده است. به VRPSD، مسأله  مسیریابی وسایل­نقلیه احتمالی (PVRP)[6] نیز گفته می­شود.

یکی از مهم­ترین عوامل ایجاد عدم قطعیت در VRP، عدم قطعیت در تقاضای مشتریان می­باشد که در این پژوهش نیز تمرکز ما بر روی عدم قطعیت مشتریان می­باشد. وقوع عدم قطعیت تقاضای مشتریان به این صورت است که میزان تقاضا نامشخص است تا هنگامی که وسیله نقلیه به محل مشتری برسد؛ چنانچه میزان تقاضا کمتر از بار موجود در وسیله نقلیه باشد مشتری سرویس می­گیرد و وسیله نقلیه برای خدمت، به مشتری بعدی می­رود. در غیر این­صورت برای مشتری کنونی یک هزینه منفی در نظر گرفته می­شود و وسیله نقلیه پس از رفتن به انبار و بارگیریِ مجدد به مشتریِ بعد از مشتری کنونی می­رود. تابع هدفِ روش پیشنهادی، علاوه بر هزینه­ی منفیِ ناشی از عدم سرویس به مشتریان، شامل هزینه­ی سفر بین مشتریان و همچنین انبار می­باشد.

به منظور ارزیابی روش پیشنهادی، آن را با روش­های «الگوریتم ژنتیک»، «بهینه سازی ازدحام ذرات» و «بهینه سازی ازدحام ذرات ترکیبی» مورد مقایسه قرار دادیم. نتایج بدست آمده، کارایی روش پیشنهادی را نسبت به روش­های دیگر نشان می­دهد.

ساختار این پایان­نامه به صورت زیر می­باشد:

فصل اول مسأله مسیریابی وسایل نقلیه در زنجیره تأمین را شرح می­دهد. فصل دوم عدم قطعیت در مسائل و مدیریت آن به کمک الگوریتم ژنتیک را ارائه می­دهد، فصل سوم مروری بر مسأله مسیریابی وسایل نقلیه­ی غیرقطعی دارد. فصل چهارم و پنجم به ترتیب، روش پیشنهادی و ارزیابی روش پیشنهادی را بیان می­کنند و در نهایت در فصل ششم نتیجه­گیری و پیشنهادهای آینده ذکر می­شود.فصل اول 

مسأله مسیریابی وسایل نقلیه در زنجیره تامین

مقدمه

در جهان صنعتی امروز که رقابتی تنگاتنگ میان شرکت­ها و تولیدکنندگان وجود دارد، تولید کالاهایی متنوع با کیفیت بالا مطابق خواسته­های مشتری و در عین حال، قیمت مناسب با توجه به توان خرید مشتری، تنها راه ماندن می­باشد و رقابت میان شرکت­ها در رقابت میان اجزای آنها است (ماکویی و افتخار، 1383). خواست مشتری بر کیفیت بالا و خدمت رسانی سریع، موجب افزایش فشارهایی شده است که قبلا وجود نداشته است. در نتیجه شرکت­ها بیش از این نمی­توانند به تنهایی از عهده تمامی کارها برآیند. فعالیت­هایی نظیر برنامه­ریزی عرضه و تقاضا، تهیه مواد، تولید، کنترل کیفیت، برنامه­ریزی محصول یا خدمت، نگهداری کالا و کنترل موجودی، بازاریابی، توزیع کالا و خدمات، تحویل و خدمت به مشتری که قبلا همگی در سطح شرکت انجام می­شد، اینک به سطح زنجیره تأمین انتقال یافته است. مسأله کلیدی در یک زنجیره تأمین، مدیریت و کنترل هماهنگ تمامی این فعالیت­ها است به­طوری که مشتریان بتوانند خدمت خود را با بالاترین سطح اطمینان، سرعت، کیفیت و هزینه مناسب دریافت کنند. فعالیت‌هاى حمل­و­­نقل، بخش نسبتا بزرگى از فعالیت‌هاى زنجیره تأمین را به خود اختصاص مى­دهد (بانک مقالات مدیریت بیمارستان، 1390؛ نوروزی، 1388). لجستیک و زنجیره تامین لفظی است که در چند سال اخیر در کشورمان و به ویژه این روزها تحت عنوان­هایی نظیر «مدیریت زنجیره تامین»، «لجستیک ناب» و «انجمن لجستیک و زنجیره تامین» بسیار شنیده می­شود (انجمن لجستیک ایران، 1392). در این فصل مطالبی راجع به «زنجیره تأمین» و همچنین نقش « مسأله مسیریابی وسایل نقلیه» در زنجیره تأمین ارائه می­شود.

زنجیره تأمین (SC)[1]

زنجیره تأمین شامل تمام فعالیت­هاى مرتبط با جریان و تبدیل کالاها از مرحله ماده خام (استخراج) تا تحویل به مصرف­کننده­ نهایى و نیز جریان­هاى اطلاعاتى مرتبط با آن­ها  می­باشد؛ این فعالیت­ها شامل منبع­یابی برای تأمین مواد اولیه، مدیریت سیستم­ها، مونتاژها، فروش و غیره می­باشد (نوروزی، 1388؛ ماکویی و افتخار، 1383).

 به ­عبارت دیگر یک زنجیره تأمین شامل دو یا چند سازمان است که از نظر قانونی از هم جدا بوده، اما به­وسیله­ی جریان­های مواد، اطلاعات و مالی به­هم مرتبط هستند.  این سازمان­ها می­توانند شرکت­هایی باشند که قطعات، اجزایِ تشکیل دهنده و محصولات نهایی، تولید می­کنند و حتی فراهم کنندگان خدمات تهیه و توزیع (لجستیک) و خود مشتری (نهایی) را نیز در بر گیرند (بانک مقالات مدیریت بیمارستان، 1390). در شکل (1-1) یک مدل زنجیره تأمین نشان داده شده است.

مدیریت زنجیره تأمین (SCM)[2]

مسأله کلیدی در یک زنجیره تأمین، مدیریت و کنترل هماهنگِ تمامی فعالیت­هایی نظیر توزیع، تحویل و خدمت به مشتری است. در SCM هدف این است که به گونه­ای جریان اطلاعات مالی و مواد با هم هماهنگ شوند که مشتریان بتوانند خدمت خود را با بالاترین سطح اطمینان، سرعت، کیفیت و هزینه مناسب دریافت کنند (بانک مقالات مدیریت بیمارستان، 1390؛ ماکویی و افتخار، 1383).

هدف زنجیره تأمین

هدف همه کسانی که در زنجیره تأمین فعالیت می­کنند، افزایش رقابت­پذیری است. دلیل آن این است که امروزه از دید مشتریِ نهایی، فقط یک واحد سازمانی به تنهایی، در مورد رقابت­پذیری محصولات یا خدماتش مسئول نیست. بنابراین رقابت از شرکت­های تکی به سمت زنجیره تأمین حرکت کرده است (بانک مقالات مدیریت بیمارستان، 1390).

عوامل یا محرک های زنجیره تامین[3]

در زنجیره تأمین چهار محرک اصلی، مطرح است (عبیری، غلامحسن، 1374) :

تسهیلات[4]

انبار[5]

اطلاعات[6]

حمل­و­نقل[7]

تسهیلات

تسهیلات، اشاره به تجهیزات و امکاناتی دارد که در اماکنی که محصول نگهداری (مثل فضای انبارش و انبارهای نگهداری کالا) و یا کالا تولید می­شود (مانند کارخانجاتی که مواد اولیه را گرفته­اند و روی آن­ها کارهایی انجام می­شود تا به محصول تبدیل شود) مورد استفاده قرار گرفته و به­کار می­روند (عبیری، غلامحسن، 1374).

انبار

نقش انبار در زنجیره تأمین، افزایش رضایتمندی تقاضا از طریق تضمین موجود بودن محصول است (عبیری، غلامحسن، 1374).

اطلاعات

در یک زنجیره تأمین، مراحل مختلفی از تأمین مواد اولیه، حمل، انبارداری و تولید گرفته تا توزیع و رساندن به مشتری، وجود دارد که این مراحل[8] مختلف از طریق «اطلاعات» به همدیگر مرتبط و هماهنگ می­شوند (عبیری، غلامحسن، 1374).

حمل­و­نقل

نقش حمل ونقل در زنجیره تأمین، انتقال محصول، چه مواد اولیه و چه محصول نیمه تمام و چه محصول تمام شده تا مرحله­ی توزیع و رساندن آن به دست مشتری می­باشد (عبیری، غلامحسن، 1374).

در این کار پژوهشی، تمرکز ما بر روی حمل­و­نقل می­باشد؛ به­همین دلیل به توضیح بیشتر این مورد می­پردازیم.

در رابطه با حمل­و­نقل مسائل زیادی مطرح است که یکی از آن­ها مسأله مسیریابی وسایل­نقلیه (VRP) می­باشد؛ در ادامه به شرح این مسأله می­پردازیم.

مسأله مسیریابی وسایل­نقلیه

مسأله فروشنده دوره­گرد (TSP)[9]  کوتاه­ترین مسیر را برای یک فروشنده دوره­گرد می­یابد به­طوری که از یک شهر شروع شود و سپس از تمامی سایر شهرها به یک ترتیب خاص عبور کند و سرانجام به شهر مقصد برگردد با این شرط که از هر کدام از شهرها فقط و فقط یک بار عبور کند. هدف این مسأله بهینه­سازی هزینه­ها می­باشد. مشخص است مسافتی که این فروشنده دوره­گرد می­پیماید بستگی به ترتیبی دارد که از شهرها عبور می­نماید. بنابراین هدف این مسأله ، یافتن یک ترتیب بهینه برای عبور از شهرها است، به گونه­ای که اهداف هزینه­ی در نظر گرفته شده، بهینه­سازی شود. با وجودی که درک این مسأله نیاز به مهارت­های ریاضی پیچیده ندارد و حتی بسیار ساده و قابل فهم است اما به عنوان یک « مسأله­ی بهینه­سازی ترکیبی سخت» از آن نام برده می شود چرا که حل آن بسیار دشوار است (رجبی و همکاران، 1389).

اولین بار چنین مسأله­ای در سال 1759 از سوی اولر مطرح شد که در آن زمان با نام « مسأله مسیر شوالیه­ها» ارائه شد. یک «مسیر شوالیه» عبارت بود از یک دور هامیلتونی در گرافی که نودهای آن 64 مربع صفحه شطرنج بودند که هر کدام با دو راس دیگر مجاور بودند و شوالیه هر بار تنها به یک مربع مجاور می توانست حرکت کند (رجبی و همکاران، 1389).

عبارت «فروشنده دوره­گرد» اولین بار در یک کتاب آلمانی در سال1932به کار گرفته شد که مولف آن خود، یک فروشنده دوره­گرد بود. اولین کسی که این مسأله را مورد مطالعه و بررسی قرار داد منجر[10] (1932) بود که با ارائه­ی یک الگوریتم شبیه به «نزدیک­ترین همسایگی» سعی در حل این مسأله داشت اما نتوانست به جواب بهینه­ای برسد. البته مطالعات اصولی روی TSP به عنوان یک مسأله بهینه­سازی ترکیبی از دنزیگ[11] و رامسر[12] (1959)آغاز شد (رجبی و همکاران، 1389).

گلدبرگ[13] (1989) با مطالعاتی که روی الگوریتم­های تکاملی انجام داد، آن­ها را به عنوان یکی از کاراترین الگوریتم­های بهینه­سازی معرفی نمود. در مورد TSP، جانسون[14] و همکاران (1979) تحقیق قدرتمندی روی جزئیات بهینه­سازی این مسأله ، با استفاده از الگوریتم­های مختلف انجام دادند و به این نتیجه رسیدند که الگوریتم­های تکاملی برای حل مسأله TSP  بهتر از سایر روش­ها به جواب می­رسند. به همین دلیل TSP یکی از مسائلی است که مطالعات بسیاری روی حل آن با استفاده از الگوریتم­های تکاملی ِگوناگون صورت گرفته است (رجبی و همکاران، 1389).

مسأله مسیریابی وسیله نقلیه(VRP)  یکی از چالش برانگیزترین مسائل بهینه­سازی ترکیبی و یک موضوع تحقیقاتی داغ در چند دهه گذشته است. برای اولین بار دنتزیگ و رامسر در سال 1959 این مسأله را در قالب «مسأله اعزام کامیون» بیان کردند. پس از آن، با توجه به کاربرد گسترده­ی مسأله VRP و اهمیت اقتصادی آن در کاهش هزینه­های عملیاتی در سیستم­های توزیع شده، مسأله VRP به یک حوزه­ی پژوهشی تبدیل شد (Benjamin, 2011; Zheng, 2012).

مسأله VRP اولیه از مجموعه­ای از وسایل­نقلیه، مشتریان و انبار تشکیل شده است. این مسأله را می­توان به­عنوان مسأله­ای از طراحی مسیرهایی با حداقل هزینه برای وسایل­نقلیه یکسان با ظرفیت­های شناخته شده تعریف کرد. این وسایل­نقلیه از یک انبار مرکزی به سوی مجموعه­ای از مشتریان که از لحاظ جغرافیایی پراکنده­اند و دارای تقاضاهای غیر منفی هستند، روانه می­شوند. هر مشتری دقیقا یک بار (به طور معمول توسط یک وسیله نقلیه) سرویس می­گیرد. تقاضای کل و طول مسیر نباید از ظرفیت کل تجاوز کند. این وسایل­نقلیه پس از این­که به مشتریانی که به آن­ها اختصاص داده شده­اند، خدمت کردند به انبار باز می­گردند (Benjamin, 2011).

نمونه­ای از حل مسأله VRP با یک انبار، 11 مشتری و 3 مسیر در شکل (1-2) نشان داده شده است.

انواع VRP

مسأله VRP اساسا توسعه TSP با چند فروشنده است. اما در مسأله VRP گروه­هایی از شهرها، از قبل مشخص نشده­اند. علاوه­بر این، فرض ظرفیت نامحدود TSP، با محدودیت ظرفیت وسیله نقلیه برطرف شده است (Zheng, 2012). همچنین NP-hard بودن آن توسط جانسون و گری[15] (1979) اثبات شده است (Johnson & Garey, 1979).

به منظور برآوردن سناریوهایVRP در زندگی واقعی، معمولا محدودیت­های زیادی در این مسأله نقش دارند، از قبیل: تعداد متعدد انبارها، انواع مختلف وسایل­نقلیه (همگن و ناهمگن)، انواع مختلف تقاضای مشتری (قطعی یا تصادفی)، محدودیت­های جاده (مسیر یک طرفه، مسیر ممنوع)، انواع عملیات (جمع­آوری، تحویل و ترکیبی) و غیره. به حساب آوردن این محدودیت­ها حاکی از افزایش قابل توجه پیچیدگی در مسأله VRP است؛ درنتیجه، انواعVRP  در مقالات معرفی شده­اند. مقاله­ای یک چارچوب طبقه­بندی ازVRP  را در سه دهه­ی گذشته ارائه می­دهد (Reisman, 2009 Eksioglu & Vural &). نمونه­های مختلف VRP و تکنیک­ها و راه­حل­های مورد استفاده برای حل VRP و همچنین بهترین راه حل­ها در سایت زیر به روز شده است (Benjamin, 2011).

http://neo.lcc.uma.es/radiaeb/WebVRP/index.html?/Problem_Instances/instances.html

کاربرد عملی VRP

بسیاری از مسائل عملی می­توانند به عنوانVRP  مدل­سازی شوند، مانند جمع­آوری زباله­های خانگی، مسأله اتوبوس مدرسه، کامیون­های تحویل بنزین، سیستم خدمات ایمیل، توزیع کالا و غیره.VRP  نقش مهمی در مسأله لجستیکی و توزیع است. تحقیقات عظیمی بر روی ارائه آن نقش داشته است (Zheng, 2012).

تعریف VRP کلاسیک

با توجه به تعریف لاپورت[16](b1992)،VRP  به شرح زیر است:

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

علاوه­بر این، فرض می­شود که  وسایل­نقلیه­ی در دسترس، مستقر در انبار هستند به­طوری که    . وقتی­که  گفته می­شود که  ثابت است. وقتی­که  و  گفته می­شود که  مستقل است.

VRP متشکل از طراحی مجموعه­ای از مسیرهای کم هزینه وسیله نقلیه است به گونه­ای که:

هر شهر در  دقیقا یک بار توسط دقیقا یک وسیله نقلیه بازدید می­شود.

 تمام مسیرهای وسیله نقلیه شروع و پایان آن­ها در انبار است.

محدودیت­های جانبی برآورده می­شوند.

VRP به شرح زیر فرمول بندی می­شود:

فرض کنید  یک متغیر باینری است که مقدار آن برابر با 1 است اگر و تنها اگر کمان  از  در راه حل بهینه ظاهر شود.

    (1-1)                                           

که در ارتباط با آن:

(1-2)                                            

(1-3)                                           

(1-4)                        

(1-5)                                            

محدودیت (1-4)، محدودیت از بین بردن زیرتورها می­باشد:   حد پایین برای تعداد وسایل­نقلیه مورد نیاز برای بازدید از همه رئوس  در راه حل بهینه است (Zheng, 2012).

طبقه بندی و توسعه VRP

مسائلی که نیاز به حل، در شرایط زندگی واقعی دارند معمولا بسیار پیچیده­تر ازVRP  کلاسیک هستند. نسخه­های مختلفی ازVRP  توسعه یافته، وجود دارد که چند نوع از آن­ها عبارتند از (Zheng, 2012):

VRP ظرفیت دار (CVRP)[17]

VRP همراه با پنجره زمانی (VRPTW)[18]

VRP  با گرفتن و تحویل دادن (VRPPD)[19]

VRP  با تقاضا تصادفی (VRPSD)

VRP ظرفیت دار(CVRP)

برخلاف VRP کلاسیک، مسیرها درCVRP  به عنوان یک سیکل ساده از گرافG  با حداقل هزینه تعریف می­شوند به­طوری­که با عبور از انبار، تقاضای کل رئوس بازدید شده، از ظرفیت وسیله نقلیه تجاوز نکند (Zheng, 2012). محتمل­ترین الگوریتم دقیق برای حل CVRP، شاخه و برش (بالدکسی[20] و همکاران، 2004؛ فیوکساوا[21] و همکاران، 2006؛ لسرد[22] و همکاران، 2004) است.

VRP همراه با پنجره زمانی(VRPTW)

VRPTW یک بَسط از VRP با محدودیت پنجره زمانی است. در VRPTW، علاوه بر محدودیت در VRP، محدودیت پنجره زمانی باید ارضا شود (Zheng, 2012).VRPTW یکی از مسائل مهم در تحقیق و عملیات و حمل­و­نقل به شمار می­آید که در آن وسایل­نقلیه­ی مستقر در یک انبار مرکزی، باید در یک بازه­ی زمانی تعیین شده از جانب هر مشتری، به آن­ها سرویس ارائه نمایند (قصیری و قنادپور، 1386). این محدودیت­های پنجره زمانی، زمان­هایی است که در آن یک مشتری در دسترس است تا توسط یک وسیله نقلیه، سرویس بگیرد (Benjamin, 2011).

دو نوع پنجره زمانی وجود دارد: پنجره زمانی سخت (VRPHTW)[23] و پنجره زمانی نرم (VRPSTW)[24]؛ همچنین می­توان این دو نوع را به صورت تلفیقی در نظر گرفت و با عنوان پنجره زمانی سخت و نرم (VRPHSTW)[25] از آن نام برد.

Abstract

One of the issues raised in today's supply chain is a very broad field of study and it is done, it is vehicle routing problem (VRP). The goal is to optimize the objective function of the number of parameters such as distance, travel time, number of vehicles to be minimized and objective function to be minimized and finally to maximize customer satisfaction. Because of these problems are NP-hard, so solving these meta-heuristic techniques are used. In the real world, there are a number of factors that makes the VRP problem is a problem of uncertain and variable.

In this study a method based on genetic algorithms for solving intractable problems is presented VRP uncertain. This method will try to answer the question that’s being resistant to change, to keep the optimality when faced with change, to keep the its optimality. Here, the uncertainty on the problem of changing demand of customers so that demand is uncertain when the vehicle reaches the customer premises. Evaluations conducted have shown the effectiveness of the proposed method.

Keywords: Vehicle Routing Problem, Demand Uncertainty, Uncertainty, Robust Solutions, Genetic Algorithm, NP-hard Problems