An Adaptive Variable Neighborhood Search for a Heterogeneous Fleet Vehicle Routing Problem with Three-Dimensional Loading Constraints

چکیده

ین مقاله مسئله مسیریابی ناوگان خودروی ناهمگون (3L-HFVRP) را با محدودیت های بارگیری سه بعدی (3D) نشان می دهد، گونه ای عملی جدیدی از مسئله مسیریابی ترکیبی و بارگیری. در این مسئله، بارها شامل مجموعه ای از اقلام سه بعدی و با شکل مستطیل می باشند. ناوگان متشکل از خودروهای ناهمگون با وزن و ظرفیت های فضای متفاوت می باشد. هدف ارائه سرویس به همه مشتریان با انتخاب دسته ای از خودروها می باشد به نحوی که هزینه حمل و نقل کل به حداقل برسد. هزینه ها شامل هزینه ثابت خودرهای انتخاب شده و هزینه سفر شان می باشد. به علاوه، محدودیتهای مربوطه دنباله دار بارگیری که اغلب در کاربردهای واقع گرایانه مواجه می شوند زمان بارگیری و تخلیه اقلام در نظر گرفته می شوند. برای حل این مسئله چالش بر انگیز، ما یک جستجوی همسایگی متغییر تطبیقی (AVNS) را توسعه می دهیم که از نقطه شدید بر اساس اولین ابتکار متناسب برای یافتن الگوی ممکن بارگیری برای هر مسیر استفاده می کند. ما دو استراتژی برای سرعت بخشیدن به پروسه های بارگیری و مسیریابی طراحی می کنیم. ساختار اطلاعات Trie برای ثبت اطلاعات بارگیری مسیرهایی که قبلا دیدار شده اند استفاده می شود و برای کنترل تلاش محاسباتی صرف شده برای هر مسیر. ساختار دیتای توده ای Fibonacci برای نگهداری همه حرکات ممکن و وظایف نوع خودرو استفاده می شوند، که از ارزیابی مکرر برخی تحرکات و بررسی بارگیری غیرلازم روشهای نامطلوب اجتناب می کند. قدرت و کارایی الگوریتم پیشنهادی توسط تست های محاسباتی تائید شده اند هم در چند نمونه 3L-HFVRP تازه تولید شده و هم نمونه های معیاری شناخته شده از تحقیقات برای دو گونه VRP ساده: مسئله مسیریابی خودروی با ظرفیت واحد با محدودیتهای بارگیری سه بعدی (3L-CVRP) و مسئله مسیریابی ناوگان خودرویی ناهمگون (HFVRP) . تحقیقات عددی نشان می دهند که AVNS از دیگر الگوریتم ها در 3L-CVRP برتر هستند و چندین بهترین روشهای شناخته شده را که گزارش شده اند را بهبود می بخشند. نتایج بدست آمده برای HFVRP خالص بسیار مشابه به بهترین روشهای شناخته شده می باشند.

Abstract

The paper addresses the heterogeneous fleet vehicle routing problem with three-dimensional (3D) loading constraints (3L-HFVRP), a new practical variant of the combined routing and loading problem. In this problem, the loads consist of a set of three-dimensional, rectangular shaped items. The fleet is composed of heterogeneous vehicles with different weight and space capacities. The objective is to serve all customers by selecting a set of vehicles such that the total transportation cost is minimized. The cost consists of the fixed cost of the selected vehicles and their travel cost. In addition, loading sequence related constraints frequently encountered in realistic applications are respected when loading and unloading the items. To solve this challenging problem, we develop an adaptive variable neighborhood search (AVNS) which utilizes an extreme point based first fit heuristic to find a feasible loading pattern for each route. We design two strategies to accelerate the loading and routing processes. The Trie data structure is used to record the loading information of routes already visited and to control the computational effort spent for each route. The Fibonacci heap data structure is used to maintain all of the possible moves and vehicle type assignments, which avoids the duplicated evaluation of some moves and unnecessary loading check of unpromising solutions. The robustness and effectiveness of the proposed algorithm is validated by computational tests performed both on some newly generated 3L-HFVRP instances and well-known benchmark instances from the literature for two simplified VRP variants: the capacitated vehicle routing problem with 3D loading constraints (3L-CVRP) and the pure heterogeneous fleet vehicle routing problem (HFVRP). The numerical experiments show that the proposed AVNS outperforms other algorithms in 3L-CVRP and improves several best known solutions reported in the literature. The results obtained for the pure HFVRP are very close to the best known solutions.