الگوریتم آزادسازی لاگرانژ برای حل مساله مسیریابی وسیلۀ نقلیه تغدیه‌کنندۀ چندناوگانی

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

lagrangian relaxation algorithm for solving multi-fleet feeder vehicle routing problem

receiving fast, flexible, reliable and low-cost delivery services by customers is one of the important challenges for the distribution of goods, especially in urban areas. after that, with the increase in demand and as a result, the increase in vehicles for the purpose of goods' transportation, it causes congestion in urban transportation networks. therefore, in this study, the multi-fleet feeder vehicle routing problem is investigated in a situation where several trucks and motorcycles cooperate with each other to satisfy the demand at the same time. the feeding vehicle routing problem consists of a heterogeneous fleet of vehicles, including trucks and it makes it possible for motorcycles to pass in high-traffic areas and distribute urban traffic easily. in fact, the feeder approach in the vrp is to reduce the number of times of returning to the main depot for loading and to save the cost and time of tours. here, at first, a mathematical model is presented, then, due to the high complexity of the mixed integer programming model and in order to reduce the runtime of solving the model in large dimensions, the lagrangian relaxation algorithm with the sub-gradient optimization approach is proposed. the results showed that with the increase in the dimensions of the problem, the runtime of the proposed algorithm is less compared to the outputs of gams. also, the runtime saving resulting from solving the model with the lagrangian relaxation algorithm is significant, and as a result, this algorithm is effective for solving the model.