آزادسازی لاگرانژ برای حل مسأله مسیریابی وسایل نقلیه سبز با درنظر گرفتن پنجره زمانی و محدودیت سرعت: مطالعه موردی

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

2 دانشیار، گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی‌سینا، همدان، ایران

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

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

نویسندگان [English]

  • 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
چکیده [English]

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.

کلیدواژه‌ها [English]

  • 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.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 9، شماره 19
اسفند 1400
صفحه 155-167

فایل ها

هم رسانی

ارجاع به این مقاله

آمار