ارزیابی و کاربرد الگوریتم ژنتیک در مکان یابی مراکز خرید با شرایط رقابتی

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

نویسندگان

1 کارشناس ارشد سیستم اطالاعات مکانی، دانشکده مهندسی نقش هبرداری، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران.

2 استادیار گروه سیستم اطلاعات مکانی، دانشکده مهندسی نقش هبرداری، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران.

چکیده

بسیاری از مسائل در جهان واقعی متأثر از پارامترها و اهداف گوناگونی می باشند. با توجه به گسترش روزافزون جمعیت شهرها، ارائه خدمات شهری مناسب به شهروندان اهمیت بالایی پیدا می کند. این تحقیق به مکانی‏یابی بهینه خدمات شهری و به ویژه مراکز خرید می پردازد و عوامل متعددی را مورد توجه قرار می دهد. با تعریف اهداف مختلف مؤثر بر مکان‏یابی، نیازمند استفاده از روش های چندهدفه برای حل مسئله هستیم. دو رویکرد کلی برای حل مسائل چندهدفه، روش های سنتی و فراابتکاری می باشند؛ روش های سنتی همه جواب های بهینه پارتو را ارائه نمی دهند و برای دستیابی به هدف واحد ناچار به وز ن دهی اهداف می باشند. لذا علاوه بر اینکه با وز ندهی به اهداف، نظرات کارشناسی را پیش از حل مسئله در آن وارد می کنند، کارکرد مناسبی نیز برای حل مسائل چندهدفه نشان نمی دهند؛ بنابراین در تحقیقات اخیر ترجیح بر کاربرد روش های فراابتکاری می باشد. از میان روش های فراابتکاری، روش بهبود یافته ای از الگوریتم مرتب سازی را به کار بردیم که الگوریتم ژنتیک پارتوی سریع نام دارد. برای پیاده سازی و حل مسئله مکانی‏یابی بهینه II- نامغلوب مراکز خرید، پس از شناسایی مکان های پتانسیل دار در شهر کرج، با اعمال شرایط رقابتی دو هدف دسترس پذیری و جذب تقاضا تعریف شد و با استفاده از روش الگوریتم ژنتیک پارتوی سریع، ترکیب های چندتایی از مراکز خرید شناسایی گردید. تعداد مراکز خرید پیشنهادی به عنوان ورودی مسئله می باشد و با توجه به نیاز کاربر تعیین می شود و هدف از آن یافتن مکان های مناسب با توجه به اهداف مسئله است. خروجی الگوریتم جواب های بهینه پارتو می باشد. جواب های حاصل از اجرای الگوریتم، مکا نهایی را پیشنهاد می دهد که از مراکز خرید موجود فاصله دارد، تقاضای بیشتری را پوشش می دهد و مکان هایی با دسترس پذیری بالا را ارائه می دهد.

کلیدواژه‌ها


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

Evaluation and Application of Genetic Algorithm in Shopping CentersLocation with Competitive Conditions

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

  • Saeid Rashidi 1
  • Mohammad Taleai 2
  • Ahid Naeimi 1
1 Master of Science in Geospatial Information Systems Department, Geodesy and Geomatic Engineering Faculty, K.N.Toosi University of Technology, Tehran, Iran .
2 Assistant Prof. of Geospatial Information Systems Department, Geodesy and Geomatic Engineering Faculty, K. N. Toosi University of Technology, Tehran, Iran.
چکیده [English]

