Journal of Industrial Engineering Research in Production Systems

Journal of Industrial Engineering Research in Production Systems

Lagrangian rRelaxation for Green Vehicle Routing Problem with Time Windows and Speed Limitations: A Case Study

Document Type : Research Paper

Authors
Arash Pazhouhandeh 1
Javad Behnamian 2
1 1Ph.D. Student of Industries, Department of industries, Faculty of Technology and Engineering, Bu-Ali Sina University, Hamadan, Iran
2 2Associate Professor, Department of Industries, Faculty of Technology and Engineering, Bu-Ali Sina University, Hamadan, Iran
10.22084/ier.2022.26083.2079
Abstract
As a relatively emerging topic in optimization, green routing could reduce the fixed and variable costs induced by different parts of a routing and transportation system and the costs imposed by pollution. This study proposes green transportation routing with a time window under confirmed stable conditions that consider transportation capacity restrictions, speed and time of delivery, and allocation of authorized drivers. This being the case, the goals of selecting the shortest route to goods transfer with the lowest costs caused by pollution, overdue fines, and maintenance of costs could be attained. Accordingly, the Lagrangian relaxation algorithm was employed, and the mathematical model of mixed-integer was developed to address the problem. Lagrange coefficient takes advantage of subgradient methods and closed methods. Lagrangian relaxation is applied separately to address two restrictions. The algorithm saves time by immediate problem solving than the Baron approach. These papers seek to simultaneously use complex restrictions close to actual incidents and could be more similar to natural conditions than other developed models.
Keywords
Green Vehicle routing
Lagrangian Relaxation
Time Window
Speed Constraint
Capacity Constraint
  • Morganti, S. Seidel, C. Blanquart, L. Dablanc, and B. Lenz, “The Impact of E-commerce on Final Deliveries: Alternative Parcel Delivery Services in France and Germany,” 2014. doi: 10.1016/j.trpro.2014.11.014.
  • Janjevic, M. Winkenbach, and D. Merchán, “Integrating collection-and-delivery points in the strategic design of urban last-mile e-commerce distribution networks,” Transportation Research Part E: Logistics and Transportation Review, 2019, doi: 10.1016/j.tre.2019.09.001.
  • H. Lin, Y. Wang, D. He, and L. H. Lee, “Last-mile delivery: Optimal locker location under multinomial logit choice model,” Transportation Research Part E: Logistics and Transportation Review, 2020, doi: 10.1016/j.tre.2020.102059.
  • ع. علی زاده، م. عابدیان، م. خونساری. (1399). ”پیاده‌سازی الگوریتم آزادسازی لاگرانژ در مدل مسیریابی سبز“. [Online]. Available: https://civilica.com/doc/1124924
  • B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, 1959, doi: 10.1287/mnsc.6.1.80.
  • Laporte, “The vehicle routing problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, 1992, doi: 10.1016/0377-2217(92)90192-C.
  • W. P. Savelsbergh, “Local search in routing problems with time windows,” Annals of Operations Research, 1985, doi: 10.1007/BF02022044.
  • Simchi-Levi, X. Chen, and J. Bramel, “The logic of logistics: Theory, algorithms, and applications for logistics and supply chain management: Second edition,” in Springer Series in Operations Research and Financial Engineering, 2005.
  • M. Solomon, “ALGORITHMS FOR THE VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW CONSTRAINTS.,” Operations Research, 1987, doi: 10.1287/opre.35.2.254.
  • K. Rand, B. L. Golden, and A. A. Assad, “Vehicle Routing: Methods and Studies (Studies in Management Science and Systems, Volume 16),” J Oper Res Soc, 1988, doi: 10.2307/2583052.
  • S.; Srivastava, S. Kumar, R. C.; Garg, and P. Sen, “GENERALIZED TRAVELLING SALESMAN PROBLEM THROUGH n SETS OF NODES,” CORS Journal, 1969.
  • E. Noon and J. C. Bean, “An Efficient Transformation of the Generalized Traveling Salesman Problem,” INFOR: Information Systems and Operational Research, 1993, doi: 10.1080/03155986.1993.11732212.
  • Fischetti, J. J. Salazar González, and P. Toth, “A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem,” Operations Research, vol. 45, no. 3, pp. 378–394, 1997, doi: 10.1287/opre.45.3.378.
  • Gutin and D. Karapetyan, “A memetic algorithm for the generalized traveling salesman problem,” Natural Computing, vol. 9, no. 1, 2010, doi: 10.1007/s11047-009-9111-6.
  • Helsgaun, “Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm,” Mathematical Programming Computation, vol. 7, no. 3, 2015, doi: 10.1007/s12532-015-0080-8.
  • L. Smith and F. Imeson, “GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem,” Computers and Operations Research, vol. 87, 2017, doi: 10.1016/j.cor.2017.05.010.
  • Yuan, D. Cattaruzza, M. Ogier, and F. Semet, “A branch-and-cut algorithm for the generalized traveling salesman problem with time windows,” European Journal of Operational Research, vol. 286, no. 3, 2020, doi: 10.1016/j.ejor.2020.04.024.
  • C. McKinnon and M. I. Piecyk, “Measurement of CO2 emissions from road freight transport: A review of UK experience,” Energy Policy, 2009, doi: 10.1016/j.enpol.2009.07.007.
  • A. Juan, J. Goentzel, and T. Bektaş, “Routing fleets with multiple driving ranges: Is it possible to use greener fleet configurations?,” Applied Soft Computing Journal, 2014, doi: 10.1016/j.asoc.2014.03.012.
  • Ç. Koç, T. Bektaş, O. Jabali, and G. Laporte, “The fleet size and mix pollution-routing problem,” Transportation Research Part B: Methodological, 2014, doi: 10.1016/j.trb.2014.09.008.
  • Salehi, M. Jalalian, and M. M. Vali Siar, “Green transportation scheduling with speed control: trade-off between total transportation cost and carbon emission,” Computers and Industrial Engineering, vol. 113, 2017, doi: 10.1016/j.cie.2017.09.020.
  • Erdoĝan and E. Miller-Hooks, “A Green Vehicle Routing Problem,” Transportation Research Part E: Logistics and Transportation Review, 2012, doi: 10.1016/j.tre.2011.08.001.
  • F. Bard, L. Huang, M. Dror, and P. Jaillet, “A branch and cut algorithm for the VRP with satellite facilities,” IIE Transactions (Institute of Industrial Engineers), 1998, doi: 10.1080/07408179808966528.
  • L. Fisher, “LAGRANGIAN RELAXATION METHOD FOR SOLVING INTEGER PROGRAMMING PROBLEMS.,” Management Science, 1981, doi: 10.1287/mnsc.27.1.1.
  • Kohl and O. B. G. Madsen, “An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation,” Operations Research, 1997, doi: 10.1287/opre.45.3.395.
  • Jepsen, B. Petersen, S. Spoorendonk, and D. Pisinger, “Subset-row inequalities applied to the vehicle-routing problem with time windows,” Operations Research, vol. 56, no. 2, 2008, doi: 10.1287/opre.1070.0449.
  • Ç. Koç and I. Karaoglan, “The green vehicle routing problem: A heuristic based exact solution approach,” Applied Soft Computing Journal, 2016, doi: 10.1016/j.asoc.2015.10.064.
  • Policroniades Chípuli and I. Flores de la Mota, “Analysis, design and reconstruction of a VRP model in a collapsed distribution network using simulation and optimization,” Case Studies on Transport Policy, vol. 9, no. 4, 2021, doi: 10.1016/j.cstp.2021.07.002.
  • توکلی مقدم. رضا، ر. مسعود، ش. محمدعلی، ص. نیما. ”حل مسأله مسیریابی وسایل نقلیه با پنجره های زمانی نرم بااستفاده از یک الگوریتم فرا ابتکاری تلفیقی“. دانشکده فنی دانشگاه تهران، 469- 476
  • ع. بابایی تیرکلایی، ش. هادیان، ا. مهدوی، م. م. سیداصفهانی. (2019). ”حل مسأله مسیریابی وسایل نقلیه سبز با درنظر گرفتن وضعیت ترافیک شهری و کاهش سوخت مصرفی در توزیع کالاهای فاسدشدنی“. فصلنامه مهندسی حمل‌‌ونقل. 11(1): 163-180. [Online]. Available: http://jte.sinaweb.net/article_79654.html
  • ز. نورمحمدزاده،” الگوریتم آزادسازی لاگرانژ جهت یکپارچه‌سازی مسائل زمان‌بندی تولید و تحویل بارویکرد مسیریابی وسیله نقلیه“. 1394. [Online]. Available: https://civilica.com/doc/409442/
  • Messaoud, A. el Bouzekri El Idrissi, and A. E. Alaoui, “A hybrid metaheuristic algorithm for the green vehicle routing problem in the dynamic environment,” International Journal of Applied Metaheuristic Computing, vol. 12, no. 4, 2021, doi: 10.4018/IJAMC.2021100102.
  • Chen, E. Demir, and Y. Huang, “An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots,” European Journal of Operational Research, vol. 294, no. 3, 2021, doi: 10.1016/j.ejor.2021.02.027.
  • ن. نوروزی، م. صادق عمل نیک، ر. توکلی مقدم. (2017). ”کاهش انرژی مصرفی و زمان سفر در مسأله مسیریابی وسائط نقلیه با درنظر گرفتن سرعت‌های سفر وابسته‌به زمان توسط الگوریتم رقابت استعماری“. نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید. 4(9): 213-219.doi: 10.22084/ier.2017.1810.
  • ر. توکلی‌مقدم، ش. مسعودی، ح. اقبالی. (2016). ”حل مدل ریاضی جدید برای مسأله مسیریابی وسایل نقلیه چندهدفه و چند قرارگاهی با الگوریتم ژنتیک مرتب شده غیرمغلوب“, نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید. 3(6): 167-175. [Online]. Available: https://ier.basu.ac.ir/article_1353.html
  • ا. شفائی، م. اکبری جوکار، م. رفیعی. (2021). ”بررسی اثرات استفاده از مدل VRP بر کاهش هزینه‌های توزیع قطعات یدکی بین خودروهای امدادی“. نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید. 9(18): 111-125. doi: 10.22084/ier.2021.24224.2025.
Journal of Industrial Engineering Research in Production Systems
Volume 9, Issue 19
February 2022
Pages 155-167