الگوریتم شاخه-برش-قیمت برای مساله مسیریابی وسایل نقلیه دارای ظرفیت تجمعی

قیمت: 42,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

الگوریتم شاخه-برش-قیمت برای مساله مسیریابی وسایل نقلیه دارای ظرفیت تجمعی

عنوان لاتین

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

در این مقاله ، مساله مسیریابی وسایل نقلیه دارای ظرفیت تجمعی (CCVRP) در نظر گرفته شده است، که نوعی متفاوت از مساله شناخته شده مسیریابی وسایل نقلیه دارای ظرفیت (CVRP) می باشد. در این مسئله، هدف مرسوم به حداقل رساندن فاصله کل یا زمان سفر طی شده توسط وسایل نقلیه با حداقل سازی مجموع زمان رسیدن به مشتری جایگزین شده است. یک الگوریتم شاخه - برش - قیمت برای به دست آوردن حل های بهینه برای این مساله ارائه شده است. تا جایی که اطلاع داریم، این اولین الگوریتم دقیق منتشر شده برای CCVRP های استاندارد معیار می باشد. نتایج محاسباتی بر اساس مجموعه ای از CCVRP های استاندارد معیار ارائه شده است و اثر اصلاح تعداد وسایل نقلیه موجود را بررسی می کند.

In this paper we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available