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

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

انواع VRP
مسأله VRP اساسا توسعه TSP با چند فروشنده است. اما در مسأله VRP گروه­هایی از شهرها، از قبل مشخص نشده­اند. علاوه­بر این، فرض ظرفیت نامحدود TSP، با محدودیت ظرفیت وسیله نقلیه برطرف شده است (Zheng, 2012). همچنین NP-hard بودن آن توسط جانسون و گری^[۲۱] (۱۹۷۹) اثبات شده است (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 کلاسیک
با توجه به تعریف لاپورت^[۲۲](b1992)،VRP به شرح زیر است:
فرض کنید یک گراف است که در آن مجموعه ­ای از رئوس هستند که نشان دهنده شهرها با انبار واقع در راس ۱ است و مجموعه ­ای از کمان­ها است. هر کمان مربوط به یک ماتریس فاصله غیر منفی است. در برخی شرایط، می ­تواند به عنوان هزینه سفر و یا به عنوان زمان سفر تفسیر شود. هنگامی که متقارن است، اغلب جایگزین کردن توسط مجموعه از لبه­های بدون جهت، راحت است.
علاوه­بر این، فرض می­ شود که وسایل­نقلیه­ی در دسترس، مستقر در انبار هستند به­ طوری که . وقتی­که گفته می­ شود که ثابت است. وقتی­که و گفته می­ شود که مستقل است.
VRP متشکل از طراحی مجموعه ­ای از مسیرهای کم هزینه وسیله نقلیه است به گونه ­ای که:
هر شهر در دقیقا یک بار توسط دقیقا یک وسیله نقلیه بازدید می­ شود.
تمام مسیرهای وسیله نقلیه شروع و پایان آن­ها در انبار است.
محدودیت­های جانبی برآورده می­شوند.
VRP به شرح زیر فرمول بندی می­ شود:
فرض کنید یک متغیر باینری است که مقدار آن برابر با ۱ است اگر و تنها اگر کمان از در راه حل بهینه ظاهر شود.
(۱-۱)
که در ارتباط با آن:
(۱-۲)
(۱-۳)
(۱-۴)
(۱-۵)
محدودیت (۱-۴)، محدودیت از بین بردن زیرتورها می­باشد: حد پایین برای تعداد وسایل­نقلیه مورد نیاز برای بازدید از همه رئوس در راه حل بهینه است (Zheng, 2012).

طبقه بندی و توسعه VRP
مسائلی که نیاز به حل، در شرایط زندگی واقعی دارند معمولا بسیار پیچیده­تر ازVRP کلاسیک هستند. نسخه­های مختلفی ازVRP توسعه یافته، وجود دارد که چند نوع از آن­ها عبارتند از (Zheng, 2012):
VRP ظرفیت دار (CVRP)^[23]
VRP همراه با پنجره زمانی (VRPTW)^[24]
VRP با گرفتن و تحویل دادن (VRPPD)^[25]
VRP با تقاضا تصادفی (VRPSD)

VRP ظرفیت دار(CVRP)
برخلاف VRP کلاسیک، مسیرها درCVRP به عنوان یک سیکل ساده از گرافG با حداقل هزینه تعریف می­شوند به­ طوری­کـه با عبور از انبار، تقاضای کـل رئوس بازدید شده، از ظرفیت وسیله نقلیه تجاوز نکند (Zheng, 2012). محتمل­ترین الگوریتم دقیق برای حل CVRP، شاخه و برش (بالدکسی^[۲۶] و همکاران، ۲۰۰۴؛ فیوکساوا^[۲۷] و همکاران، ۲۰۰۶؛ لسرد^[۲۸] و همکاران، ۲۰۰۴) است.

VRP همراه با پنجره زمانی(VRPTW)
VRPTW یک بَسط از VRP با محدودیت پنجره زمانی است. در VRPTW، علاوه بر محدودیت در VRP، محدودیت پنجره زمانی باید ارضا شود (Zheng, 2012).VRPTW یکی از مسائل مهم در تحقیق و عملیات و حمل­و­نقل به شمار می ­آید که در آن وسایل­نقلیه­ی مستقر در یک انبار مرکزی، باید در یک بازه­ی زمانی تعیین شده از جانب هر مشتری، به آن­ها سرویس ارائه نمایند (قصیری و قنادپور، ۱۳۸۶). این محدودیت­های پنجره زمانی، زمان­هایی است که در آن یک مشتری در دسترس است تا توسط یک وسیله نقلیه، سرویس بگیرد (Benjamin, 2011).
دو نوع پنجره زمانی وجود دارد: پنجره زمانی سخت (VRPHTW)^[29] و پنجره زمانی نرم (VRPSTW)^[30]؛ همچنین می­توان این دو نوع را به صورت تلفیقی در نظر گرفت و با عنوان پنجره زمانی سخت و نرم (VRPHSTW)^[31] از آن نام برد.
مدل پنجره زمانی سخت: در این نوع مدل، وسایل­نقلیه ملزم به انجام سرویس به یک مشتری در بازه­ی زمانی معین می­باشند. به­عبارت دیگر، هر ایستگاه (ایستگاه) یک بازه­ی زمانی سرویس به صورت خواهد داشت که زمان سرویس حتما باید در این بازه صورت گیرد.
مدل پنجره زمانی نرم: در حالت پنجره زمانی نرم، سرویس­دهی تا حد معینی خارج از بازه­ی تعیین شده نیز مجاز می­باشد. به این صورت که برای هر گره (مشتری) علاوه بر یک پنجره­ی زمانی معین یک بازه­ی زمانی سرویس دیگر نیز به نام تعریف می­ شود که بازه در داخل آن قرار می­گیرد و به سرویس­هایی که خارج از بازه انجام می­گیرد، جریمه تعلق خواهد گرفت.
مدل پنجره زمانی سخت و نرم: این حالت ترکیبی از دو حالت فوق می­باشد. بدین صورت که هر پنجره­ی زمانی شامل یک محدوده­ نرم و یک محدوده­ سخت می­باشد. محدوده­ نرم مشابه حالت نرم قابل نقض بوده ولی محدودیت سخت نباید نقض گردد.