بررسی الگوریتم رقابت استعماری (ICA) و کاربرد آن در زمینه جمع‌آوری زباله‌های شهری به روش فروشنده دوره‌گرد (TSP) در شهر اردبیل

فصلنامه علمی و پژوهشی پژوهش و برنامه ریزی شهری

مقاله 5، دوره 11، شماره 43، بهمن 1399، صفحه 69-85   

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

نویسندگان

حسین یغفوری¹؛ وحید پاسبان عیسی لو^{* 2}؛ محبوبه تاجی³

¹دانشیار گروه جغرافیا و برنامه ریزی شهری، دانشگاه سیستان و بلوچستان، زاهدان، ایران

²دانشجوی دکتری جغرافیا و برنامه ریزی شهری، دانشگاه سیستان و بلوچستان، زاهدان، ایران

³دانشجوی مقطع کارشناسی ارشد جغرافیا و برنامه ریزی گردشگری، دانشگاه سیستان و بلوچستان، زاهدان، ایران

تاریخ دریافت: 22 بهمن 1398،  تاریخ بازنگری: 09 مرداد 1399،  تاریخ پذیرش: 11 مرداد 1399 

چکیده

امروزه سرعت عمل شهرداری­ها در زمینه ارائه خدمات شهری و در رأس  آن­ها جمع‌آوری زباله‌های شهری نقش بسیار مهمی درزمینه بهبود کارایی این ارگان و درنتیجه جلب رضایت شهروندان دارد. این در حالی است که باوجود مدرنیزه شدن ماشین‌آلات جمع­آوری زباله‌ها، مسئله سرعت عمل ارائه خدمات با اینکه همواره تأثیر بسزایی درزمینه کاهش هزینه و بهبود کیفیت ارائه خدمات دارد، عمدتا مورد بی‌توجهی و غفلت مدیران شهری قرارگرفته است. شهر اردبیل نیز مستثنا از این قضیه نیست. این شهر دارای چهار منطقه و بالغ‌بر 100 محله مختلف هست که همواره شهرداری را درزمینه سرعت عمل در جمع­آوری پسماندهای شهری و ارائه یک‌ چشم‌اندازی زیبا از شهر با مشکل مواجه کرده است. هدف این مقاله افزودن فاکتور سرعت به فرایند فعالیت اکیپ­های جمع‌آوری زباله از طریق پیشنهاد بهترین مسیر حرکت برای این ماشین‌آلات با استفاده از مدل الگوریتم رقابت استعماری است.، به این صورت که با برنامه‌نویسی مربوطه و تعریف موقعیت محلات 100 گانه برای مدل، اقدام به معرفی بهینه‌ترین مسیرهای حرکت به اکیپ‌های خدماتی شهرداری می‌نماییم، با این شرط که از هر محله فقط یک‌بار عبور کنند و بعد از طی همه محلات درنهایت به نقطه شروع حرکت بازگردند. روش پژوهش توصیفی تحلیلی، مبتنی بر مطالعات کتابخانه ای و در صورت لزوم بررسی میدانی است. یافته‌های تحقیق نشان داد که الگوریتم مورداستفاده در تحقیق در صورت دریافت اطلاعات مناسب، ابزار کارآمدی به منظور افزایش سرعت عمل اکیپ های جمع آوری زباله های شهری است. همان طور که برای محلات 100 گانه واقع در مناطق 4 گانه شهر اردبیل با تکرار 200 و به ترتیب با ضریب اطمینان 99، 91،93 و 97 درصد و در بازه زمانی30، 22، 30 و 24 ثانیه به بهینه‌ترین جواب دست‌یافت. به عبارت دیگر گروه های خدماتی در بازه زمانی کمتر، بهترین مسیر برای حرکت و جمع آوری زباله ها را انتخاب کردند.

کلیدواژه‌ها

خدمات شهری؛ مدل فروشنده دوره‌گرد (TSP)؛ الگوریتم رقابت استعماری (ICA)؛ اردبیل

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

Investigation of the imperialist Competitive Algorithm (ICA) and its Application in Urban Services by Travelling Salesman Problem (TSP) model

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

Hossein yaghfoori¹؛ vahid pasban²؛ Mahboobe Taji³

¹Associate Professor of Geography & Urban Planning, Sistan & Baloochestan University, Zahedan, Iran

²PhD Student of Geography & Urban Plannig, Sistan & Baloochestan University, Zahedan, Iran

³MSc Student of Gegraphy & Tourism Planning, Sistan & Baloochestan University, Zahedan, Iran

چکیده [English]

