مکانیابی با روش مونت کارلو و تلفیق آن با الگوریتم‌های جستجوی خام و ژنتیک با رویکرد پردازش تصویر (مطالعه موردی: جایگاه سوخت در شهر تبریز)

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

نویسندگان

دانشکده مهندسی شیمی، دانشگاه صنعتی سهند، تبریز، ایران

چکیده

هدف از این پژوهش، یافتن مکانی بهینه برای احداث واحد جدید در داخل محدوده‌ی شهری و افزودن آن به مجموعه‌‌‌‌‌‌ موجود می‌باشد، به نحوی که متوسط فاصله‌ی پیموده شده توسط هر کاربر تا نزدیک‌ترین واحد، با افزودن آن، به کمترین مقدار ممکن برسد. بدین منظور با استفاده از روش مونت‌کارلو و تلفیق آن با دو روش جستجوی خام و الگوریتم ژنتیک و با استفاده از ابزارهای پردازش تصویر که برای تصحیح نقشه‌ و حذف مناطق برون شهری به کار برده شد، به مدل‌سازی و حل مسئله پرداخته شده است. در این مقاله که برای مورد مطالعاتی شهر تبریز و احداث واحد جدید پمپ بنزین صورت گرفته، تعداد 000‚40 نفر کاربر بصورت تصادفی و با توجه به تراکم جمعیت هر منطقه، در داخل شهر انتخاب شدند و متوسط فاصله‌ی هریک از آن‌ها از نزدیک‌ترین ایستگاه محاسبه شد. در ادامه با استفاده از دو الگوریتم ذکر شده، واحد جدید به نحوی افزوده شد که این فاصله به کمترین مقدار خود برسد. با در نظر گرفتن کاربران تصادفی یکسان برای هر دو روش، الگوریتم ژنتیک با تعداد جمعیت اولیه 60 نفر، تعداد 30 نسل و نرخ جهش 2/0، هم به لحاظ کاهش متوسط فاصله و هم به لحاظ زمان محاسبات، نتایج بهتری را نسبت به روش جستجوی خام با 5000 جستجو ارائه می‌دهد. متوسط فاصله کاربران قبل از افزودن واحد جدید 2105 متر می‌باشد که با افزودن واحد جدید پمپ بنزین از روش جستجوی خام و الگوریتم ژنتیک، این فاصله به ترتیب به 1908 و 1901 متر کاهش می‌یابد.

کلیدواژه‌ها

موضوعات

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

Site selection by Monte Carlo method and integration with brute-force search and genetic algorithm by using image processing approach (Case study: Fuel station in Tabriz city)

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

  • Ramin Nemati
  • Javad Rahbar Shahrouzi
Faculty of Chemical Engineering, Sahand University of Technology, Tabriz, Iran
چکیده [English]

The purpose of this research is to find the optimal location for establishing a new service unit, like fuel station, within the urban area so that the average distance traveled by each user to the nearest unit reaches the lowest value. For this purpose, Monte Carlo simulation method was applied along with two optimization approaches including brute-search and genetic algorithm. In addition, image processing tools were used for distinguishing the urban regions and identifying the border of each zone. As a case study, the construction of a new fuel station unit in Tabriz city is carried out in this article. To achieve this goal, 40,000 users were randomly selected according to the population density of each zone within the city and the average distance of each of them was calculated from the nearest station. Afterwards, using the two mentioned algorithms, the new station was added in such a way that the minimum mean traveling distance was achieved. Considering the same number of random users for both methods, the genetic algorithm with initial population, generation and mutation rate of 60, 30 and 0.2, respectively, was resulted in better performance in terms of time and the mean distance. The mean distance between drivers and stations before adding a new unit was 2105 meters. However, by adding a new fuel station using the brute-search method and the genetic algorithm, this distance is reduced to 1908 and 1901 meters, respectively.

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

  • Site selection
  • Monte-Carlo
  • Brute-force search
  • Genetic algorithm
  • Fuel station

مراجع

