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

نویسندگان

1 گروه پژوهشی کسب و کار الکترونیک، پژوهشکده فناوری اطلاعات، پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک).

2 کارشناسی ارشد مهندسی صنایع، واحد الکترونیکی، دانشگاه آزاد اسلامی ، تهران، ایران.

3 استادیار دانشکده مهندسی صنایع، واحد الکترونیکی، دانشگاه آزاد اسلامی، تهران، ایران.

چکیده

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

کلیدواژه‌ها

موضوعات

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

A total covering problem and facility dispersion with existing facility, capacitated demand, and variable transfer cost

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

  • Ali Naimi-Sadigh 1
  • Amir Emami 2
  • Marzieh Mozafari 3

1 Information Technology Research Department, Iranian Research Institute for Information Science and Technology (IranDoc), Tehran, Iran.

2 MSc of Industrial Engineering, Electronic Branch, Islamic Azad University, Tehran, Iran.

3 Assistant Professor of Department of Industrial Engineering, Electronic Branch, Islamic Azad University, Tehran, Iran.

چکیده [English]

Total covering problem is one of the most commonly used issues of locating facilities. In this context, the goal of determining the P service center is to cover at least the cost of deploying all demand points. These issues have a wide range of nature and scope, each of which is optimized by taking into account certain conditions in order to find the answer. One of these conditions can be a situation in which, in addition to full coverage of demand, the dispersion of facilities is also considered. Facility dispersion means maximizing the distance between facilities with respect to existing limits. This research seeks to provide a suitable model considering the predictable limits of the real world and the use of an appropriate method for solving the cover-dispersion model. Accordingly, the full coverage of the solution space and the choice of the optimal location of the facility with maximum dispersion, taking into account the minimum number of facilities and the lowest cost of deployment, due to the limited capacity of facilities and the minimization of transportation costs are the goals of this research. Due to the NP-HARD nature of the coating and literature models, solving these models, an algorithm is designed based on the genetic method for solving the model. In order to improve the quality of the algorithm's parameters, the parameters of the algorithm are set by the Taguchi experimental design method. The results show that the algorithm is suitable for the model.

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

  • Total covering problem
  • Facility dispersion
  • Genetic algorithm
  • Taguchi method
Al-Sultan, K. S., Hussain, M. F., & Nizami, J. S. (1996). A genetic algorithm for the set covering problem. Journal of the operational research society, 47(5), 702-709.‏ https://doi.org/10.1016/0377-2217(95)00159-X
 Arkat, J., & Zamani, S. (2016). Critical facilities location problem considering principles of passive defense. Journal of advanced defence science and technology, 6(4), 265–276. Retrieved from https://www.sid.ir/en/journal/ViewPaper.aspx?id=539349