Facility location is an important problem in all kinds of businesses, including service and manufacturing efforts. The suitable selection of business location is a crucial component in the eventual success or failure of the firm. Proper facility location can be a strategic tool that can significantly improve market share growth and increase customer profitability. Facility location involves much more than just selecting a location with good visibility and access. Effective research on competition and market demand are also required. Each of the above mentioned business types have different location requirements that need to be considered when settling upon a location for starting or relocating a business. The most of decision making issues in the real-world are affected by various parameters and objectives. Due to the increasing urban population, providing every citizen with adequate municipal services is highly important. this study deals with optimal locating of municipal services and particularly shopping center and also I considered several criteria, such as the citizens demand, access to shopping centers, opponent shopping centers, the applicant’s access to welfare facilities like public car parks parking and main roads and etc. Optimization is the process of searching for feasible solutions in a problem until no other superior solution can be found. Much of the current focus is on single objective optimization, even though most real-world problems require the simultaneous optimization of more than one objective function. In general, such problems consist of two or more conflicting objective functions with a set of constraints taken into consideration. At this point, it is not possible to obtain a single solution that optimizes simultaneously all the objective functions. Therefore, we need to find out a set of solutions that tradeoff the different objectives called Pareto front thus the concept of optimality in single objective optimization problems is replaced by the concept of Pareto front in multi-objective optimization problems. This set helps the decision maker to identify the best compromise solutions by elimination of inferior ones. The choice of one solution over the other entails an additional knowledge of the problem such as the relative importance of different objectives. As mentioned, the definition of the effective objectives for facility location, requiring the use of multi objective methods for problem solving. There are two general approaches to solving multi objective problems; classic and metaheuristic approach. Classical methods do not provide all the Pareto optimal solutions so to achieve an objective they must be weighted. In addition to the weighting objectives, and considering experts opinions, the methods do not show good performance for multi objective problems. Therefore, in recent research the metaheuristic methods are preferred. Among the metaheuristic methods,we use an improved method of Non-dominated Sorting Genetic Algorithm (NSGA-II), called Fast Pareto genetic algorithm (FPGA), for implementation and solving shopping center location problem. This method is able to find optimal solutions for multi objective problems in objective space. FPGA uses a new ranking strategy for the simultaneous optimization of multiple objectives. New genetic operators are employed to enhance the algorithm’s performance in terms of convergence behavior and computational effort. Computational results indicate that FPGA is a promising approach and it outperforms the improved NSGA-II. Study area, part of the city of Karaj, is including the North of Freeway Karaj – Qazvin. Data of this area for demand capture objective, obtained from Demographic information of the Statistical Center of Iran from the 1385 census. For other information layers, data of Bavand Consulting Engineers database used. The base map of database is of 1:10000 scales. These maps were used as the main source of information. This data layers used to achieving criteria of demand capture and accessibility objectives. For implementation and solving shopping center location problem, after identifying potential sites in the city of Karaj, with considering competitive conditions and defining two objectives; accessibility and demand capture then with using FPGA, multiple combinations of shopping centers were identified. The number of shopping centers is proposed as input and determined according to user needs and its purpose is to find suitable location as objectives of problem. Outputs of the algorithm are Pareto optimum solutions that show the trade-off between the objectives. By the Given input, we can see that the solutions of the algorithm, proposed locations away from existing shopping centers, and it cover a greater demand and have suitable accessibility. In order to validate the results of the FPGA-based approach, Results are compared with outputs of index overlay method. This comparison shows that 90 percent of optimum results in genetic algorithm method stand in two categories with high utility rates. This means that the results of FPGA are in areas with high utility rates.

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

  • Shopping Center Location
  • Competitive Condition
  • Multi Objective Optimizing
  • Fast Pareto Genetic Algorithm
-- Beasley, D., R. Bull, D., Ralph, M. (1993). An Overview of Genetic Algorithms, Inter University of Committee on
Computing (Part1 and 2).
-- Boloori Arabani, A., Zandieh, M., Fatemi Ghomi, S.M.T. (2011). Multi-objective Genetic-based Algorithms for
Cross-docking Scheduling Problem, Applied Soft Computing, 11, 4954-4970.
-- Cheng, E., Li, H., Yu, L. (2005). A GIS Approach to Shopping Mall Location Selection, Building and Environment,
42, 884-892.
-- Deb K, Pratab A, Agarwal S, Meyarivan T. (2001). A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-
II, IEEE Transactions on Evolutionary Computation, 6, 182-197.
-- Dias, J., Captivo E, Climaco J. (2007). A Mementic Algorithm for Dynamic Location Problems, Centro de Investigacao
Operacional, Chapter 12, 225-244.
-- Ehrgott, M., Wiecek, M. (2004). Multi Objective Programming, Department of Engineering Science, Chapter 17,
667- 722.
-- Eskandari, H., Geiger, Ch. (2007). A Fast Pareto Genetic Algorithm Approach for Solving Expensive Multi Objective
Optimization Problems, Journal of Heuristics, 203-241.
-- Farahani, R., Hekmatfar, M. (2009). Facility Location: Concepts, Models, Algorithms and Case Studies, Contributions
to Management Science, Chaper 20, 473-503.
-- Haupt, R., Haupt Sue, E. (2004). Practical Genetic Algorithms, John Wiley and Sons.
-- Jaramillo, J., Bhadury, J., Batta, R. (2002). On the Use of Genetic Algorithms to Solve Location Problems, Computers
& Operations Research, 29, pp 761-779.
-- Khoshamooz, G. (2011). Development of A Spatial Multiple Objective Decision Making Model for Industrial
Planning, Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering in GIS.
-- Modares, A. (2009), A Tabu Search Algorithm for Vehicle Routing and Scheduling Problem, Journal of Transportation
Research 4.
-- Onut, S., Efendigil, T., Soner, K. S. (2009). A Combined Fuzzy MCDM Approach for Selecting Shopping Center
Site: An Example from Istanbul, Turkey, Expert Systems with Applications, 37, 1973-1980.
-- Rahmani, M., Saeidian, T. M. (2009). Introducing Park and Ride Location Model and Solving with Genetic Algorithms,
Journal of Transportation Research, 3, 245-255.
-- Rezaei, J., Davoudi, M. M. (trans.) (2008). Multi-Objective Optimization Using Evolutionary Algorithms, University
of Vali Asr, Rafsanjan, Publisher Pelk.
-- Srinivas, N., Deb, K. (1994). Multi Objective Function Optimization Using Non-Dominated Sorting Genetic Algorithms,
Evolutionary Computation, 2, 221-248.
-- Talebi, R. (2010). Optimum Setting of Parking Places in Tehran City; Case Study: Seven Area of Tehran, Urban
Management, 26, 119-132.
-- Zanjirani Farahani, R., Asgari, N. (2006). Combination of MCDM and Covering Techniques in a Hierarch