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

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

هر چه مسأله در مقابل حالات مختلف تقاضا قابل انعطاف­تر باشد ضریب پایداری مسأله بیشتر خواهد بود.
تمامی زیربخش­های موجود در این قسمت، از Shanmugam et al. (2011) اقتباس شده است که با اندکی تغییر بر روی آن، برای روش پیشنهادی استفاده گردیده است.

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

فرمول VRPSD پیشنهادی
در این بخش، مدل ریاضیِ مسأله با هدف حداقل­کردن هزینه­ های متعارف VRP یعنی هزینه­ طی مسیر به­همراه هزینه­ بارگیری­مجدد و هزینه­ تقاضاهای سرویس داده نشده، بیان شده است. جواب مدلِ مطرح شده، مسیر حرکت وسیله­ نقلیه به سمت مشتریانی که دارای تقاضای نامعلوم هستند را مشخص می­ کند. فرمول VRPSDروش پیشنهادی و تمامی زیربخش­های این قسمت، با اندکی تغییر و با اقتباس از Shanmugam et al. (2011) نوشته شده ­اند.

فرمول ریاضی
VRPSD بر روی گراف کامل تعریف شده است، که درآن مجموعه ­ای از گره­ها (مشتریان) هستند که گره بیانگر انبار است.
مجموعـه­ای از کمان­های متصل به گره­ها است.
هزینه­ سفر (فاصله) بین گره­ها است.
از آنجایی که در Shanmugam et al. (2011) برای بدست آوردن فاصله بین گره­ها از روش اقلیدسی استفاده کرده است، در روش پیشنهادی نیز فاصله­ی بین گره­ها از روش اقلیدسی به صورت رابطه (۴-۱) محاسبه گردیده است.
(۴-۱)
یک وسیله­نقلیه با حداکثر ظرفیت کالا را از انبار به مشتریان با توجه به تقاضاهایشان تحویل می­دهد. حداکثر ظرفیت برای وسیله­نقلیه را برابر با ۱۵ واحد در نظر گرفته­ایم.
تقاضاهای مشتریان متغیرهای تصادفی هستند. تقاضای هر مشتری شناخته شده نیست تا هنگامی­که وسیله­نقلیه به محل مشتری برسد. هم­چنین فرض می­ شود که از ظرفیت وسیله­نقلیه تجاوز نمی­کند و از توزیع احتمال گسسته پیروی می­ کند؛ در روش پیشنهادی این مقدار از ۰ تا ۶ فرض شده است.
یک مسیر باید از انبار شروع و بعد از ملاقات تعدادی از مشتریان به انبار بازگردد. یک راه حل عملی برای VRPSD یک جایگشت از مشتریان است که با شروع و پایان در انبار به عنوان یک «مسیر پیش ­بینی شده» نامیده می­ شود. وسیله­نقلیه، مشتریان را به ترتیب مسیر پیش ­بینی شده ملاقات می­ کند و با توجه به تقاضای مشتری و بار کنونی وسیله­نقلیه تصمیم می­گیرد که آیا برای ادامه به مشتری بعدی برود و یا این­که برای «بارگیری مجدد»^[۱۷۲] به انبار برگردد.

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

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

تعریف علائم و پارامترها
در Shanmugam et al. (2011) برای تعریف تابع هدف از یکسری پارامتر استفاده شده است که ما روش پیشنهادی را با آنها تطبیق داده­ایم.
شرح علائم و پارامترهای مورد استفاده در تعریف تابع هدف به شرح زیر می­باشند:
: مجموعه­ نقاط (گره­ها) تقاضا یا تعداد مشتریان است به­ طوری­که و انبار در گره قرار گرفته است که همان محسوب می­ شود.
: مجموعه وسایل نقلیه در دسترس است به­ طوری­که است و تعداد کـل وسیله­ های­نقلیه در دسترس می­باشد که در مطالعه ما درنظر گرفته شده است.
: ظرفیت وسیله­نقلیه
: بار فعلی وسیله­نقلیه
: حداکثر تقاضای مشتری
: تقاضای مشتری i اُم می­باشد که می­باشد و رابطه برقرار می­باشد.
: مسافت بین انبار تا مشتری i
: مسافت بین مشتری i تا انبار
: مسافت بین انبار تا مشتری j