مرکز تحقیقات مهندسی صنایع و کسب و کار​

مسأله مسیریابی وسیله نقلیه به انتقال محصول از یک دپو به مراکز مشتریان می پردازد که در دنیای واقعی بسیار پرکاربرد است. مسأله مسیریابی وسیله نقلیه نسخه توسعه یافته مسأله فروشنده دوره گرد می باشد. با در نظر گرفتن شبکه­ای از یک مجموعه از گره ها (V) و مجموعه‌ای از کمان‌های (E) متصل کننده این گره‌ها، TSP در واقع یافتن کوتاه ترین مسیری است که از هر گره دقیقاً یک بار می گذرد. وقتی M مسیر وجود دارد، این مسأله M-TSP نامیده می شود که در این مسأله یکی از گره ها دپو نامیده می شود و باید در تمام مسیرها وجود داشته باشد. اغلب ساختار نسبتاً ساده M-TSP برای توصیف فرضیات مسائل دنیای واقعی کافی نیست. به منظور پرداختن به شرایط پیچیده تر، محدودیت های مختلفی به مسأله M-TSP اضافه شده و آن را به VRP تبدیل می کند. مسأله مسیریابی وسیله نقلیه شامل یافتن مجموعه ای از مسیرها به گونه ایست که کل هزینه مسیر حداقل شود. ابتدا مسائل VRP حالت تک سفره داشتند، یعنی هر وسیله تنها یک سفر می توانست برود که این مفهوم بعد به حالت چند سفره توسعه پیدا کرد.

اولین مقاله در تاریخچه VRP مقاله دانتزیگ و همکاران[1] (1954) می باشد که به مطالعه مسائل فروشنده دوره گرد در مقیاس بزرگ پرداختند و راه حل هایی ارائه دادند. کلارک و رایت[2] (1964) بیشتر از یک وسیله نقلیه را در فرمول بندی مسأله خود وارد کردند. این تحقیق را می توان به عنوان اولین پژوهش در ادبیات VRP در نظر گرفت. اولین مقاله ای که عبارت «مسیر یابی وسیله نقلیه» را در عنوان خود داشت مقاله گلدن و همکاران[3] (1972) می باشد.

مسائل مسیریابی کلاسیک به صورت زیر تعریف می شوند: «تعیین مسیرهای وسایل نقلیه که هر مسیر در واقع سفری است که از یک انبار مرکزی (دپو) شروع می شود، با ترتیب مشخصی از مجموعه هایی از مشتریان عبور می کند و به همان مرکز بازمی گردد. هر مشتری باید دقیقاً به یک مسیر تخصیص یابد و مجموع مقادیر حمل شده به مشتریان تخصیص داده شده که به یک وسیله نباید از ظرفیت وسیله بیشتر باشد. مسیرها باید به گونه‌ای تعیین شوند که هزینه کل سفر حداقل شود» (تات و ویگو[4] ، 2002).

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

در مسائل مسیریابی، تصمیم گیری در مورد سفارش و تصمیم گیری در مورد مسیریابی همزمان و معمولاً توسط یک واحد انجام نمی شوند. اغلب تصمیم سفارش­دهی توسط مصرف کننده اتخاذ و به تأمین کننده داده می­شود. تأمین کننده تمام سفارشات را جمع می کند و یک برنامه مسیر برای تأمین سفارشات تعیین می کند. مقادیر حمل به هر مشتری برای تأمین کننده ثابت و معلوم است و باید در طول دوره برنامه‌ریزی به مشتریان تحویل شود.