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

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

مسئله مسیریابی وسیله نقلیه (انگلیسی: 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 در گراف اصلی جاده است.

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

توسعه بهینه الگوریتم از مهمترین بخش های بهینه سازی است . از دیگر روش های بهینه سازی مسئله VRP را می توان از طریق GA یا الگوریتم ژنتیک که به الگوریتم تکامل تدریجی نیز شناخته می شود نام برد . روش حل بهینه سازی مسیر در این الگوریتم ها بطور خلاصه بدین شکل است که در ابتدا تعدادی راه حل یا همان Chromosome ایجاد و نقاط مختلف مانند محل های تحویل و یا انبار ها درون آن بعنوان Gene بصورت تصادفی و غیر تکراری قرار می گیرند و روی آنها محاسبات مورد نیاز انجام می شود . سپس ، تعدادی از راه حل هایی که بهتر از بقیه راه حل ها بودند را انتخاب و به مرحله بعد می روند . در مرحله بعد از کار برای تولید راه حل های جدید از همان راه حل های منتخب استفاده می کنند که در اصطلاح به آن Crossover یا تولید مثل می گویند . اینکار باعث می شود که فرزندان که همان راه حل های جدید هستند از شرایط مناسب تر والدین خود بخشی را به ارث برده و مسئله را به سمت یافتن راه حل های بهتر سوق می دهند . در مراحل بعد می توان از عملیاتی مانند Mutation یا جهش استفاده کرد . جهش باعث ایجاد تغییر ناخواسته در یک راه حل ایجاد می کند که ممکن است به بهتر شدن وضعیت و یا بدتر شدن آن بیانجامد . این فرآیند را تا زمانی که به شرایط مطلوب برسند انجام می دهند و در پایان از بهترین راه حل موجود را بعنوان جواب در نظر می گیرد .

از قابلیت هایی که می توان به الگوریتم های بهینه سازی می توان استفاده کرد را در زیر اشاره می کنیم :

• استفاده از ترافیک لحظه ای برای محاسبه مدت زمان و فاصله بین دو نقطه
• افزودن مدت زمان توقف برای هر نقطه
• رتبه بندی مشتری ها و نقاط برای ایجاد اولویت در بهینه سازی مسیر و محاسبه زمان رسیدن
• بهینه سازی چند تایی برای چند خودرو در یک عملیات
• بهینه سازی برای وسیله نقلیه موتورسیکلت
• بهینه سازی برای بازاریاب ها و ویزیتور های پیاده
• بهینه سازی بر اساس یک نقطه شروع ثابت
• و ...

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

منابع

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

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