برنامه ریزی ظرفیت وسایل نقلیه در یک مسئله مسیریابی چندهدفه با ناوگان ناهمگن

معصومی, ملیحه; بهنامیان, جواد

doi:10.22034/ijts.2021.246922

برنامه ریزی ظرفیت وسایل نقلیه در یک مسئله مسیریابی چندهدفه با ناوگان ناهمگن

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

نویسندگان

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

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

10.22034/ijts.2021.246922

چکیده

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

کلیدواژه‌ها

مسئله مسیریابی وسایل نقلیه / پنجره زمانی/ مصرف انرژی / ناوگان اجارهای / استراتژی ظرفیت

20.1001.1.17350794.1400.25.100.7.5

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

Vehicle Capacity Planning in a Multi-Objective Vehicle Routing Problem With Heterogeneous Fleet

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

Malihe Masoumi ¹
Javad Behnamian ²

¹ PhD student, Department of Industrial Engineering, Buali Sina University, Hamedan, Iran

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

چکیده [English]

Carrying goods from points of supply to different customers is an important task in the supply chain. In this regard, the problem of vehicle routing is of particular importance. In this paper, the Vehicle Routing Problem with Time Windows (VRPTW) is presented using the concept of heterogeneities. The concept of heterogeneities is concerned with the ownership of ﬂeet. Ownership heterogeneities occur when the private ﬂeet is not sufﬁcient and the company has to rent some vehicles from freight companies. Moreover, unlike prior attempts to minimize cost by minimizing overall traveling distance, the proposed model incorporates energy minimizing. In this paper, two different scenarios have been analyzed and for each of them a mathematical multi-objective model is proposed. The first scenario investigates VRPTW regardless of the concept of heterogeneity and in the second scenario, there are some rental vehicles provided by freight companies. In senario II, the number of these vehicles, the time of contract and generally their capacity must be specified. Therefore, the strategy of changing the capacity of the rental fleet is determined based on the proposed model. The proposed solution method of this paper is based on a hybrid artificial immune system, artificial fish swarm, and NSGAII. Metaheuristics finally, small and large-scale test problems are randomly generated, solved and compared by those algorithms. The computational results show that using rental fleet significantly saves costs and energy. Also, the proposed model can be used as a decision support system for carriers to investigate capacity strategies.

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

Vehicle Routing Problem / Time Window /Energy Consumption / Rental Fleet / Capacity Strategy

مراجع

توکلی مقدم، رضا؛ ربانی، مسعود؛ شریعت، محمد‌علی؛ صفایی، نیما؛ (1385). "حل مسئله مسیریابی وسایل نقلیه با پنجره‌های زمانی نرم با استفاده از یک الگوریتم فرا ابتکاری تلفیقی"، نشریه دانشکده فنی دانشگاه تهران، ۴۰(۴) صص.۴۶۹.

فتاحی، پرویز؛ معصومی، ملیحه؛ بهنامیان, جواد. (1396). ارائه یک الگوریتم ترکیبی برای حل مسئله مکان‌یابی مسیریابی-چندکالایی با در نظر گرفتن سیستمهای فرابارانداز در زنجیره‌تأمین، مطالعات مدیریت صنعتی، 15(46)، صص 97-134.

میرمحمدی، سید حمید؛ حاجی شفیعی، زینب. (1394). ‹رویکرد فراابتکاری ترکیبی برای حل مسئله‌ی مسیریابی وسایل نقلیه با محدودیت ظرفیت و تصمیم‌گیری همزمان در سطرجدید مورد خرید یا اجاره‌ی وسایل نقلیه›، مهندسی صنایع و مدیریت، 31.1(1)، صص 73-80.

Bao, Y., Tang, J.F. and Liu, L.L., (2011). Clustering Algorithm for Minimizing Vehicle Number of Airport Pickup and Delivery Service. Computer Integrated Manufacturing Systems, 17(2), pp.442-447.

Bektaş, T. and Laporte, G., (2011). The Pollution-Routing Problem. Transportation Research Part B: Methodological, 45(8), pp.1232-1250.

Brandão, J., (2011). A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem. Computers & Operations Research, 38(1), pp.140-151.

Dantzig, G.B. and Ramser, J.H., (1959). The Truck Dispatching Problem. Management Science, 6(1), pp.80-91.

Dondo, R. and Cerdá, J., (2007). A Cluster-Based Optimization Approach for the Multi-depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 176(3), pp.1478-1507.

Dotoli, M. and Epicoco, N., (2016), October. A Technique for the Optimal Management of Containers’ Drayage at Intermodal Terminals. In 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (pp. 000566-000571). IEEE.

