بهینه سازی حملونقل نفت خام با الگوگیری از مساله بستهبندی ظرف

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

نویسندگان

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

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

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

چکیده

.در سال های گذشته مقالات بسیاری در زمینه تفسیر و مدلسازی مسائل جدید توسط مدل‌های پایه به منظور تسهیل در حل مسائل ارائه شده است. یکی از پرکاربردترین این مدل‌های پایه، مسئله بسته‌بندی ظرف (BPP) است که درسال های اخیر کاربرد آن در مدل سازی مسائل مختلف روبه افزایش است. در این مقاله ضمن معرفی یک تعمیم جدید از مسئله بسته بندی ظرف به نام مسئله بسته‌بندی ظرف با هزینه و اندازه متفاوت (VCSBPP)، برای اولین بار یک مسئله " تصمیم‌گیری برای انتقال نفت خام توسط روش های مختلف حمل و نقل" توسط VCSBPP تفسیر و مدلسازی می شود. مدل ریاضی ارائه شده برای این مساله، دو هدفی است و به این سوال که برای انتقال نفت خام از بین روش های موجود از کدام روش و یا چه ترکیبی از روش ها استفاده شود تا علاوه بر هزینه‌ها، میزان ریسک نیز کاهش یابد پاسخ می‌دهد. روش‌های حمل‌و‌نقل براساس پنج معیار "ظرفیت"، هزینه هماهنگی"، "هزینه راه اندازی"، "هزینه حمل" و " هزینه ریسک" تعریف می شوند. بر اساس پیشینه ی تحقیق، به این دلیل که مدل ریاضی دو هدفی ارائه شده در این مقاله از نوع NP-hard است، برای حل آن از الگوریتم فراابتکاری ژنتیک مرتب‌شده نامغلوب (NSGA-II)استفاده می‌شود که یکی از متداول‌ترین الگوریتم‌های تکاملی چند‌هدفه است. همچنین از روش برنامه ریزی آرمانی برای نمایش کارایی الگوریتم پیشنهادی در ابعاد‌‌ کوچک استفاده می‌شود. نتایج این ‌الگوریتم برای تعدادی از مسائل با ابعاد بزرگ نیز ارایه و ‌سپس توسط شاخصهای "میانگین فاصله از آرمان"، و "پراکندگی" و "زمان حل" مورد ارزیابی قرار می‌گیرد

کلیدواژه‌ها

موضوعات

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

Optimization of Crude Oil Transportation by Using the Bin Packing Problem

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

  • ُSeyyed Masoud Tahanian Qomi 1
  • Maryam Hamedi 2
  • Reza Tavakkoli-Moghaddam 3
1 Ph.D., Student, Department of Industrial Engineering, Payame Noor University, Tehran, Iran.
2 Assistant Professor, Department of Industrial Engineering, Payame Noor University, Tehran, Iran.
3 Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.
چکیده [English]

In recent years, many papers have been presented on the interpretation and modeling of new problems by basic models. One of the most widely used of these basic models is the Bin Packing Problem (BPP). One of the most widely used of these basic models is BPP, the use of which is increasing in various modeling. In this paper, while introducing a new generalization of the BPP called the developed VCSBPP, a "decision to transport crude oil by different modes of transport" problem is interpreted and modeled by the BPP for the first time. The proposed mathematical model has two objectives and answers the question of which method or combination of methods is used to transfer crude oil from the existing methods in order to reduce the risk in addition to the costs. Transportation methods are defined based on five criteria: "capacity", "coordination cost", "set-up cost", "transportation cost" and "risk cost". Because based on the literature, the presented model is a bi-objective nonlinear programming type and NP-hard one to be solved in a reasonable time, a well-known multi-objective evolutionary algorithm, namely a non-dominated sorting genetic algorithm (NSGA-II), is proposed. To verify the obtained solution and evaluate the performance of the NSGA-II, the goal programing method is developed in solving small-sized problems. In large-sized problems, the test problems are solved by the proposed NSGA-II. Then, the Pareto-optimal solutions are evaluated by Mean Ideal Distance (MID), diversification, and time metrics.

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

  • Bin packing problem
  • Crude oil transportation
  • Variable Cost and Size Bin Packing Problem (VCSBPP)
  • Non-Dominated Sorting Genetic Algorithm (NSGA-II)