Nowadays, the speed at which municipalities provide urban services and collect urban waste play an important role in improving the efficiency of this organization, and therefore, the satisfaction of the citizens. In recent decades, due to the dominance of consumerism culture in Third World countries, especially Iran, we witness an increase in the urban waste each and every single day. In spite of the modernization of waste collection machines, the service delivery speed has been neglected although it has always had a significant impact on cost reduction and quality of service delivery. The city of Ardabil is no exception to this. It has four districts and 100 large and small neighborhoods in total that have always encountered the municipality with a major problem in terms of the rate at which urban wastes was collected and thus provided a beautiful outlook of the city. This article aims at adding the speed as a factor to the waste collection units by proposing the best route for the machines via Travelling Salesman Problem approach and Imperialist Competitive Algorithm in MATLAB environment. Using the appropriate programming and defining those 100 neighborhoods for the model, the most optimal routes for the municipality’s service units are introduced provided that the service units pass each neighborhood once and at the end return to the starting point again. The results of the study showed that the algorithm used in this research for 100 neighborhoods in those four districts can provide the optimal solution with the repetition of 200 and respectively with the values of 99, 91, 93, and 97 and within the intervals of 30, 22, 30, and 24 seconds.
Keywords: Urban Wastes, Travelling Salesman Problem (TSP) model, Imperialist Competitive Algorithm (ICA)
 
 
Extended Abstract
Introduction
The issue of vehicle routing is one of the important issues that has been widely used in the efficiency and effectiveness of transportation systems in recent decades.
Transportation issues, in addition to being one of the most important categories of optimization issues, are issues that are very effective in life and everyday problems of human life, including in the field of municipal services. On the other hand, one of the most important challenges in today's fast-paced life, especially in urban affairs management, is preventing waste of time and energy in order to prevent huge waste of costs while providing better and faster services. Therefore, using a regular process of collecting and disposal of waste is one of the basic needs of developing cities to solve the problem of waste storage and lack of collection and disposal of waste.
Ardabil city as the study area is due to the physical and population development that has experienced over recent years day by day, the population increase and its follower increases the number of locales. Therefore, it is not possible to pay attention to the health of the people of Ardabil city and to observe the preventive aspects before treatment without considering the new systems and methods of collecting and disposal of waste that have been the main cause of pollution in this city and its 100 places.
Methodology
This is an applied research and descriptive-analytical research method. The data of this research have been collected through library studies (books, articles and dissertations) and field studies. The statistical population of this study is the geographical location of 100 neighborhoods in different areas of Ardabil. The raw data obtained from the research were analyzed in the MATLAB programming software environment in the form of a meta-algorithm of colonial competition.
Results and discussion
Normally, in a small space of Ardabil city, garbage collection teams of this city in order to carry out their mission, when reaching multiple intersections and routes, based on one of the factors of chance or probability of choosing one of the routes to continue their activities. They say that naturally this choice will waste money and energy if it is wrong and prolongs the route. The cost of this wrong choice is exacerbated when we encounter an unwanted obstacle in the way of a possible choice, such as blocking city streets due to uncoordinated improvements and reconstructions.
In the continuation of the research, the direction of the movement of municipal waste collection teams in the form of four areas of Ardabil city has been entrusted to MATLAB software. The software, based on instantaneous data and in accordance with the algorithm applied to it, accelerates the optimal path and displays it to the service group occupants. In this case, on the one hand, due to shortening the route and on the other hand, due to not encountering obstacles and changing the route, travel and depreciation costs will be reduced and municipal waste collection teams will reach the relevant places in an acceptable time while satisfying citizens.
Region 1
By defining 200 repetitions, the software gave the best answer with 99% confidence and a time of 30.99 seconds.
Region2
In region 2 of Ardabil city, by defining 200 repetitions, the software obtained the best answer with 93% confidence and in a time of 22.28 seconds.
Region 3
For the roadmap of the garbage collection groups of the neighborhoods located in the 3rd district of Ardabil, the colonial competition algorithm introduced the best answer in the repetition of 200, with a confidence level of 91% and in an approximate time of 31 seconds.
Region 4
The algorithm used in the research, by solving the problem of the traveling salesman, obtained the optimal path for the movement of municipal waste collection machines located in the 4th district of Ardabil in the form of 200 repetitions with a confidence level of 99% and a standstill of 25 seconds.
Conclusion
In this study, a case study was conducted on over 100 urban neighborhoods of Ardabil to the center of municipalities in the four regions of the city in the MATLAB environment. Findings showed that the algorithm used in the research for the 100 neighborhoods located in the 4 areas under study with 200 repetitions and with values ​​of 99, 91, 93 and 97%, respectively, and in a period of 30, 22, 30 and 24 seconds with the most optimal answer (The shortest route in the shortest possible time) was achieved.
In this research, three main questions of efficiency, optimization of travel time and capacity of the study area in the field of routing and improving access were raised and examined in the research process. In the first step, the colonial competition algorithm showed that if combined with the method of the traveling salesman, it can be an effective tool in reducing the movement time of garbage trucks and collecting garbage faster in Ardabil. As a result, these types of meta-heuristic algorithms have good capabilities to optimize travel time. As various researchers such as Ramozi et al. (Solving the problem of vehicle routing using the colonial competition algorithm) and Moslehi and Shakeri (vehicle routing using the colonial competition algorithm) achieved it.
It should be noted that in the ICA algorithm, in addition to connecting the central neighborhood with large and small neighborhoods, the exchange of paths can also take place between individual cities and other villages. In other words, the determination of centrality is directly dependent on the type of programming and the definition of points of origin and destination, and each city or village can be central in a particular situation.This feature allows us to easily select and replace new hotspots as quickly as possible in critical situations, such as wars and natural disasters and the destruction of the central city. In other words, the model presented in this article, in addition to the problem under study, can be used to optimally route the distribution of basic goods in the event of natural and human crises, traffic problems, etc.

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

