مدل‌سازی ریاضی جدید برای مسئله موجودی - مسیریابی وسائط نقلیه الکتریکی

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

نویسندگان

1 مهندسی صنایع/پردیس بین الملل کیش/دانشگاه تهران/کیش

2 استاد دانشکده مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران

3 رئیس دانشکده مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران

چکیده

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

کلیدواژه‌ها

موضوعات


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

New mathematical modelling for an electric vehicle inventory-routing problem

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

  • Kosar Sadeghi-Velni 1
  • Reza Tavakkoli-Moghaddam 2
  • Fariborz Jolai 3
1 School of Industrial Engineering, Kish International Campus, University of Tehran, Kish, Iran
2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran
3 Head of School of Industrial Engineering, College of Engineering, University of Tehran
چکیده [English]

Transportation industry activities have a significant negative impact on the environment, economy and human health. To reduce the environmental impact strategies, such as using electric vehicles, is taken into account. This paper presents a new mathematical model related to the electric vehicle inventory-routing problem. The objective function of the proposed model is to minimize the total cost of this system. Vehicles are considered as electrical device and due to the limited capacity of the batteries, the driving range is limited. Hence, if the battery is over, there is a possibility of swapping the battery at the battery swapping stations. In the proposed model, the shortage is not allowed and the customer demand is certain and determined. Because the proposed problem is categorized as NP-hard one, a meta-heuristic algorithm, namely variable neighborhood search (VNS), is proposed to solve large-scale problems. To evaluate the performance of the proposed VNS, numerical results are compared with the exact method and the simulated annealing (SA) method. The computational results show the proper performance of the proposed VNS.

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

  • Inventory-routing problem
  • electric vehicles
  • meta-heuristic algorithm
- توکلی مقدم، رضا، علینقیان، مهدی، سلامت بخش، علیرضا (1393) "مسأله مسیریابی وسائط نقلیه دوره ای با پنجره زمانی در حالت رقابتی با روش شبیه سازی تبرید بهبود یافته"، فصلنامه مهندسی حمل و نقل، شماره 4، تابستان 1393، ص. 470-449.
- کهفی، عاطفه، توکلی مقدم، رضا (1393) "حل مدل مسیریابی وسایل نقلیه چندانباره مبتنی بر کاهش ریسک با استفاده از یک الگوریتم خفاش چندهدفه"، فصلنامه مهندسی حمل و نقل، شماره 3، بهار 1394، ص. 522-507.
-Bruglieria, M.,  Mancinib, S. , Pezzellac, F. , Pisacaned, O.,  Suracic, S. (2017) "A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges" Electronic Notes in Discrete Mathematics, vol. 58, pp. 95–102.
-Conrad, R.G., Figliozzi, M.A. (2011) "The recharging vehicle routing problem" In: Proceedings of the industrial engineering research conference. Reno, NV.
-Montgomery, D.C. (1997), "Montgomery Design and Analysis of Experiments", USA.
-Desaulniers, G., Fausto, E., Irnich, S., & Schneider, M. (2014) "Technical report les cahiers du gerad, g-2014-110. Canada: Montreal.
-Erdogan, S. & Miller-Hooks, E. (2012) "A green vehicle routing problem", Transp. Res. E: Logist. Transp. Rev. vol. 48, pp. 100–114.
-Felipe, A., Ortuno, M. T., Righini, G. & Tirado, G., (2014) "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges", Transportation Research, Part E: Logistics and Transportation Review, vol. 71(1), pp. 111-128.
-Fleszar, K.I., Osman, H., Hindi, K. S., (2009)"A variable neighbourhood search algorithm for the open vehicle routing problem," European Journal of Operational Research, vol. 195, pp. 803-80.
-Hiermann, G., Puchinger, J., Stefan Ropke, S. & F. Hartl, R. (2016) "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations", European Journal of Operational Research, Vol.252, pp. 995–1018.
-Hof, J., Schneider, M., Goeke, M., (2017) "Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops", Transportation Research Part B: Methodological, vol. 97, pp.102–112.
-Keskin, M. & Çatay, B. (2016) "Partial recharge strategies for the electric vehicle routing problem with time windows", Transportation Research, Part C, vol. 65, pp. 111–127.
-Koç, C. & Karaoglan, I. (2016) "The green vehicle routing problem: A heuristicbased exact solution approach", Applied Soft Computing, vol. 39, pp. 154–164.
-Liao, C.S., Lu, S.H., Shen, Z.J.M. (2016) "The electric vehicle touring problem", Transportation Research Part B, vol. 86, pp. 163–180.
-Lin, J., Zhou, W. & Wolfson, O. (2016) "Electric vehicle routing problem", Transportation Research Procedia, vol.12, pp. 508 – 521.
-Mancini, S., (2017) "The Hybrid Vehicle Routing Problem", Transportation Research Part C: Emerging Technologies, vol.78, pp1-12.
-Mirchandani, P., Madsen, O.B.G. & Adler, J. (2012) "Scheduling and location issues in transforming service fleet vehicles to electric vehicles", in: 12th International Conference on Advanced Systems for Public Transport, Santiago, Chile.
-Murakami, K. (2017) " A new model and approach to electric and diesel-powered vehicle routing", Transportation Research Part E: Logistics and Transportation Review, Vol. 107,pp23-37.
-Perl, J. (1983) "Unified warehouse location-routing analysis", Technical Report, North- western University, Illinois.
-Repoussis, P., Paraskevopoulos, D., Tarantilis, C. & Ioannou, G. (2006) “A reactive greedy randomized variable neighborhood tabu search for the vehicle routing problem with time windows”, Hybrid Metaheuristics, 124-138.
-Schiffer, M., Walther, G., (2017) "The electric location routing problem with time windows and partial recharging", European Journal of Operational Research, vol. 260, pp. 995–1013.
-Schneider, M. , Stenger, A. & Goeke, D. (2012) "The electric vehicle routing problem with time windows and recharging stations", Technical Report, University of Kaiser- slautern, Kaiserslautern.
-Shao, S., Guan, W., Ran, B., He, Z., Bi, J., (2017) "Electric vehicle routing problem with charging time and variable travel time", Mathematical Problems in Engineering, 2017.
-Wang, H. & Shen, J. (2007) "Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints", Appl. Math. Comput. Vol. 190, pp. 1237–1249.
-Worley, O. & Klabjan, D. (2012) "Simultaneous vehicle routing and charging station siting for commercial electric vehicles", In: IEEE International Electric Vehicle Conference, Greenville, SC, 1–3.
-Yang, J. & Sun, H. (2015) "Battery swap station location-routing problem with capacitated electric vehicles", Computers &Operations Research, vol. 55, pp. 217–232.