نوع مقاله : علمی- ترویجی
نویسندگان
1 استاد، دانشکده مهندسی هوافضا، دانشگاه صنعتی شریف، تهران، ایران
2 کارشناس ارشد، دانشکده علوم و فنون نوین، دانشگاه تهران، تهران، ایران
چکیده
روش بهینه‌سازی دوسطحی زمانی مطرح می‌شود که مسئله هدف دارای دو تصمیم‌گیرنده با سلسله مراتب مختلف باشد. در چنین مسائلی، روابط بهینه‌سازی سطح زیرین در محدوده قیود سطح بالاتر مؤثر هستند و تفکیک آنها از همدیگر امکان‌پذیر نیست. مسائل بهینه‌سازی دوسطحی گستردگی و کاربرد زیادی در موضوعات مرتبط با حمل و نقل کالا و مسافر و در کل مسائل تصمیم گیری خرد و کلان دارند. در این مقاله آخرین یافته‌های تحقیقاتی و روش‌های مدلسازی و حل چنین مسائلی با تمرکز بر سه دهه اخیر ارائه شده است. علاوه بر آن جدیدترین کاربرد این نوع بهینه‌سازی در مسائل حمل و نقل‌های هوافضایی ارائه می‌گردد. در این مقاله، همچنین به معرفی الگوریتم‌های متداول کلاسیک و ترکیبی برای حل اینگونه مسائل می‌پردازیم.
کلیدواژه‌ها
[1] Bard, J.F., "An Algorithm for Solving the General Bilevel Programming Problem", Mathematics of Operations Research, Vol. 8, No. 2, pp. 260-272, 1983.
[2] Ho, K., De Weck, O.L., Hoffman, J.A., and Shishko, R., "Dynamic Modeling and Optimization for Spacelogistics, Using Time-expanded Networks", Acta Astronautica, Vol. 105, No. 2, pp. 428-443, 2014.
[3] Dempe, S., Foundations of Bilevel Programming, Springer Science & Business Media, Berlin, Germany, 2002.
[4] Dempe, S., Kalashnikov, V., Pérez-Valdés, G.A., and Kalashnykova, N., Bilevel Programming Problems, Springer-Verlag, Berlin, Germany, 2015.
[5] Sinha, A., Malo, P., and Deb, K., "A Review on Bilevel Optimization: from Classical to Evolutionary Approaches and Aapplications", IEEE Transactions on Evolutionary Computation, Vol. 22, No. 2, pp. 276-295, 2018.
[6] Hansen, P., Jaumard, B., and Savard, G., "New Branch-and-bound Rules for Linear Bilevel Programming", SIAM Journal on Scientific and Statistical Computing, Vol. 13, No. 5, pp. 1194-1217, 1992.
[7] Edmunds, T.A. and Bard, J.F., "An Algorithm for the Mixed-integer Non-linear Bilevel Programming Problem", Annals of Operations Research, Vol. 34, No. 1, pp. 149-162, 1992.
[8] Ben-Ayed, O., "Bilevel Linear Programming", Computers & Operations Research, Vol. 20, Nno. 5, pp. 485-501, 1993.
[9] Migdalas, A., "Bilevel Programming in Traffic Planning: Models, Methods and Challenge", Journal of Global Optimization, Vol. 7, No. 4, pp. 381-405, 1995.
[10] Smith, M., Xiang, Y., and Yarrow, R., "Bilevel Optimisation of Signal Timings and Roadprices on Urban Road Networks", IFAC Proceedings Volumes, Vol. 30, No. 8, pp. 609-614, 1997.
[11] Hejazi, S., Memariani, A., Jahanshanloo, G., and Sepehri, M., "Bilevel Programming Solution by Genetic Algorithms", The First National Industrial Engineering Conference, Sharif University of Technology, Tehran, Iran, 2001.
[12] Nishizaki, I., Sakawa, M., and Kan, T., "Computational Methods through Genetic Algorithms for Obtaining Stackelberg Solutions to Two Level Integer Programming Problems", Electronics and Communications in Japan (Part III: Fundamental Electronic Science), Vol. 86, No. 6, pp. 59-66, 2003.
[13] Gümüş, Z.H. and Floudas, C.A., "Global Optimization of Mixed-integer Bilevel Programming Problems", Computational Management Science, Vol. 2, No. 3, pp. 181-212, 2005.
[14] Wang, G., Wang, X., Wan, Z., and Lv, Y., "A Globally Convergent Algorithm for a Class of Bilevel Non-linear Programming Problem", Applied Mathematics and Computation, Vol. 188, No. 1, pp. 166-172, 2007.
[15] Sun, H., Gao, Z., and Wu, J., "A Bi-level Programming Model and Solution Algorithm for the Location of Logistics Distribution Centers", Applied Mathematical Modelling, Vol. 32, No. 4, pp. 610-616, 2008.
[16] Rassafi, A.A. and Bavaghar Zaeimi, M., "Solve the Problem of Designing the Transportation Network of Hazardous Materials", The 8th International Civil Engineering Congress, Shiraz University, Shiraz, Iran, 2009 (In Persian).
[17] Domínguez, L.F. and Pistikopoulos, E.N., "Multiparametric Programming Based Algorithms for Pure Integer and Mixed-integer Bilevel Programming Problems", Computers & Chemical Engineering, Vol. 34, No. 12, pp. 2097-2106, 2010.
[18] Hamidi, F. and Mishmast Nehi, H., "Bilevel Linear Programming with Fuzzy Parameters", Iranian Journal of Fuzzy Systems, Vol. 10, No. 4, pp. 83-99, 2013.
[19] Abbasi Molai, A., Pirouzeh, Z., and Jafari, A., "Bilevel Internal Data Envelopment Analysis: A Bilevel Programing Approah", The 4th Conference on Data Envelopment Analysis, University of Mazandaran, Babolsar, Iran, 2002 (In Persian).
[20] Khodamoradi, S., Torabi Goodarzi, M., and Raei Ezabadi, M., "A Two-step Mathematical Approach to Portfolio Optimization", Vol. 4, No. 14, pp. 136-167, 2013 (In Persian).
[21] Harbavi, M., "Optimization Quadratic Bilevel Programming Problems", The 1st International Conference on Management, Accounting and Economics, Rasht, Iran, 2014.
[22] Herminia, C.G., Calvete, I., and Iranzo, J.A., "Planning of a Decentralized Distribution Network, Using Bilevel Optimization", Omega Journal, Vol. 49, No. 2, pp. 30-41, 2014.
[23] Alves, M.J. and Costa, J.P., "An Algorithm Based on Particle Swarm Optimization for Multi-objective Bilevel Linear Problems", Applied Mathematics and Computation, Vol. 247, pp. 547-561, 2014.
[24] Caramia, M. and Mari, R., "Enhanced Exact Algorithms for Discrete Bilevel Linear Problems", Optimization Letters, Vol. 9, No. 7, pp. 1449-1468, 2015.
[25] Agor, J., and Özaltın, O.Y., "Feature Selection for Classification Models Via Bilevel Optimization", Computers & Operations Research, Vol. 106, pp. 156-168, 2018.
[26] Aboussoror, A. and Adly, S., "New Necessary and Sufficient Optimality Conditions for Strong Bilevel Programming Problems", Journal of Global Optimization, Vol. 70, No. 2, pp. 309-327, 2018.
[27] Poirion, P.-L., Toubaline, S., D’Ambrosio, C., and Liberti, L., "Algorithms and Applications for a Class of Bilevel MILPs", Discrete Applied Mathematics, Vol. 272, pp. 75-89, 2020.
[28] Baffier, J.-F., Poirion, P.-L., and Suppakitpaisarn, V., "Bilevel Model for Adaptive Network Flow Problem", Electronic Notes in Discrete Mathematics, Vol. 64, pp. 105-114, 2018.
[29] El-Sobky, B. and Abo-Elnaga, Y., "A Penalty Method with Trust-region Mechanism for Non-linear Bilevel Optimization Problem", Journal of Computational and Applied Mathematics, Vol. 340, pp. 360-374, 2018.
[30] Kumar, A., Gupta, A., and Mehra, A., "A Bilevel Programming Model for Operative Decisions on Special Trains: An Indian Railways Perspective", Journal of Rail Transport Planning & Management, Vol. 8, No'S. 3-4, pp. 184-206, 2018.
[31] Sinha, A., Soun, T., and Deb, K., "Using Karush-kuhn-tucker Proximity Measure for Solving Bilevel Optimization Problems", Swarm and Evolutionary Computation, Vol. 44, pp. 496-510, 2019.
[32] De Marchi, A. and Gerdts, M., "Free Finite Horizon LQR: A Bilevel Perspective and Its Application to Model Predictive Control", Automatica, Vol. 100, pp. 299-311, 2019.
[33] Zito, P., Salvo, G., and La Franca, L., "Modelling Airlines Competition on Fares and Frequencies of Service by Bi-level Optimization", Procedia-Social and BehavioralSciences, Vol. 20, pp. 1080-1089, 2011.
[34] Liu, W., Zheng, Z., and Cai, K., "Adaptive Path Planning for Unmanned Aerial Vehicles, Based on Bi-level Programming and Variable Planning Time Interval", Chinese Journal of Aeronautics, Vol. 26, No. 3, pp. 646-660, 2013.
[35] Mirshams, M., Naseh, H., Taei, H., and Fazeley, H., "Liquid Propellant Engine Conceptual Design by Using a Fuzzy-Multi-objective Genetic Algorithm (MOGA) Optimization Method", Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, Vol. 228, No. 14, pp. 2587-2603, 2014.
[36] Fazeley, H., Taei, H., Naseh, H., and Mirshams, M., "A Multi-objective, Multidisciplinary Design Optimization Methodology for the Conceptual Design of a Spacecraft Bi-propellant Propulsion System", Structural and Multidisciplinary Optimization, Vol. 53, No. 1, pp. 145-160, 2016.
[37] Nik, A. Sadegh, M. Ansarifar, J., and Akhavizadegan, F., "Benders’ Decomposition Algorithm to Solve Bi-level Bi-Objective Scheduling of Aircrafts and Gate Assignment Under Uncertainty", Journal of Industrial and Systems Engineering, Vol. 9, No. 3, pp. 111-126, 2016.
[38] Palagachev, K., "Mixed-Integer Optimal Control and Bilevel Optimization: Vanishing Constraints and Scheduling Tasks", Ph.D. Desertation, Aerospace Engineering, Bundeswehr University Munich, Institut für Mathematik und Rechneranwendung, Germany 2017.
[39] Sun, W., Tang, G., and Hauser, K., "Fast UAV Trajectory Optimization, Using Bilevel Optimization with Analytical Gradients", CoRR, 2018 )[Online]. Available: http://arxiv.org/abs/1811.10753(.
[40] Piprek, P. and Holzapfel, F., "Robust Trajectory Optimization of Vtol Transition Maneuver, Using Bi-level Optimal Control", The 31st Congress of the International Council og the Aeronautica Science, Belo Horizonte, Brazil, 2018.
[41] Zhang, J., Jia, X., Hu, J., and Tan, K., "Satellite Multi-Vehicle Tracking under Inconsistent Detection Conditions by Bilevel K-Shortest Paths Optimization", Digital Image Computing: Techniques and Applications (DICTA), Canberra, Australia, 2018.
[42] Sinha, S.K. Salsingikar, S., and SenGupta, S., "An Iterative Bi-level Hierarchical Approach for Train Scheduling", Journal of Rail Transport Planning & Management, Vol. 6, No. 3, pp. 183-199, 2016.
[43] Patriksson, M. and Rockafellar, R.T., "A Mathematical Model and Descent Algorithm for Bilevel Traffic Management", Transportation Science, Vol. 36, No. 3, pp. 271-291, 2002.
[44] Côté, J.-P., Marcotte, P., and Savard, G., "A Bilevel Modelling Approach to Pricing and Fare Optimisation in the Airline Industry", Journal of Revenue and Pricing Management, Vol. 2, No. 1, pp. 23-36, 2003.
[45] Chiong, R. and Dhakal, S., Natural Intelligence for Scheduling, Planning and Packing Problems, Springer-Verlag, Berlin, Germany, 2009.
[46] Carrasqueira, P., Alves, M.J., and Antunes, C.H. "Bi-level Particle Swarm Optimization and Evolutionary Algorithm Approaches for Residential Demand Response with Different User Profiles", Information Sciences, Vol. 418, pp. 405-420, 2017.
[47] Calvete, H.I., Galé, C., and Oliveros, M.-J., "Bilevel Model for Production–Distribution Planning Solved by Using Ant Colony Optimization", Computers & Operations Research,Vol. 38, No. 1, pp. 320-327, 2011.
[48] Legillon, F. Liefooghe, A., and Talbi, E.-G., "Cobra: A Cooperative Coevolutionary Algorithm for Bi-level Optimization", IEEE Congress on Evolutionary Computation, Brisbane, QLD, Australia, 2012.
[49] Fontaine, P., and Minner, S., "Benders Decomposition for Discrete–continuous Linear Bilevel Problems with Application to Traffic Network Design", Transportation Research Part B: Methodological, Vol. 70, pp. 163-172, 2014.
[50] Labbé, M., Marcotte, P., and Savard, G., "A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing", Management Science, Vol. 44, No. 12-part-1, pp. 1608-1622, 1998.
[51] Lin, B., Wu, J., Wang, J., Duan, J., and Zhao, Y. "A Bi-level Programming Model for the Railway Express Cargo Service Network Design Problem", Symmetry, Vol. 10, No. 6, pp. 227, 2018.
[52] Alves, M.J. and Antunes, C.H., "A Semivectorial Bilevel Programming Approach to Optimize Electricity Dynamic Time-of-use Retailpricing", Computers & Operations Research, Vol. 92, pp. 130-144, 2018.
[53] Bard, J.F., Practical Bilevel Optimization: Algorithms and Applications (Non-convex Optimization and Its Applications, No. 30), Springer, New Yourk, USA, 1998.
[54] Florian, M., and Chen, Y., "A Coordinate Descent Method for the Bi-level OD Matrix Adjustment Problem", International Transactions in Operational Research, Vol. 2, No. 2, pp. 165-179, 1995.
[55] Calvete, H.I., Gale, C., and Mateo, P.M., "A New Approach for Solving Linear Bilevel Problems, Using Genetic Algorithms", European Journal of Operational Research, Vol. 188, No. 1, pp. 14-28, 2008.
[56] Jiang, Y., Li, X., Huang, C., and Wu, X., "Application of Particle Swarm Optimization Based on CHKS Smoothing Function for Solving Non-linear Bilevel Programming Problem", Applied Mathematics and Computation, Vol. 219, No. 9, pp. 4332-4339, 2013.
[57] https://www.gams.com/latest/docs/UG_EMP_NBil evel.html.
[59] Zhou, S., Zemkoho, A.B., and Tin, A., "BOLIB: Bilevel Optimization LIBrary of Test Problems", arXiv preprint arXiv:1812.00230, 2018.
[60] http://www.conopt.com.
)