ant colony algorithm
در نشریات گروه صنایع-
مسئله ی چندین فروشنده ی دوره گرد (M T S P) گسترشی مشهور از مسئله ی فروشنده ی دوره گرد (T S P) است. تحقیقات این مسئله بر خلاف مسئله ی T S P که گستردگی آن توجه زیادی را به خود معطوف کرده است، بسیار محدودبوده و ازاین رو الگوریتم جدید ترکیبی موجود به نام الگوریتم ژنتیک مورچگان بهبودیافته (I A C-P G A) ارائه شده است که در آن از یک روش جستجوی محلی به منظور بهبود الگوریتم بهره گرفته شده است. ایده ی اصلی این مقاله آن است که از الگوریتم ژنتیک برای تعیین تعداد شهرها و نقطه ی شروع هر فروشنده بهره بگیریم و سپس از الگوریتم مورچگان برای تعیین بهترین تور استفاده کنیم. نتایج حاصل از مقایسه ی نتایج الگوریتم با دیگر الگوریتم های موجود در ادبیات موضوع و تجزیه و تحلیل آن نشان می دهد که الگوریتم پیشنهادی در حل M T S P در مقیاس بزرگ موثر
کلید واژگان: الگوریتم ژنتیکی پارتنو، الگوریتم کلونی مورچه ها، مسئله ی فروشنده ی دوره گرد چندگانه همراه با الگوریتم ترکیبی بهبودیافته، روش جستجوی محلی -opt2The Multiple Traveling Salesmen Problem (MTSP) is a generalized Traveling Salesmen Problem (TSP). The difference with the traveling salesmen problem is that all cities are visited by multiple salesmen, and each salesman from the city that initiated the move must go back to the same city, which is, in fact, suitable for modeling practical problems in real life than TSP. To solve MTSP with a few starting points, you need the minimum and maximum number of cities each salesman should visit. The total number of cities that salesmen go through should be equal to all cities. In this article, The hybrid Algorithm (IAC-PGA), which combines Parteno Genetic Algorithms (PGA) and Ant Colony (ACO) and uses the 2-opt local search method to improve the algorithm. This method provides full double displacement to improve the response. The main idea in this article is to use the PGA algorithm to search for the best number of cities visited as well as to obtain the starting point of each salesman using the genetic algorithm, and then to use the ACO algorithm to accurately determine the cities visited and the best tour for each salesman. The objective function for this problem is to minimize the distance traveled by all salesmen. For the purpose of analysis, the parameters of each algorithm are selected according to the number of experimental samples in the most appropriate case, and then the results of the algorithm are compared with other algorithms including PGA, Improved PGA (IPGA), Two-part Wolf Pack Search (TWPS), Artificial Bee Colony (ABC), and Invasive Weed Optimization (IWO). Statistics show the algorithm improvement for problem solving. The results of comparative experiments show that the proposed IAC-PGA algorithm is sufficiently effective in solving large-scale MTSP and is not worse than other algorithms on a small scale and performs better than the existing algorithms.
Keywords: Parteno genetic algorithm, ant colony algorithm, multi traveling salesmen problem with improved hybrid algorithm, 2-opt local search method -
مسئله ی مسیریابی وسایل نقلیه، یکی از مهم ترین مسائل مدیریت زنجیره ی تامین است. این اهمیت از آنجا ناشی می شود که تخصیص مطلوب وسایل به مسیرهای مختلف، تاثیر بسیار زیادی بر کاهش هزینه ها دارد. در تحقیق حاضر، این مسئله با درنظرگرفتن شرایط دنیای واقعی ازجمله محدودیت تردد وسایل بررسی می شود. پس از تشریح مسئله و تعریف متغیرها و پارامترهای آن، مدل ریاضی این مسئله توسعه داده می شود. باتوجه به N P-h a r d بودن مسئله، ابتدا جواب بهینه ی مسئله در ابعاد کوچک مشخص می شود. به منظور حل این مسئله در ابعاد متوسط و بزرگ، مدلی مبتنی بر الگوریتم کلونی مورچگان توسعه داده می شود. به منظور اطمینان از عملکرد مدل پیشنهادی، مسائل متنوعی برای آزمون آن طراحی می شود و نتایج مورد ارزیابی قرار می گیرد. همچنین عملکرد الگوریتم پیشنهادی با نتایج حاصل از دو الگوریتم جست وجوی ممنوع (T S) و ژنتیک (G A) نیز مقایسه می شود.
کلید واژگان: مسیریابی وسایل نقلیه، سیستم زنجیره ی تامین، توزیع، الگوریتم کلونی مورچگانSince precise assignment of vehicles to the routs in supply chain network has a great eect on the important results such as cost reduction, on time delivery of the products or services, and customer satisfaction indexes (CSI), the Vehicle Routing Problem (VRP) is one of the most important problems in the supply chain management. For the complexity of this problem in real world, researchers usually ignore some real conditions and restriction in modelling and solving this problem. In this paper, the Vehicle Routing Problem (VRP) considering real conditions, such as vehicle capacity and restriction for vehicles with their movement in some routes, is studied. At rst, the literature review and past studies are presented. Then, the considered problem will be illustrated completely and its parameters and variables will be dened. After that, the mathematical model of the problem is presented considering restriction for movement of the vehicles. This mathematical model will be codedinGAMSsoftware; becausethisproblemisknown as an NP-Hard problem, the mathematical model of the problem is solved just for the small-sized problems. A new model is also presented for the medium- and largesized problems based on ant colony (AC). The parameters of the ant colony are adjusted well in order to increase the eciency of the algorithm. Finally, some diversity test problems are designed considering the important and eective parameters. These test problems are solved in order to evaluate the eciency of the proposed algorithm, and the result shows that the proposed algorithm has a good performance in solving the test problems. Performanceoftheproposedalgorithmisalso compared with two power algorithms tabou search (TA) and genetic algorithm (GA) in solving the test problems. Results show that the proposed algorithm has better performance both in optimality and running time comparison of two other algorithms.
Keywords: Vehicle routhing problem, supply chain system, distribution, ant colony algorithm -
International Journal of Industrial Engineering and Productional Research, Volume:28 Issue: 4, dec 2017, PP 441 -460Considering the high costs of the implementation and maintenance of gas distribution networks in urban areas, optimal design of such networks is vital. Today, urban gas networks are implemented within a tree structure. These networks receive gas from City Gate Stations (CGS) and deliver it to the consumers. This study presents a comprehensive model based on Mixed Integer Nonlinear Programming (MINLP) for the design of urban gas networks taking into account topological limitations, gas pressure and velocity limitations and environmental limitations. An Ant Colony Optimization (ACO) algorithm is presented for solving the problem and the results obtained by an implementation of ACO algorithm are compared with the ones obtained through an iterative method to demonstrate the efficiency of ACO algorithm. A case study of a real situation (gas distribution in Kelardasht, Iran) affirms the efficacy of the proposed approach.Keywords: Designing urban networks, optimization, tree structure, ant colony algorithm, pressure, velocity, metaheuristic algorithms
-
مساله مکان یابی مسیریابی با هدف مشخص نمودن همزمان تصمیمات مربوط به مکان یابی مراکز عرضه و مسیریابی وسایل حمل و تامین هماهنگی مناسب میان این دو مساله مطرح شده و در طراحی شبکه های توزیع یک زنجیره تامین از اهمیت زیادی برخوردار است. این اهمیت از آن جا ناشی می شود که در سیستم های توزیع، هماهنگی مناسب بین مکان یابی مراکز توزیع و مسیریابی وسایل نقلیه، تاثیر بسیار زیادی بر عملکرد سیستم زنجیره تامین داشته و می تواند موجب ارتقاء شاخص های کارایی آن شود. هرچند جهت ساده سازی، این دو مساله معمولا در دو فاز جداگانه بررسی و حل می شوند اما این موضوع باعث از دست رفتن نتایج ایده آل و فاصله گرفتن از جواب بهینه سراسری خواهد شد. در این مقاله، این مساله با در نظر گرفتن ظرفیت و تنوع وسایل حمل و همچنین محدودیت تردد برخی وسایل در بعضی از مسیرها که بیانگر شرایط کاربردی آن می باشد مورد بررسی قرار می گیرد. پس از تشریح مساله موردنظر به همراه متغیرها و پارامترهای مربوط به آن، مدل ریاضی این مساله توسعه داده می شود. این مدل در نرم افزار مدلسازی GAMS کدنویسی شده و باتوجه به NP-Hard بودن مساله، لذا در ابعاد کوچک حل می شود. به منظور حل این مساله در ابعاد بزرگ، مدلی مبتنی بر الگوریتم کلونی مورچگان توسعه داده شده است. در پایان به منظور اطمینان از عملکرد مدل پیشنهادی، مسائل متنوعی جهت تست و ارزیابی آن طراحی شده و نتایج حل این مسائل مورد تجزیه و تحلیل قرار می گیرد.
کلید واژگان: شبکه توزیع، مساله مکان یابی مسیریابی، ظرفیت وسایل حمل، الگوریتم کلونی مورچگانJournal of Industrial Engineering Research in Production Systems, Volume:3 Issue: 5, 2015, PP 91 -105The location routing problem (LRP) is presented with the aim of specifying both routing and location decision simultaneously and coordinate these two matters is very important in designing distribution networks of supply chain. This importance is for that the suitable coordinating between location and routing has a powerfuul affect on supply chain performance in distribution systems and also can improve it’s efficiency indexes. Although for simplifying، these two matters are usually analyzed and solved in two separated phase، but this would cause to lost the ideal benefit and global optimum solution. In this paper، the routing and location problem with considering real word conditions and restrictions like diversity of vehicles and restrictions of some vehicles movement in specified route are investigated concurrently. After presenting summery of previous research، we investigate the problem that mentioned earlier and relevant variables and parameters will be declared. Then mathematical model will be extended. In addition، mathematical model with modeling software GAMS will be implemented. With assuming this problem is kind of NP-hard problem، thus we solve this problem in small scale. In order to solve the considered problem in larg scale، a model will be presented based on ant colony. So with our specific parameters، diverse testing problems will be designed and outcome of these problems will be analyzed to show the algorithm efficiency.Keywords: Distribution Network, Location Routing Problem, Capacitied Vehicle, Ant Colony Algorithm -
The economical determination of lot size with capacity constraints is a frequently complex, problem in the real world. In this paper, a multi-level problem of lotsizing with capacity constraints in a finite planning horizon is investigated. A combination of ant colony algorithm and a heuristic method called shifting technique is proposed for solving the problem. The parameters, including the costs, demands and capacity of resources vary during the time. The goal is to determine the economical lot size value of each product in each period, so that besides fulfilling all the needs of customers, the total cost of the system is minimized. To evaluate the performance of the proposed algorithm, an example is used and the results are compared other algorithms such as: Tabu search (TS), simulated annealing (SA), and genetic algorithm (GA). The results are also compared with the exact solution obtained from the Lagrangian relaxation method. The computational results indicate that the efficiency of the proposed method in comparison to other meta-heuristics.Keywords: Production planning, Capacitated lot, sizing, Ant colony algorithm, Shifting technique
-
مسئله مسیریابی وسایل نقلیه به همراه پنجره های زمانی، در زمره مسائل NP-Complete می باشد، بگونه ای که حتی یافتن یک جواب بهینه برای ابعاد کوچک آن بسیار دشوار و زمانبر است. هدف این مسئله بکارگرفتن ناوگانی از وسایل نقلیه با ظرفیت های معین جهت خدمت دهی به تعداد معینی از مشتریان با تقاضاهای متفاوت و محدودیت های زمانی متفاوت می باشد، بگونه ای که هزینه کمینه شده و ظرفیت ها و نیز پنجره زمانی نقض نگردند. این مسئله تاکنون توسط بسیاری از روش های حل ابتکاری و فراابتکاری مورد حل واقع شده و جوابهای بهینه یا نزدیک به جواب بهینه حاصل شده است. در این مقاله نوع اصلاح شده الگوریتم کلونی مورچگان پیشنهاد گردیده و در آن سعی شده تا حد ممکن از پیچیدگی های محاسباتی اجتناب و سهولت روش حل فراهم گردد؛ البته درنظر گرفتن چنین قابلیتی منجر به از دست دادن مقدار کمی از دقت محاسباتی شده است. با این حال اجرای الگوریتم پیشنهادی بر روی تعدادی از نمونه مسائل Solomon، آشکار نمود که این الگوریتم توانایی تولید جواب های نسبتا خوب را دارا می باشد.
کلید واژگان: مسئله مسیریابی وسایل نقلیه به همراه پنجره های زمانی، الگوریتم کلونی مورچگان، نمونه مسائل SolomonInternational Journal of Industrial Engineering & Production Management, Volume:20 Issue: 2, 2009, P 23Vehicle Routing Problem with Time Windows (VRPTW) is an NP-Complete Optimization Problem. Even finding an optimal solution for small size problems is too hard and time-consuming. The objective of VRPTW is to use a fleet of vehicles with specific capacity to serve a number of customers with dissimilar demands and time window constraints at minimum cost, without violating the capacity and time window constraints. This problem has been solved with a number of heuristic and meta-heuristic solution algorithms and optimal or near optimal solutions gained. In this paper, a modified Ant Colony algorithm is proposed. In this algorithm we tried to simplify the solution procedure and computational complexities of ant colony meta-heuristic. To gain this capability, we sacrificed some computational accuracy. Testing the solution procedure on the Solomon test-problems showed that this algorithm is capable of generating relatively good solutions.Keywords: Vehicle Routing Problem with Time Windows, Ant Colony Algorithm, Solomon test, problems
- نتایج بر اساس تاریخ انتشار مرتب شدهاند.
- کلیدواژه مورد نظر شما تنها در فیلد کلیدواژگان مقالات جستجو شدهاست. به منظور حذف نتایج غیر مرتبط، جستجو تنها در مقالات مجلاتی انجام شده که با مجله ماخذ هم موضوع هستند.
- در صورتی که میخواهید جستجو را در همه موضوعات و با شرایط دیگر تکرار کنید به صفحه جستجوی پیشرفته مجلات مراجعه کنید.