مراجع

Almasi, M., Khoshfetrat, S. and Galankashi, M.R., (2019), “Sustainable supplier selection and order allocation under risk and inflation condition”, IEEE Transactions on Engineering Management, pp.1-15.
-Anand, S. and Guericke, S., (2020), “A Bin Packing Problem with Mixing Constraints for Containerizing Items for Logistics Service Providers”, In International Conference on Computational Logistics­, Springer, Cham.
pp. 342-355.
-Aydin, N., Muter, I. and Birbil, S. I., (2019), “Bin Packing Problem with Time Dimension: An Application in Cloud Computing, Preprint”.
-Aydin, N., Muter, I. and Birbil, S. I., (2020), “Multi-objective temporal bin packing problem: An application in cloud computing”, Computers and Operations Research, pp.104959.
-Baldi, M. M., Crainic, T. G., Perboli, G. and Tadei, R., (2012), “The generalized bin packing problem”, Transportation Research Part E: Logistics and Transportation Review, Vol.48, No.6, pp. 1205-1220.
-Baldi, M. M., Manerba, D., Perboli, G. and Tadei, R., (2019), “A generalized bin packing problem for parcel delivery in last-mile logistics”, European Journal of Operational Research, Vol. 274, No.3, pp.990-999.
-Balliauw, M., Kort, P.M. and Zhang, A.M. (2019), “Capacity investment decisions of two competing ports under uncertainty: a strategic real options approach”, Transportation research part B: Methodological, Vol. 122, pp.249–264.
-Canbolat, P.G., Rothblum, U.G., (2019), “Constant risk aversion in stochastic contests with exponential completion times”, Naval Research Logistics, Vol., 66. No.1,  pp.4–14.
-Charnes, A., Cooper, WW. (1961), “Management Models and the Industrial Applications of Linear Programming”, Wiley, New York.
-Cheng, L., Duran, M. A., (2004), “Logistics for world-wide crude oil transportation using discrete event simulation and optimal control”, Computers and chemical engineering, ­Vol. 28, No.6-7, pp.897-911.
-Chernykh, I. and Pyatkin, A., (2019), “Irreducible bin packing: complexity, solvability and application to the routing open shop”. In International Conference on Learning and Intelligent Optimization, Springer, Cham., pp. 106-120.
-Correia, I., Gouveia, L., Saldanha-da-Gama, F., (2008), “Solving the variable size bin packing problem with discretized formulations”, Computers and Operations Research, Vol.35, No.6, pp. 2103–2113.
-Crainic, T. G., Perboli, G., Rei, W. and Tadei, R., (2011), “Efficient lower bounds and heuristics for the variable cost and size bin packing problem”, Computers and Operations Research, Vol.38, No. 11, pp.1474-1482.
-Deb, K., (2011), “Multi-objective optimisation using evolutionary algorithms: an introduction. In Multi-objective evolutionary optimisation for product design and manufacturing”, London: Springer.
-Deb, K., Pratap, A. and Agarwal, S., (2002), “A fast and elitist multi objective genetic algorithm: NSGA-II”, IEEE transactions on evolutionary computation, Vol.2, pp. 182-97.
-Emmerson, C., Stevens, P., (2012), “Maritime Choke Points and the Global Energy System”, Charting a Way Forward, Chatham House Briefing Paper, London, Vol. 4.
-Fan, J., Wang, G. and Thürer, M., (2020), “Approximation algorithms for a new truck loading problem in urban freight transportation”, Transportation Science, Vol. 54, No.3, pp. 690-702.
-Fatima, A., Javaid, N., Sultana, T., Aalsalem, M. Y. and Shabbir, S., (2019), “An efficient virtual machine placement via bin packing in cloud data centers”, In International Conference on Advanced Information Networking and Applications, pp. 977-987, Springer, Cham.
-Garey, M. R., Johnson, D., (1979), “A Guide to the Theory of NP-Completeness”, Freeman, San Francisco, Computers and Intractability, Vol.26, pp.618–630.
-Gavriilidis, K., Kambouroudis, D.S. and Tsakou, K., (2018), “Volatility forecasting across tanker freight rates: the role of oil price shocks”, Transportation Research Part E: Logistics and Transportation Review.Vol.118. pp.376-391.
-Gradisar, D. and Glavan, M., (2020), “Material Requirements Planning Using Variable-Sized Bin-Packing Problem Formulation with Due Date and Grouping Constraints”, Processes, Vol.8, No.10.
-Griffiths, V., Scanlan, J. P., Eres, M. H., Martinez-Sykora, A. and Chinchapatnam,
P., (2019), “Cost-driven build orientation and bin packing of parts in Selective Laser Melting (SLM)­”, European Journal of Operational Research, Vol.273, No.1, pp. 334-352.
-Gzara, F., Elhedhli, S. and Yildiz, B. C., (2020), “The Pallet Loading Problem: Three-dimensional Bin Packing with Practical Constraints”, European Journal of Operational Research.
-Hebler, K., Irnich, S., Kreiter, T. and Pferschy, U., (2020), “Lexicographic
Bin-Packing Optimization for Loading Trucks in a Direct-Shipping System”, No. 2009.
-Kaaouache, M., Bouamama, S., (2015), “Solving bin packing problem with a hybrid genetic algorithm for VM placement in cloud”. Procedia Computer Science, Vol.60,
pp.1061-1069.
-Li, J.P., Sun, X.L., He, W., Tang, L. and Xu, W.X., (2009), “Modeling dynamic correlations and spillover effects of country risk: evidence from Russia and Kazakhstan”, International Journal of Information Technology and Decision Making. Vol.8, No.4, pp.803–818.
-Liang, X., Zhou, S., Chen, H. and Xu, R. (2019), “Pseudo transformation mechanism between resource allocation and bin-packing in batching environments”, Future Generation Computer Systems, Vol.95, pp.79-88.
-Liu, Z.G., Wang, J., (2019), “Supply chain network equilibrium with strategic financial hedging using futures”, European Journal of Operational Research, Vol. 272, No. 3,
pp. 962–978.
-Martello, S., Toth, P., (1990), “Knapsack Problems: Algorithms and Computer Implementations”, New York­,Wiley.
-Monaci, M., (2002), “Algorithms for Packing and Scheduling Problems”, PhD Thesis, University di Bologna, Bologna, Italy.
-Polyakovskiy, S. and M’Hallah, R., (2020), “Just-in-time two-dimensional bin packing”, Omega, pp.102311.
-Spencer, K. Y., Tsvetkov, P. V. and Jarrell, J. J., (2019), “A greedy memetic algorithm for a multi objective dynamic bin packing problem for storing cooling objects”, Journal of Heuristics, Vol.25, No.1, pp.1-45.
-Su, B., Xie, N. and Yang, Y., (2020), “Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem”, Journal of Intelligent Manufacturing, pp.1-13.
-Tavakkoli-Moghaddam, R., Amiri, M. and Azizmohammadi, R., (2013), “Solving a redundancy allocation problem by a hybrid multi-objective imperialist competitive algorithm”, International Journal of Engineering, Vol.9, No.26, pp.1031-1042.
-Wang, F., Yang, X., Zhuo, X.P. and Xiong, M.H., (2019), “Joint logistics and financial services by a 3PL firm: effects of risk preference and demand volatility”. Transportation Research Part E: Logistics and Transportation Review, Vol.130, pp.312–328.
Wang, L., Yao, D.D., (2019), “Risk hedging for production planning”, Production and Operations Management.
-Wang, S., Li, J. and Mehrotra, S., (2019), “Chance-Constrained Bin Packing Problem with an Application to Operating Room Planning”. 
-Wang, S., Lu, J. and Jiang, L., (2020), “Time Reliability of the Maritime Transportation Network for China’s Crude Oil Imports”, Sustainability, Vol.12, No.1,
pp.198-209.
-Wen, X., Xu, X.Y., Choi, T.M. and Chung, S.H., (2019), “Optimal pricing decisions of competing air-cargo-carrier systems-impacts of risk aversion, demand, and cost uncertainties”. IEEE Transactions on Systems, Man, and Cybernetics: Systems, pp.1–15.
-Ye, D., Xie, F. and Zhang, G., (2020), “Truthful mechanism design for bin packing with applications on cloud computing”.
 

فایل ها

هم رسانی

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

آمار