[1] R. Z. Farahani, S. Fallah, R. Ruiz, S. Hosseini, and N. Asgari, "OR models in urban service facility location: a critical review of applications and future developments", European Journal of Operational Research, in press, DOI: 10.1016/j.ejor.2018.07.036.
]2[ شمس نوبخت و امیر مصطفوی ماریان، "مکانیابی بهینه جایگاه‌های عرضه سوخت با استفاده از برنامه‌ریزی ریاضی و سیستم اطلاعات جغرافیایی (GIS)، مطالعه موردی مشهد"، فصلنامه مهندسی حمل و نقل، دوره 2، شماره 2، زمستان 1389، صفحه 171-180.
]3[ منصور حاجی حسینلو و شهاب کبیری، "مکانیابی بهینه ایستگاه‌های پمپ بنزین در شبکه‌های درون شهری"، کنفرانس مهندسی حمل و نقل و ترافیک ایران، تهران، ایران، 2 تا 3 اسفند، دوره 11، ۱۳۹0.
]4[ یوسفعلی زیاری و مهدی حسین مردی، "بررسی و تحلیل کاربری اراضی شهری و وزن دهی معیارهای مکانیابی جایگاه‌های پمپ گاز  CNG با استفاده از مدل  AHP (مطالعه موردی: منطقه 4 گازی شهر تهران)"، فصلنامه علمی پژوهشی جغرافیای انسانی، دوره 2، شماره 1، زمستان 1388، صفحه 39-52.
]5[ محمد اجزاء شکوهی و هومن شاداب مهر، "مطالعه تطبیقی موقعیت مکانی پمپ بنزین‌های شهر مشهد"، فصل‌نامه آمایش محیط، دوره 8، شماره 28، بهار 1394، صفحه 67-82.
[6] M. Aslani, and A.A. Alesheikh, "Site selection for small gas stations using GIS", Scientific Research and Essays, Vol. 6, No. 15, August 2011, pp. 3161-3171.
]7[ مهدی بشیری و محمدرضا یعقوبی، "مدل‌سازی ریاضی مساله مکان‌یابی P مرکز با در نظر گرفتن سلسله مراتب لانه‌ای و کاربرد الگوریتم بهینه‌سازی گروهی ذرات در حل آن"، مجله مدل‌سازی در مهندسی، دوره 14، شماره 47، زمستان 1395، صفحه 187-197.
[8] C. Upchurch, and M. Kuby, "Comparing the p-median and flow-refueling models for locating alternative-fuel stations", Journal of Transport Geography, Vol. 18, No. 6, November 2010, pp. 750-758.
[9] S.H.R. Pasandideh, and A. Chambari, "A new model for location-allocation problem within queuing framework", Journal of Optimization in Industrial Engineering, Vol. 3, No. 6, September 2010, pp. 53-61.
]10[ سیده طلیعه شریعتمداری، سید نادر شتاب بوشهری و قدرت افتخاری، "استفاده از راه حلی ابتکاری در مکانیابی جایگاه‌های CNG (مطالعه موردی: شهر اصفهان)"، کنفرانس مهندسی حمل و نقل و ترافیک ایران، تهران، ایران، 2 و 3 اسفند، دوره 11، ۱۳۹0.
[11] I. Capar, and M. Kuby, "An efficient formulation of the flow refueling location model for alternative-fuel stations", IIE Transactions, Vol. 44, No. 8, August 2012, pp. 622-636.
[12] T. Adams, S. Nolen, J. Sweezy, A. Zukaitis, J. Campbell, T. Goorley, S. Greene, and R. Aulwes, "Monte Carlo application toolkit (MCATK)", in SNA + MC 2013 - Joint International Conference on Supercomputing in Nuclear Applications + Monte Carlo, Paris, France, June 2014, Article number: 06009, EDP Sciences.
]13[ مرتضی یعقوبی، علیرضا کرباسی، فاطمه رستمیان و فاطمه رستگاری پور، "بهینه‌سازی تصمیمات تولید با استفاده از روش ترکیبی الگوریتم تکاملی و شبیه‌سازی مونت کارلو"، کنفرانس دوسالانه اقتصاد کشاورزی ایران، شیراز، ایران، 20 و 21 اردیبهشت، دوره 8، 1391.
]14[ فرشاد حکیم پور، سیامک طلعت اهری و ابوالفضل رنجبر، "ارزیابی و مقایسه الگوریتم‌های بهینه‌سازی ژنتیک، شبیه‌سازی تبرید و فاخته‌ها در مکانیابی رقابتی تسهیلات )مطالعه موردی: بانک‌ها("، مجله مدل‌سازی در مهندسی، دوره 15، شماره 48، بهار 1396، صفحه 231-246.
[15] P. Hansen, J. Brimberg, D. Urošević, and N. Mladenović, "Solving large p-median clustering problems by primal–dual variable neighborhood search", Data Mining and Knowledge Discovery, Vol. 19, No. 3, December 2009, pp. 351-375.
[16] M. P. Scaparra, S. Pallottino, and M. G. Scutellà, "Large‐scale local search heuristics for the capacitated vertex p‐center problem", Networks, Vol. 43, No. 4, July 2004, pp. 241-255.
[17] E. Aghezzaf, "Capacity planning and warehouse location in supply chains with uncertain demands", Journal of the Operational Research Society, Vol. 56, No. 4, April 2005, pp. 453-462.
[18] C. G. Rawls, and M. A. Turnquist, "Pre-positioning of emergency supplies for disaster response", Transportation research part B: Methodological, Vol. 44, No. 4, May 2010, pp. 521-534.
[19] J. C. García-Palomares, J. Gutiérrez, and M. Latorre, "Optimizing the location of stations in bike-sharing programs: A GIS approach", Applied Geography, Vol. 35 No. 1-2, November 2012, pp. 235-246.
[20] M. F. Goodchild, and M. T. Noronha, "Location-allocation and impulsive shopping: the case of gasoline retailing", Spatial analysis and location-allocation models, 1987, pp. 121-136.
[21] D. L. Greene, P. N. Leiby, B. James, J. Perez, M. Melendez, A. Milbrandt, and M. Hooks, "Analysis of the Transition to Hydrogen Fuel Cell Vehicles and the Potential Hydrogen Energy Infrastructure Requirements", No. ORNL/TM-2008/30, March 2008, Oak Ridge National Lab. (ORNL), Oak Ridge, TN United States.
[22] M. Nicholas, and J. Ogden, "Detailed analysis of urban station siting for California hydrogen highway network", Transportation Research Record: Journal of the Transportation Research Board, January 2006, pp. 121-128.
[23] M. A. Nicholas, S. L. Handy, and D. Sperling, "Using geographic information systems to evaluate siting and networks of hydrogen stations". Transportation Research Record, No. 1, 2004, pp. 126-134.
[24] Z. Lin, J. Ogden, Y. Fan, and C. W. Chen, "The fuel-travel-back approach to hydrogen station siting", International journal of hydrogen energy, Vol. 33, No. 12, June 2008, pp. 3096-3101.
[25] M. Melendez, and A. Milbrandt, "Analysis of the Hydrogen Infrastructure Needed to Enable Commercial Introduction of Hydrogen-Fueled Vehicles", Preprint (No. NREL/CP-540-37903), National Renewable Energy Lab, Golden, CO (US), Mars 2005.
[26] A. Boostani, R. Ghodsi, and A. K. Miab, "Optimal location of compressed natural gas (CNG) refueling station using the arc demand coverage model", In 2010 Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation, May 2010, pp. 193-198. IEEE.
[27] J. J. Brey, R. Brey, A. F. Carazo, M. J. Ruiz-Montero, and M. Tejada, "Incorporating refuelling behaviour and drivers’ preferences in the design of alternative fuels infrastructure in a city", Transportation Research Part C: Emerging Technologies, Vol. 65, No. 1, April 2016, pp. 144-155.
[28] T. L. Kerzmann, G. A. Buxton, and J. Preisser, "A computer model for optimizing the location of natural gas fueling stations", Sustainable Energy Technologies and Assessments, Vol. 7, No.1, September 2014, pp. 221-226.
[29] Google maps, Tabriz fuel stations, 2017. Retrieved from: https://www.google.com/maps/search/tabriz+fuel+station/@38.0800165,46.2873987,12z/data=!3m1!4b1.
[30] سایت رسمی شهرداری تبریز، نقشه محدوده و حریم قانونی کلانشهر تبریز، سال 1392، برگرفته شده از: http://tshs.tabriz.ir/uploads/User/2000/Maps/Maps2/for_web/for_web/Boundry_Border/TABRIZ_Boundary_Map_2-1.html.
[31] مرکز آمار ایران، گزارش سرشماری جمعیت سال 1395، استان آذربایجانشرقی، شهر تبریز. برگرفته از سایت: https://www.amar.org.ir.
 [32] B. A. Trakhtenbrot, "A survey of Russian approaches to perebor (brute-force searches) algorithms", Annals of the History of Computing, Vol. 6, No. 4, October 1984, pp. 384-400.
]33[ محمد رضایی پژند و سید روح الله موسوی، "ترک‌یابی در سازه‌های مستوی با الگوریتم ژنتیک"، مجله مدل‌سازی در مهندسی، دوره 7، شماره 18، پاییز 1388، صفحه 23-37.
[34] M. Kumar, M. Husian, N. Upreti, and D. Gupta, "Genetic algorithm: Review and application", International Journal of Information Technology and Knowledge Management, Vol. 2, No. 2, July 2010, pp. 451-454.
 
مدل سازی در مهندسی
دوره 17، شماره 57
تیر 1398
صفحه 27-39

فایل ها

سابقه مقاله

  • تاریخ دریافت: 30 خرداد 1397
  • تاریخ بازنگری: 03 دی 1397
  • تاریخ پذیرش: 12 دی 1397

هم رسانی

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

آمار