Ernst, A.T., Horn, M., Kilby, P. and Krishnamoorthy, M., (2010). Dynamic Scheduling of Recreational Rental Vehicles with Revenue Management Extensions. Journal of the Operational Research Society, 61(7), pp.1133-1143.

Gahm, C., Brabänder, C. and Tuma, A., (2017). Vehicle Routing with Private Fleet, Multiple Common Carriers Offering Volume Discounts, and Rental Options. Transportation Research Part E: Logistics and Transportation Review, 97, pp.192-216.

Ghannadpour, S.F. and Zarrabi, A., (2019). Multi-Objective Heterogeneous Vehicle Routing and Scheduling Problem with Energy Minimizing. Swarm and Evolutionary Computation, 44, pp.728-747.

Ghoseiri, K. and Ghannadpour, S.F., (2010). Multi-objective Vehicle Routing Problem with Time Windows Using Goal Programming and Genetic Algorithm. Applied Soft Computing, 10(4), pp.1096-1107.

Gounaris, C.E., Repoussis, P.P., Tarantilis, C.D., Wiesemann, W. and Floudas, C.A., (2016). An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem. Transportation Science, 50(4), pp.1239-1260.

Jiang, J., Ng, K.M., Poh, K.L. and Teo, K.M., (2014). Vehicle Routing Problem with a Heterogeneous Fleet and Time Windows. Expert Systems with Applications, 41(8), pp.3748-3760.

Kara, I., Kara, B.Y. and Yetis, M.K., (2007), August. Energy Minimizing Vehicle Routing Problem. In International Conference on Combinatorial Optimization and Applications (pp. 62-71). Springer, Berlin, Heidelberg.

Konings, J.W., (2008). The Future of Intermodal Freight Transport: Operations, Design and Policy. Edward Elgar Publishing.

Kumar, V.S., Thansekhar, M.R., Saravanan, R. and Amali, S.M.J., (2014). Solving Multi-Objective Vehicle Routing Problem with Time Windows by FAGA. Procedia Engineering, 97, pp.2176-2185.

Laporte, G., (2009). Fifty Years of Vehicle Routing. Transportation Science, 43(4), pp.408-416.

Leung, S.C., Zhang, Z., Zhang, D., Hua, X. and Lim, M.K., (2013). A Meta-Heuristic Algorithm for Heterogeneous Fleet Vehicle Routing Problems with Two-Dimensional Loading Constraints. European Journal of Operational Research, 225(2), pp.199-210.

Li, X., Tian, P. and Aneja, Y.P., (2010). An Adaptive Memory Programming Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Review, 46(6), pp.1111-1127.

Liu, R. and Jiang, Z., (2012). The Close–Open Mixed Vehicle Routing Problem. European Journal of Operational Research, 220(2), pp.349-360.

Naderipour, M. and Alinaghian, M., (2016). Measurement, Evaluation and Minimization of CO2, NOx, and CO Emissions in the Open time Dependent Vehicle Routing Problem. Measurement, 90, pp.443-452.

Ogryczak, W., (2001). On Goal Programming Formulations of the Reference Point Method. Journal of the Operational Research Society, 52(6), pp.691-698.

Pepin, A.S., Desaulniers, G., Hertz, A. and Huisman, D., (2009). A Comparison of Five Heuristics for the Multiple Depot Vehicle Scheduling Problem. Journal of Scheduling, 12(1), PP.17-33.

Tavares, G., Zsigraiova, Z., Semiao, V. and Carvalho, M.D.G.,(2008). A Case Study of Fuel Savings Through Optimisation of MSW Transportation Routes. Management of Environmental Quality: An International Journal, 19(4), pp.444-454.

Xiao, Y., Zhao, Q., Kaku, I. and Xu, Y., (2012). Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem. Computers & Operations Research, 39(7), pp.1419-1431.

Zachariadis, E.E., Tarantilis, C.D. and Kiranoudis, C.T., (2015). The Load-Dependent Vehicle Routing Problem and its Pick-up and Delivery Extension. Transportation Research Part B: Methodological, 71, pp.158-181.

Zhang, S., Lee, C.K.M., Choy, K.L., Ho, W. and Ip, W.H., (2014). Design and Development of a Hybrid Artificial Bee Colony Algorithm for the Environmental Vehicle Routing Problem. Transportation Research Part D: Transport and Environment, 31, pp.85-99.

Zhengzheng, X., (2015), May. A Vehicle Routing Approach Using Mixed Vehicles for Pickup and Delivery Services to Airport. In The 27^th Chinese Control and Decision Conference (2015 CCDC) (pp. 6330-6334). IEEE.