Asahiro, Y., Iwama, K., Tamaki, H., & Tokuyama, T. (2000). Greedily finding a dense subgraph. Journal of algorithms, 34(2), 203-221. https://doi.org/10.1006/jagm.1999.1062
Baouche, F., Billot, R., Trigui, R., & El Faouzi, N. E. (2014). Electric vehicle charging stations allocation model.‏ ROADEF - 15th annual congress of the French society for operational research and decision Aid, Feb 2014, Bordeaux, France. https://hal.archives-ouvertes.fr/hal-00946317/
Bashiri, M., & Yaghoubi, M. R. (2017). The nested hierarchical p-center modeling & solving with PSO algorithm. Journal of modeling engineering, 14(47), 187-197.‏ (In Persion). https://doi.org/10.22075/jme.2017.2478
Bashiri, M., Hajfathaliha, A., & Hejazi, T. H. (2010, January). A simulated annealing algorithm for bi-objective noxious network location problem considering dispersion and total cost. 2010 second international conference on computer modeling and simulation (pp. 194-198). IEEE.‏ https://doi.org/10.1109/ICCMS.2010.414
Batta, R., Lejeune, M., & Prasad, S. (2014). Public facility location using dispersion, population, and equity criteria. European journal of operational research, 234(3), 819-829.‏ https://doi.org/10.1016/j.ejor.2013.10.032
Beasley, J. E. (1990). A lagrangian heuristic for set‐covering problems. Naval Research Logistics (NRL), 37(1), 151-164. Retrieved from https://doi.org/10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2
Beasley, J. E., & Chu, P. C. (1996). A genetic algorithm for the set covering problem. European journal of operational research, 94(2), 392-404.‏ https://doi.org/10.1016/0377-2217(95)00159-X
Berman, O., Drezner, Z., & Krass, D. (2011). Discrete cooperative covering problems. Journal of the operational research society, 62(11), 2002-2012.‏ https://doi.org/10.1057/jors.2010.176
Berman, O., Kalcsics, J., & Krass, D. (2016). On covering location problems on networks with edge demand. Computers & operations research, 74, 214-227.‏ https://doi.org/10.1016/j.cor.2015.04.005
Bhattacharya, U. K. (2011). A multi-objective obnoxious facility location model on a plane. American journal of operations research, 1(2), 39-45.‏ https://doi.org/10.4236/ajor.2011.12006
Chandu, D. P. (2014). A parallel genetic algorithm for generalized vertex cover problem. International Journal of Computer Science and Information Technologies (IJCSIT), 5 (6), 7686-7689.‏ https://arxiv.org/abs/1411.7612
Abdulhalim, M. F., & Bara’a, A. A. (2015). Multi-layer genetic algorithm for maximum disjoint reliable set covers problem in wireless sensor networks. Wireless personal communications, 80(1), 203-227.‏ https://doi.org/10.1007/s11277-014-2004-8
Christofides, N. (1975). Graph Theory. An Algorithmic Approach, Computer science and applied mathematics. Academic Press; illustrated edition. https://www.amazon.com/Graph-Theory-Algorithmic-Approach-Christofides/dp/0121743500
Colombo, F., Cordone, R., & Lulli, G. (2016). The multimode covering location problem. Computers & operations research, 67, 25-33.‏ https://doi.org/10.1016/j.cor.2015.09.003
Current, J. R., & Storbeck, J. E. (1988). Capacitated covering models. Environment and planning B: planning and design, 15(2), 153-163.‏ https://doi.org/10.1068/b150153
Daskin, M. S. (2011). Network and discrete location: models, algorithms, and applications. John Wiley & Sons.‏ https://doi.org/10.1002/9781118537015
Degel, D., & Lutter, P. (2013). A robust formulation of the uncertain set covering problem. Retrieved from http://www.optimization-online.org/DB_FILE/2013/06/3926.pdf
Erkut, E. (1990). The discrete p-dispersion problem. European journal of operational research, 46(1), 48-60.‏ https://doi.org/10.1016/0377-2217(90)90297-O
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability a guide to the theory of NP-Completeness (series of books in the mathematical sciences).W. H. Freeman. https://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455
Gupta, R., & Saxena, R. R. (2014). Fuzzy linear fractional set covering problem with imprecise costs. RAIRO-operations research, 48(3), 415-427.‏ https://doi.org/10.1051/ro/2014015
Hakimpour, F., Talat Ahary, S., & ranjbar, a. (2017). the assessment and Comparison of a Genetic Algorithm, Simulated Annealing and Cuckoo Optimization Algorithm for Optimization of the Facility Location under Competitive Conditions (Case Study: Banks). Journal of modeling engineering, 15(48), 231-246.‏ (In Persion).https://doi.org/10.22075/jme.2017.2447
Hemmati, M., & Smith, J. C. (2016). A mixed-integer bilevel programming approach for a competitive prioritized set covering problem. Discrete optimization, 20, 105-134.‏ https://doi.org/10.1016/j.disopt.2016.04.001
Jacobs, L. W., & Brusco, M. J. (1993). A simulated annealing-based heuristic for the set-covering problem. Proc. “Operations management and information systems department”. Northern Illinois University, Deklab, IL 60115, USA.
Karbasian, M., & Dashti, M. (2011). Designing four multi-objective models for dispersion facilities location problems considering data envelopment analysis and maximum covering. International journal of management science and engineering management, 6(4), 298-306.‏ https://doi.org/10.1080/17509653.2011.10671177
Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). Springer, Boston, MA.‏ https://doi.org/10.1007/978-1-4684-2001-2_9
Keller, O. H. (1965). [Review of the book Packing and covering. (Cambridge tracts in mathematics and mathematical physics, No. 54) VIII+ 111 S. Cambridge 1964. At the University Press. Preis geb. 30 s. net. By C. A. Rogers]. ZaMM, 45(6), 450-450. https://doi.org/10.1002/zamm.19650450620
Kortsarz, G., & Peleg, D. (1993). On choosing a dense subgraph. Proceedings of 1993 IEEE 34th annual foundations of computer science (pp. 692-701). IEEE.‏ 10.1109/SFCS.1993.366818
Liu, J. N., Hu, Y., & He, Y. (2014). A set covering based approach to find the reduct of variable precision rough set. Information sciences, 275, 83-100.‏ https://doi.org/10.1016/j.ins.2014.02.023
Lutter, P., Degel, D., Büsing, C., Koster, A. M., & Werners, B. (2017). Improved handling of uncertainty and robustness in set covering problems. European journal of operational research, 263(1), 35-49.‏ https://doi.org/10.1016/j.ejor.2017.04.044
Mokhtari., H. (2017). Modeling and solution of job shop scheduling with no-wait orders to minimize makespan: a decomposition approach based on order sequencing and timetabling. Journal of modeling engineering, 15(50), 261-270.‏ (In Persion). https://doi.org/10.22075/jme.2017.2567
Mori, T. (1991). The new experimental design: Taguchi's approach to quality engineering.‏ Amer Supplier Inst. https://doi.org/10.1007/978-1-4615-5293-2_2
Pham, T. A., Hà, M. H., & Nguyen, X. H. (2017). Solving the multi-vehicle multi-covering tour problem. Computers & operations research, 88, 258-278.‏ https://doi.org/10.1016/j.cor.2017.07.009
Prokopyev, O. A., Kong, N., & Martinez-Torres, D. L. (2009). The equitable dispersion problem. European journal of operational research, 197(1), 59-67.‏ https://doi.org/10.1016/j.ejor.2008.06.005
Ravi, S. S., Rosenkrantz, D. J., & Tayi, G. K. (1994). Heuristic and special case algorithms for dispersion problems. Operations research, 42(2), 299-310.‏ https://doi.org/10.1287/opre.42.2.299
Richter, S., Helmert, M., & Gretton, C. (2007). A stochastic local search approach to vertex cover. In annual conference on artificial intelligence (pp. 412-426). Springer, Berlin, Heidelberg.‏ https://doi.org/10.1007/978-3-540-74565-5_31
Sadigh, A. N., Mozafari, M., & Kashan, A. H. (2010). A mixed integer linear program and tabu search approach for the complementary edge covering problem. Advances in engineering software, 41(5), 762-768.‏ https://doi.org/10.1016/j.advengsoft.2009.12.017
Solar, M., Parada, V., & Urrutia, R. (2002). A parallel genetic algorithm to solve the set-covering problem. Computers & operations research, 29(9), 1221-1235.‏ https://doi.org/10.1016/S0305-0548(01)00026-0
Song, L., Chen, H., Gu, H., Huang, H., & Du, H. (2015). Set covering in fuel-considered vehicle routing problems. Theoretical computer science, 607, 471-479.‏ https://doi.org/10.1016/j.tcs.2015.06.009
Suletra, I. W., Priyandari, Y., & Jauhari, W. A. (2018). Capacitated set-covering model considering the distance objective and dependency of alternative facilities. IOP conf. series: materials science and engineering, 319. 10.1088/1757-899X/319/1/012072
Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations research, 19(6), 1363-1373. https://doi.org/10.1287/opre.19.6.1363
Tutunchi, G. K., & Fathi, Y. (2019). Effective methods for solving the Bi-criteria p-Center and p-Dispersion problem. Computers & operations research, 101, 43-54.‏ https://doi.org/10.1016/j.cor.2018.08.009
Vieira, B. S., Ferrari, T., Ribeiro, G. M., Bahiense, L., Orrico Filho, R. D., Abramides, C. A., & Júnior, N. F. R. C. (2020). A progressive hybrid set covering based algorithm for the traffic counting location problem. Expert systems with applications, 160, 113641.‏ https://doi.org/10.1016/j.eswa.2020.113641
Zarandi, M. F., Davari, S., & Sisakht, S. H. (2012). The Q-coverage multiple allocation hub covering problem with mandatory dispersion. Scientia iranica, 19(3), 902-911.‏ https://doi.org/10.1016/j.scient.2012.03.007