مسئله مسیریابی وسیله نقلیه

گرافی از یک مسئله مسیریابی وسیله نقلیه

مسئله مسیریابی وسیله نقلیه (انگلیسی: Vehicle routing problem) یا به اختصار VRP، یک مسئله بهینه سازی ترکیبیاتی و بهینه‌سازی خطی عدد صحیح است و این سوال را مطرح می‌کند که: "مجموعه مسیرهای بهینه برای یک ناوگان وسایل نقلیه به منظور ارائه به مجموعه‌ای از مشتریان چیست؟". این مسئله، مسئله فروشنده دوره‌گرد (TSP) را تعمیم می‌دهد. اولین بار در مقاله‌ای از جرج دانتزیگ و جان رامسر در سال 1959 ظاهر شد، که در آن اولین رویکرد الگوریتمی نوشته شد و برای تحویل بنزین به کار رفت. اغلب، زمینه مسئله، تحویل کالاهایی است که در یک انبار مرکزی قرار دارند، به مشتریانی که سفارش چنین کالاهایی را داده‌اند. هدف VRP به حداقل رساندن هزینه کل مسیر است. در سال 1964، کلارک و رایت رویکرد دانتزیگ و رامسر را با استفاده از یک الگوریتم حریصانه کارآمد به نام الگوریتم صرفه‌جویی بهبود دادند.

تعیین راه حل بهینه برای VRP، یک مسئله NP-سخت است، بنابراین اندازه مسائلی که می‌توان به طور بهینه با استفاده از برنامه‌ریزی ریاضی یا بهینه سازی ترکیبیاتی حل کرد، ممکن است محدود باشد. بنابراین، حل‌کننده‌های تجاری به دلیل اندازه و فراوانی VRP‌های دنیای واقعی که باید حل کنند، تمایل دارند از روش‌های اکتشافی استفاده کنند.

VRP کاربردهای مستقیم زیادی در صنعت دارد. فروشندگان ابزارهای مسیریابی VRP اغلب ادعا می‌کنند که می‌توانند 5 تا 30 درصد در هزینه صرفه‌جویی کنند.

تنظیم مسئله

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

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

برای محاسبه هزینه کل هر مسیر، باید هزینه سفر و مدت زمان سفر بین هر مشتری و انبار مشخص باشد. برای دستیابی به این هدف، گراف اصلی ما به گرافی تبدیل می‌شود که رئوس آن، مشتریان و انبار هستند و یال‌ها، جاده‌های بین آن‌ها هستند. هزینه روی هر یال، کمترین هزینه بین دو نقطه در شبکه اصلی جاده است. انجام این کار آسان است؛ زیرا حل مسائل یافتن کوتاه‌ترین مسیر نسبتاً آسان است. این فرآیند، گراف اصلی پراکنده را به یک گراف کامل تبدیل می‌کند. برای هر جفت رئوس i و j، یک یال (i,j) در گراف کامل وجود دارد که هزینه آن به صورت C_ij نوشته می‌شود و به عنوان هزینه کوتاه‌ترین مسیر از i تا j تعریف می‌شود. زمان سفر t_ij، مجموع زمان‌های سفر یال‌ها در کوتاه‌ترین مسیر از i تا j در گراف اصلی جاده است.

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Vehicle routing problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۳ آوریل ۲۰۲۴.