مسأله‌ يكپارچه‌ي دريافت، تحويل و بازگشت وسايل‌نقليه با محدوديت‌هاي بارگذاري سه‌بعدي و پنجره‌ي زماني

Integrated problem of pick up, delivery and backhaul with three-dimensional loading constraints and time window

مسائل مسيريابي و بارگذاري، دو موضوع مهم‌ براي كاهش هزينه‌هاي حمل‌ونقل محسوب مي‌شود. در دهه‌ي‌ اخير به‌دليل نزديك‌سازي مسائل مسيريابي وسايل‌نقليه به دنياي واقعي، اين مسائل را به‌صورت يكپارچه با يكديگر درنظر گرفته‌اند. رعايت نكردن محدوديت‌هاي بارگذاري منجر به آسيب رسيدن به كالاها و يا استفاده‌ي كمتر از فضاي وسيله‌نقليه مي‌شود كه در هركدام از حالت‌ها باعث خسارت و ايجاد هزينه‌ي اضافه مي‌شود. در اين مقاله براي اولين‌بار مسأله يكپارچه‌ي مسيريابي دريافت، تحويل و بازگشت با محدوديت‌هاي بارگذاري سه‌بعدي و پنجره‌ي زماني درنظر گرفته شده كه محدوديت‌هاي انباشت، جهت‌گيري، عدم‌بارگذاري مجدد و شرايط چند تحويلي در اين مسأله مورد بررسي قرار گرفته است. هم‌چنين در اين مطالعه، آيتم‌ها و كانتينرها ناهمگون درنظر گرفته شده‌اند. با بررسي ادبيات موضوع اين مسأله در ادبيات موضوع مشاهده نگرديد. براي اين مسأله يك مدل برنامه‌ريزي عدد صحيح مختلط، يك الگوريتم ابتكاري و دو الگوريتم فراابتكاري برمبناي جست‌وجوي ممنوع و جست‌وجوي همسايگي متغير ارائه شده است. الگوريتم‌هاي فراابتكاري در ابعاد كوچك با حل پايين حاصل از آزادسازي برخي محدوديت‌هاي مدل ارائه شده مورد ارزيابي قرار گرفته و در ابعاد بزرگ نيز دو الگوريتم فراابتكاري با يكديگر مقايسه شده‌اند. نتايج نشان مي‌دهد متوسط درصد خطاي نسبي در الگوريتم جست‌وجوي ممنوع و جست‌وجوي همسايگي متغير به ترتيب برابر 0/96 و 0/88 مي‌باشد. هم‌چنين الگوريتم جست‌وجوي ممنوع و جست‌وجوي همسايگي متغير توانسته‌اند از 54 نمونه به‌ترتيب در 27 و 25 نمونه جواب بهتري ارائه دهند.

The routing and loading problems are two essential issues to reduce transportation costs. In the recent decade, these problems have been integrated to realize the vehicle routing problem. Failure to comply with the loading constraints may result in damage to the goods or less use of the vehicle space, which in each case will result in additional damage and cost. In this paper, for the first time, the integrated routing problem of pickup, delivery, and backhaul with three-dimensional loading constraints and time window is considered, where the constraints of accumulation, orientation, non-reloading, and multi-delivery conditions are examined. In this study, items and containers are considered heterogeneous. By examining the subject literature, this problem was not observed in the literature. A mixed-integer programming model, a heuristic algorithm, and two metaheuristic algorithms based on tabu search and variable neighborhood search are proposed for this problem. For small instances the proposed metaheuristics were compared to the lower bound obtained from relaxing some constraints of the model. For large instances, the two metaheuristic algorithms are compared together. The results show that the average percentage of relative error in the tabu search and variable neighbor search algorithms is 0.96 and 0.88, respectively. Also, the tabu search algorithm and variable neighborhood search were able to give better results out of 54 instances in 27 and 25 instances, respectively.