Lagrangian Relaxation Algorithm for Solving Multi-Fleet Feeder Vehicle Routing Problem

Document Type : Research Paper

Authors

1 Ph.D. student, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

Abstract

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.

Keywords

Main Subjects


  • Salehi Sarbijan, M. and J. Behnamian, Multi-fleet feeder vehicle routing problem using hybrid metaheuristic. Computers & Operations Research, 2022. 141: p. 105696.
  • Tu, s., S. Lai, and Y. Li, Application of the vehicle routing problem with time windows—an example of lunch box delivery. Graduation Term Paper, Department of Transportation Technology and Logistics Management, Chung Hua University, Hsin Chu, Taiwan, 2001.
  • Chang, J., Y.J. Cho, and Y.C. Hwang. A study on time constrained vehicle routing problem for lunch box delivery. in in Proceedings of the Annual Meeting of Chinese Institute of Industrial Engineering. 2001. Kaohsiung, Taiwan.
  • Chen, H.K., et al., The linehaul-feeder vehicle routing problem with virtual depots. IEEE Transactions on Automation Science and Engineering, 2011a. 8(4): p. 694-704.
  • Chen, H.K., H.W. Chou, and C.Y. Hsu, The linehaul-feeder vehicle routing problem with virtual depots and time windows. Mathematical Problems in Engineering, 2011 b: p. 1-15.
  • Chen, H.K. and Wang, A two-stage algorithm for the extended linehaul-feeder vehicle routing problem with time windows. International Journal of Shipping and Transport Logistics 2012. 4(4): p. 339-356.
  • Chen, H.K., Issues for the linehaul-feeder vehicle routing problem with virtual depots and time windows. Journal of the Eastern Asia Society for Transportation Studies, 2015. 11: p. 678-692.
  • Brandstätter, C. and M. Reimann, The line-haul feeder vehicle routing problem: Mathematical model formulation and heuristic European Journal of Operational Research, 2018a. 270(1): p. 157-170.
  • Brandstätter, C. and M. Reimann, Performance analysis of a metaheuristic algorithm for the line-haul feeder vehicle routing problem. Journal on Vehicle Routing Algorithms, 1(2-4): p. 121-138.
  • Brandstätter, C., A metaheuristic algorithm and structured analysis for the Line-haul Feeder Vehicle Routing Problem with Time Windows. Central European Journal of Operations Research, 2019: p. 1-43.
  • Huang, Y.-H., et al., Solving the Feeder Vehicle Routing Problem using ant colony optimization. Computers & Industrial Engineering, 2019. 127: p. 520-535.
  • Salehi Sarbijan, M. and J. Behnamian, Real-time collaborative feeder vehicle routing problem with flexible time windows. Swarm and Evolutionary Computation, 2022. 75: p. 101201.
  • Conejo, A.J., et al., Decomposition techniques in mathematical programming: engineering and science applications. 2006: Springer Science & Business Media.
  • Guignard, M., Lagrangean relaxation. Top, 2003. 11(2): p. 151-200.
  • Alkaabneh, F., A. Diabat, and S. Elhedhli, A Lagrangian heuristic and GRASP for the hub-and-spoke network system with economies-of-scale and congestion. Transportation Research Part C: Emerging Technologies, 2019. 102: 249-273.
  • Afra, A.P. and J. Behnamian, Lagrangian heuristic algorithm for green multi-product production routing problem with reverse logistics and remanufacturing. Journal of Manufacturing Systems, 2021. 58: p. 33-43.
  • Diabat, A., J.-P. Richard, and C.W. Codrington, A Lagrangian relaxation approach to simultaneous strategic and tactical planning in supply chain design. Annals of Operations Research, 2013. 203(1): p. 55-80.
  • Imai, A., E. Nishimura, and J. Current, A Lagrangian relaxation-based heuristic for the vehicle routing with full container load. European journal of operational research, 2007. 176(1): p. 87-105.
  • [19 Hamdan, B. and A. Diabat, Robust design of blood supply chains under risk of disruptions using Lagrangian relaxation. Transportation Research Part E: Logistics and Transportation Review, 2020. 134: p. 101764.
  • توکلی‌مقدم، رضا، حسینی، سید محمد حسن، عموزاد خلیلی، حسین. مدل‌سازی و حل مسأله زنجیره‌تأمین ساخت برمبنای سفارش در شرایط محدودیت ظرفیت تولید با استفاده از الگوریتم آزادسازی لاگرانژی. نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 1398، 7(14): 147-161.
  • کلوندی، الهه، بهنامیان، جواد. آزادسازی لاگرانژ برای زمان‌بندی جریان کارگاهی منعطف در شبکه‌های چند کارخانه‌یی ناهمسان. مهندسی صنایع و مدیریت، 1400; 37.1(2): 113-121.
  • Yang, S., et al., Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows. Transportation Research Part E: Logistics and Transportation Review, 2020. 135: p. 101891.
  • Nezhad, A.M., Manzour, and S. Salhi, Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem. International Journal of Production Economics, 2013. 145(2): p. 713-723.