موضوع مقاله: مسئله مسیریابی وسیله نقلیه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله مسیریابی وسیله نقلیه | مقدمه: اولین بار در مقاله‌ای از جرج دانتزیگ و جان رامسر در سال 1959 ظاهر شد، که در آن اولین رویکرد الگوریتمی نوشته شد و برای تحویل بنزین به کار رفت. | ## بخش 1: مسئله مسیریابی وسیله نقلیه | اغلب، زمینه مسئله، تحویل کالاهایی است که در یک انبار مرکزی قرار دارند، به مشتریانی که سفارش چنین کالاهایی را داده‌اند. در سال 1964، کلارک و رایت رویکرد دانتزیگ و رامسر را با استفاده از یک الگوریتم حریصانه کارآمد به نام الگوریتم صرفه‌جویی بهبود دادند. تعیین راه حل بهینه برای VRP، یک مسئله NP-سخت است، بنابراین اندازه مسائلی که می‌توان به طور بهینه با استفاده از برنامه‌ریزی ریاضی یا بهینه سازی ترکیبیاتی حل کرد، ممکن است محدود باشد. بنابراین، حل‌کننده‌های تجاری به دلیل اندازه و فراوانی VRP‌های دنیای واقعی که باید حل کنند، تمایل دارند از روش‌های اکتشافی استفاده کنند. فروشندگان ابزارهای مسیریابی VRP اغلب ادعا می‌کنند که می‌توانند 5 تا 30 درصد در هزینه صرفه‌جویی کنند. در این مسئله، کالاها، از یک یا چند انبار که دارای مجموعه مشخصی از ناوگان وسایل نقلیه است و توسط مجموعه‌ای از رانندگان که می‌توانند در یک شبکه جاده‌ای معین حرکت کنند، به مجموعه‌ای از مشتریان، هدایت می‌شوند. در این مسئله، به دنبال مجموعه‌ای از مسیرها (S) هستیم که برای هر وسیله نقلیه، یک مسیر مجزا وجود داشته باشد که از انبار خود شروع کند و به آن ختم شود. هدف این است که تمام نیازهای مشتریان و محدودیت‌های عملیاتی برآورده شود و در عین حال، کل هزینه حمل و نقل به حداقل برسد. شبکه راه را می‌توان با استفاده از یک گراف توصیف کرد که در آن، یال‌ها نشان‌دهنده جاده‌ها، و رئوس، اتصالات بین آن‌ها هستند. | ## بخش 2: مسئله مسیریابی وسیله نقلیه | یال‌ها ممکن است جهت‌دار یا بدون جهت باشند، زیرا ممکن است خیابان‌های یک طرفه یا هزینه‌های متفاوت در هر جهت وجود داشته باشد. به هر یال هزینه‌ای اختصاص داده می‌شود که به طور کلی طول یا زمان سفر آن است و ممکن است به نوع وسیله نقلیه بستگی داشته باشد. برای محاسبه هزینه کل هر مسیر، باید هزینه سفر و مدت زمان سفر بین هر مشتری و انبار مشخص باشد. برای دستیابی به این هدف، گراف اصلی ما به گرافی تبدیل می‌شود که رئوس آن، مشتریان و انبار هستند و یال‌ها، جاده‌های بین آن‌ها هستند. برای هر جفت رئوس i و j، یک یال (i,j) در گراف کامل وجود دارد که هزینه آن به صورت Cij نوشته می‌شود و به عنوان هزینه کوتاه‌ترین مسیر از i تا j تعریف می‌شود. زمان سفر tij، مجموع زمان‌های سفر یال‌ها در کوتاه‌ترین مسیر از i تا j در گراف اصلی جاده است. گاهی اوقات برآورده کردن تمام خواسته‌های مشتری غیرممکن است و در چنین مواقعی، حل‌کننده‌ها ممکن است برخی از درخواست‌های مشتری را کاهش دهند یا برخی از مشتریان را بدون سرویس رها کنند. برای مقابله با این شرایط می‌توان یک متغیر اولویت برای هر مشتری در نظر گرفت یا جریمه‌های مربوط به خدمات جزئی یا عدم ارائه خدمات برای هر مشتری در نظر گرفت. از دیگر روش های بهینه سازی مسئله VRP را می توان از طریق GA یا الگوریتم ژنتیک که به الگوریتم تکامل تدریجی نیز شناخته می شود نام برد . | ## بخش 3: مسئله مسیریابی وسیله نقلیه | روش حل بهینه سازی مسیر در این الگوریتم ها بطور خلاصه بدین شکل است که در ابتدا تعدادی راه حل یا همان Chromosome ایجاد و نقاط مختلف مانند محل های تحویل و یا انبار ها درون آن بعنوان Gene بصورت تصادفی و غیر تکراری قرار می گیرند و روی آنها محاسبات مورد نیاز انجام می شود . سپس ، تعدادی از راه حل هایی که بهتر از بقیه راه حل ها بودند را انتخاب و به مرحله بعد می روند . در مرحله بعد از کار برای تولید راه حل های جدید از همان راه حل های منتخب استفاده می کنند که در اصطلاح به آن Crossover یا تولید مثل می گویند . اینکار باعث می شود که فرزندان که همان راه حل های جدید هستند از شرایط مناسب تر والدین خود بخشی را به ارث برده و مسئله را به سمت یافتن راه حل های بهتر سوق می دهند . جهش باعث ایجاد تغییر ناخواسته در یک راه حل ایجاد می کند که ممکن است به بهتر شدن وضعیت و یا بدتر شدن آن بیانجامد . این فرآیند را تا زمانی که به شرایط مطلوب برسند انجام می دهند و در پایان از بهترین راه حل موجود را بعنوان جواب در نظر می گیرد . از قابلیت هایی که می توان به الگوریتم های بهینه سازی می توان استفاده کرد را در زیر اشاره می کنیم : استفاده از ترافیک لحظه ای برای محاسبه مدت زمان و فاصله بین دو نقطه افزودن مدت زمان توقف برای هر نقطه رتبه بندی مشتری ها و نقاط برای ایجاد اولویت در بهینه سازی مسیر و محاسبه زمان رسیدن بهینه سازی چند تایی برای چند خودرو در یک عملیات بهینه سازی برای وسیله نقلیه موتورسیکلت بهینه سازی برای بازاریاب ها و ویزیتور های پیاده بهینه سازی بر اساس یک نقطه شروع ثابت و ... | ## جمع‌بندی | با توجه به تغییرات مختلف در سطح جامعه و کشور ، حتما در توسعه بهینه الگوریتم برای رسیدن به نتایج مورد دلخواه مورد نیاز است .