Urban Wastes, Travelling Salesman Problem (TSP) model, Imperialist Competitive Algorithm (ICA)

مراجع

1. Abdoli, M. A. (1998). Disposal and recycling management of municipal solid waste in Iran. Tehran: Organization of national municipalities, p162.
2. Akhtar, Mahmuda; Basri, Hassan, Scavino, Edgar. (2017). Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization, Waste Management, 61 (3), 117-128.
3. Asghary zadeh, E., jafar Nejad, A., Zandie, M., Jooybar, S. (2017). Explaining the Traffic Modeling Pattern in Vehicle Routing Problems Based on Green Transportation Paradigm (Case Study: Zamzam Company), Journal of Industrial Management, Faculty of Management, University of Tehran, 4 (2): 217-244.
4. Eksioglu, Burak, Vural, Arif. Volkan and Reisman, Arnold. (2009). The vehicle routing problem: A taxonomic review, Computers, Industrial Engineering, 57, 2, 1472- 1483.
5. jycan, kovak. (2005). recycle in Europe. J. of. Waste management world. ISWA publication. 2 (11), 21.
6. Khammar, Gh. (2017). Application of ant community algorithm in optimal routing of intercity relief groups, Journal of Spatial Planning, 7 (23): 41-52.
7. Khammar, Gh., Pasban Essaloo, V., Mojgan, N. (2018). Comparative study of ant community algorithm and genetics in optimal routing (Case study: Parsabad and suburbs), Journal of Transportation Engineering, 8 (3): 343- 383.
8. Lin, Qinying; Song, Houbing; Gui, Xiaolin, Wang, Xiaoping; Su, Saiyu. (2017). A shortest Path Routing algorithm for unmanned aerial systems based on grid position, Journal of Network and Computer Applications, 103 (2): 215- 224.
9. Malandraki, Chryssi, Daskin, Mark. (1992). Time dependent vehicle routing problems, formulations, properties, and heuristic algorithms, Transportation Science, 26 (3), 185-200.
10. Masumi, Z., Sadegniaraki, A., Mesgary, M. (2012). Application of multi-criteria ant colony algorithm in intelligent and user-based transportation systems, Transportation Research Journal, 8 (1): 47- 62.
11. Molaiy, N. (2009). Routing using GIS with emphasis on comparing weighting methods and combining layers with intelligent algorithms, University of Bonab. P 37.
12. Nejat Bakhsh, Y., Ebrahimi, E. (2016). Design of a Logistics Transport Routing Model with Trans-Innovation Algorithm, 4th Levin International Conference on Management Research, Journal of Economics and Accounting, Berlin, Germany.
13. Omrani, G. (2017). Municipal Waste Management, Occupational Safety Research and Training Center, Published by University of Tehran.
14. Pellegrini, P. (2005), Application of two nearest neighbor approachesto a rich vehicle routing problem, TR/IRIDIA..15, IRIDIA,Universite Librede Bruxelles, Brussels, Belgium.
15. Rahaman, Mohammad; Hamilton, Margaret; Salim, Flora. (2017). CAPRA: A contour- based accessible path routing algorithm, Information Sciences, 385 (5): 157-173.
16. Rahimi, A., Rajabi, V. (2017). Provide a combined vehicle routing problem-solving algorithm with simultaneous receipt and delivery of goods, Amir Kabir Scientific Journal - Civil and Environmental Engineering, 48 (4): 375- 385.
17. Sepehry, M. (2014). Designing a model for relocating ambulances, International Journal of Production Management Engineering, 24 (2): 172- 182.
18. Tong, Liangliang; Lau, Francis. (2013). Skew- space garbage collection, Science of Computer Programming, 78 (5): 445- 457.
19. Tuzkaya, U. R. and Onut, S. (2008). A fuzzy analytic network process based approach to transportation-mode selection” between Turkey and Germany: A case study; Inform. Sciences;178 (15), 3133-3146.
20. Yousefi, M., Didevar, F., Rahmati, F. (2012). Application of a colonial competition correction algorithm to solve the itinerant vendor problem, Journal of Advanced Mathematical Modeling, 1 (2): 29- 49.
21. Yousefi, M., Didevar, F., Rahmati, F., Sedigh pour, M. (2012). An effective, comprehensive competitive algorithm for solving the open vehicle routing problem, Transportation Research Journal, 9 (1): 83- 96.
22. Yousefi, Rahmati, F. (2012). Application of Improved Ant Population Algorithm to Solve Vehicle Routing Problem with Simultaneous Receipt and Delivery of Goods, Transportation Research Journal, 8 (2): 183- 198.
23. Zolfaghary, A., Korke Abadi, Z. (2013). Intelligent routing of rescue teams using game theory algorithm (Semnan case study), Journal of Transportation Engineering, 5 (1): 19- 32.