heuristic algorithms
در نشریات گروه صنایع-
مسیریابی وسایل نقلیه، مسیله یی است که تاکنون توسط پژوهشگران متعددی مطالعه شده و توسعه یافته است. در سال های اخیر با توسعه ی فروش های اینترنتی مسیله ی مسیریابی وسایط نقلیه با در نظر گرفتن مکان زمان های پیشنهادی مشتریان، که یکی از زیرشاخه های مسیله ی مسیریابی عمومی وسایط نقلیه است مورد توجه محققین قرار گرفته است. در این مقاله دو مدل ریاضی مبتنی بر گره و مبتنی بر جریان برای مسیله ارایه شده است. نتایج حل مدل نشان می دهد که مدل ریاضی مبتنی بر جریان کارایی بالاتری نسبت به مدل مبتنی بر گره دارد. در ادامه چهار الگوریتم ابتکاری شامل الگوریتم مبتنی بر صرفه جویی سری و موازی، الگوریتم مبتنی بر درج کردن و الگوریتم مبتنی بر نزدیک ترین مشتری بازدید نشده برای مسیله ی طراحی شده است. الگوریتم مبتنی بر درج کردن، در نمونه های کوچک نسبت به جواب بهینه، شش درصد خطا داشته است. در نمونه های بزرگ نیز، عملکرد مناسبی در مقایسه با سایر الگوریتم ها داشته است.
کلید واژگان: مسیریابی وسایل نقلیه، مسیریابی انتخابی وسایل نقلیه، مکان زمان های پیشنهادی مشتریان، پنجره ی زمانی، الگوریتم ابتکاریTransportation is one of the most signi cant issues in the eld of logistics. The development and expansion of urban networks, the increase in population, and the consequent increase in the trac of road networks have led to an increase in the importance and sensitivity of transportation compared to the past. On the other hand, transportation accounts for a signi cant part of any country's Gross National Product (GNP), and a lot of research has been done to improve the transportation situation. One of the most challenging problems in transportation is the Vehicle Routing Problem (VRP). VRP is one of the most important classic optimization problems that has been studied and developed by many researchers since its introduction. One developed form of VRPs is the Generalized Vehicle Routing Problem (GVRP). This problem is relatively new and is one of the novel areas for research. In the generalized vehicle routing problem, the customers are partitioned into clusters, each with a given demand. The objective is to construct a minimum-cost set of delivery routes serving one of the customers in each cluster in a way that the total demand of the customers served by a single vehicle does not exceed the vehicle capacity. In this article, we have considered generalized vehicle routing problem with time windows and sought to minimize the total traveling time of routes. This objective function is a comprehensive expression that includes both distances and waiting times. We have proposed two mathematical formulations for GVRPTW to minimize the total duration of routes. The rst model is a three-dimensional model based on nodes, and the second model is based on ow and is presented by two indices. We have also designed a two-phase heuristic algorithm to solve the problem. In the rst phase, an initial solution is created, and in the second phase, a heuristic algorithm is implemented to improve the constructed solutions. Three di erent approaches are considered to construct the initial solution, and based on these three approaches, four heuristic algorithms are designed. The rst category is based on savings, including both sequential and parallel saving algorithms. The second category is insertionbased heuristics which is analyzed through 25 strategies, and the last category is a time-oriented nearest neighbor heuristic algorithm. Finally, the performances of the proposed algorithms are compared with each other. The results show the good performance of the insertion-based algorithm compared to other algorithms.
Keywords: Vehicle routing problem, selective vehiclerouting problem, location-times of customers, time windows, heuristic algorithms -
The fundamental function of a cellular manufacturing system (CMS) is based on definition and recognition of a type of similarity among parts that should be produced in a planning period. Cell formation (CF) and cell layout design are two important steps in implementation of the CMS. This paper represents a new nonlinear mathematical programming model for dynamic cell formation that employs the rectilinear distance notion to determine the layout in the continuous space. In the proposed model, machines are considered unreliable with a stochastic time between failures. The objective function calculates the costs of inter and intra-cell movements of parts and the cost due to the existence of exceptional elements (EEs), cell reconfigurations and machine breakdowns. Due to the problem complexity, the presented mathematical model is categorized in NP-hardness; thus, a genetic algorithm (GA) is used for solving this problem. Several crossover and mutation strategies are adjusted for GA and parameters are calibrated based on Taguchi experimental design method. The great efficiency of the proposed GA is then demonstrated via comparing with particle swarm optimization (PSO) and the optimum solution via GAMS considering several small/medium and large-sized problems.Keywords: Cellular manufacturing system, Cell formation, Cell layout, Machine reliability, Meta, heuristic algorithms
-
چالش اصلی در حل مسائل فرایند تحلیل سلسله مراتبی فازی، محاسبات فازی و رتبه بندی اعداد فازی با استفاده از روش های مختلفی است که برای این کار وجود دارد. از آنجا که در روش تحلیل فراخ وزن های دقیق عناصر استخراج می شود، نیاز به محاسبات اضافی فازی و رتبه بندی اعداد فازی از بین می رود. این روش تاکنون در تحقیقات بسیار زیادی کاربرد داشته است اما در نوشتار حاضر نشان داده می شود که وزن های این روش صحیح نیست. به منظور رفع نقص روش تحلیل فراخ، در این نوشتار یک روش جدید مبتنی بر الگوریتم های فراابتکاری برای استخراج وزن های دقیق از ماتریس های مقایسات زوجی فازی معرفی می شود. همچنین برای نشان دادن اعتبار روش پیشنهادی،این روش با چهار روش موجود در ادبیات موضوع مقایسه شده که نتایج حاصله نشان دهنده ی اعتبار بالای روش پیشنهادی است.کلید واژگان: فرایند تحلیل سلسله مراتبی، بردار وزن، تصمیم گیری چندمعیاره، الگوریتم های فراابتکاریDifferent methods are provided to deal with imprecise judgments of decision makers for the analytical hierarchy process. Most previous methods, which allow consideration of imprecise judgments as fuzzy numbers, provide the local and global weights of elements as fuzzy numbers too. Local and global fuzzy numbers need additional aggregation, computation and ranking procedures. The global weights may overlap each other and make the ranking of alternatives difficult. As a result, since there are different methods of fuzzy computation and fuzzy ranking, in some problems, we cannot have a unique ranking of fuzzy numbers. In order to overcome this deficiency, one method for solving fuzzy analytical hierarchy process problems and obtaining the crisp priority vector is called extent analysis. As mentioned, the main challenges of solving such problems are the fuzzy computations and ranking of fuzzy numbers, because different computation and ranking of fuzzy numbers may result in the different ranking of alternatives. Since the extent analysis method derives the crisp priority vector from fuzzy comparison matrices, it eliminates the need for additional computation and ranking of fuzzy numbers. This method is used in much research, but, in this paper, it is indicated that the priority vector of this method is not appropriate. To overcome this defect, in this paper, a new meta-heuristic based algorithm is proposed to derive the crisp priority vector from fuzzy comparison matrices. Furthermore, in order to illustrate the proposed method of this paper, it is compared with four methods available in the literature. The computational results indicate that the proposed method is appropriate for deriving the crisp priority vector from fuzzy comparison matrices.Keywords: Analytic hierarchy process, priority vector, multiple criteria decision making, meta, heuristic algorithms
-
Journal of Industrial Engineering and Management Studies, Volume:3 Issue: 1, Winter-Spring 2016, PP 15 -38One of the most important extensions of the capacitated vehicle routing problem (CVRP) is the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) where customers require simultaneous delivery and pick-up service. In this paper, we propose an effective ant colony optimization (EACO) which includes insert, swap and 2-Opt moves for solving VRPSPD that is different with common ant colony optimization (ACO). ACO is a meta-heuristic algorithm inspired by the foraging behavior of real ants. Artificial ants are used to build a solution for the problem by using the pheromone information from previously generated solutions. An extensive numerical experiment is performed on 68 benchmark problem instances involving up to 200 customers available in the literature. The computational result shows that EACO not only presented a very satisfying scalability, but also was competitive with other meta-heuristic algorithms such as tabu search, large neighborhood search, particle swarm optimization and genetic algorithm for solving VRPSPD problems.Keywords: Meta, heuristic algorithms, Simultaneously Pickup, Delivery Goods, Ant Colony Optimization, Vehicle Routing Problem
-
International Journal of Industrial Engineering and Productional Research, Volume:26 Issue: 3, Sep 2015, PP 229 -246This paper addresses a reliable facility location problem with considering facility capacity constraints. In reliable facility location problem some facilities may become unavailable from time to time. If a facility fails, its clients should refer to other facilities by paying the cost of retransfer to these facilities. Hence, the fail of facilities leads to disruptions in facility location decisions and this problem is an attempt to reducing the impact of these disruptions. In order to formulate the problem, a new mixed-integer nonlinear programming (MINLP) model with the objective of minimizing total investment and operational costs is presented. Due to complexity of MINLP model, two different heuristic procedures based on mathematical model are developed. Finally, the performance of the proposed heuristic methods is evaluated through executive numerical example. The numerical results show that the proposed heuristic methods are efficient and provide suitable solutions.Keywords: Facility failure, Heuristic algorithms, Reliable capacitated facility location, Uncertainty
-
Maximizing the nurses’ preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm
The nurse scheduling problem (NSP) has received a great amount of attention in recent years. In the NSP, the goal is to assign shifts to the nurses in order to satisfy the hospital’s demand during the planning horizon by considering different objective functions. In this research, we focus on maximizing the nurses’ preferences for working shifts and weekends off by considering several important factors such as hospital’s policies, labor laws, governmental regulations, and the status of nurses at the end of the previous planning horizon in one of the largest hospitals in Iran i.e., Milad Hospital. Due to the shortage of available nurses, at first, the minimum total number of required nurses is determined. Then, a mathematical programming model is proposed to solve the problem optimally. Since the proposed research problem is NP-hard, a meta-heuristic algorithm based on simulated annealing (SA) is applied to heuristically solve the problem in a reasonable time. An initial feasible solution generator and several novel neighborhood structures are applied to enhance performance of the SA algorithm. Inspired from our observations in Milad hospital, random test problems are generated to evaluate the performance of the SA algorithm. The results of computational experiments indicate that the applied SA algorithm provides solutions with average percentage gap of 5.49 % compared to the upper bounds obtained from the mathematical model. Moreover, the applied SA algorithm provides significantly better solutions in a reasonable time than the schedules provided by the head nurses.
Keywords: Health systems . Nurse scheduling problem .Preference scheduling . Mathematical programming . Neighborhood structure . Meta, heuristic algorithms -
Cellular manufacturing system, an application of group technology, has been considered as an effective method to obtain productivity in a factory. For design of manufacturing cells, several mathematical models and various algorithms have been proposed in literature. In the present research, we propose an improved version of discrete particle swarm optimization (PSO) to solve manufacturing cell formation problem effectively. When a local optimal solution is reached with PSO, all particles gather around it, and escaping from this local optimum becomes difficult. To avoid premature convergence of PSO, we present a new hybrid evolutionary algorithm, called discrete particle swarm optimization-simulated annealing (DPSO-SA), based on the idea that PSO ensures fast convergence, while SA brings search out of local optimum. To illustrate the behavior of the proposed model and verify the performance of the algorithm, we introduce a number of numerical examples. The performance evaluation shows the effectiveness of the DPSO-SA.Keywords: Particle swarm optimization, Simulated Annealing, Cellular manufacturing problem, Meta, heuristic algorithms
-
International Journal of Industrial Engineering and Productional Research, Volume:25 Issue: 2, Jun 2014, PP 139 -149periodic vehicle routing problem focuses on establishing a plan of visits to clients over a given time horizon so as to satisfy some service level while optimizing the routes used in each time period. This paper presents a new effective heuristic algorithm based on data mining tools for periodic vehicle routing problem (PVRP). The related results of proposed algorithm are compared with the results obtained by best Heuristics and meta-heuristics algorithms in the literature. Computational results indicate that the algorithm performs competitive in the accuracy and its small amount of solving time point of views.Keywords: Periodic vehicle routing problem, Heuristic algorithms, data mining
-
Journal of Optimization in Industrial Engineering, Volume:6 Issue: 12, Winter and Spring 2013, PP 61 -77In today''s globalization, an effective integration of production and distribution plans into a unified framework is crucial for attaining competitive advantage. This paper addresses an integrated multi-product and multi-time period production/distribution planning problem for a two-echelon supply chain subject to the real-world variables and constraints. It is assumed that all transportations are outsourced to third-party logistics providers and all-unit quantity discounts in transportation costs are taken into consideration. The problem has been formulated as a multi-objective mixed-integer linear programming model which attempts to simultaneously minimize total delivery time and total transportation costs. Due to the complexity of the considered problem, genetic algorithm (GA) and particle swarm optimization (PSO) algorithm are developed within the LP-metric method and desirability function framework for solving the real-sized problems in reasonable computational time. As the performance of meta-heuristic algorithms is significantly influenced by calibrating their parameters, Taguchi methodology has been used to tune the parameters of the developed algorithms. Finally, the efficiency and applicability of the proposed model and solution methodologies are demonstrated through several problems in different sizesKeywords: supply chain, Production, distribution planning, Multi, objective optimization, Meta, heuristic algorithms, Transportation cost discount
-
در این مقاله، مسئله تعیین ترکیب تولید محصولات با استفاده از رویکرد نظریه محدودیت ها مورد بررسی قرار می گیرد. این رویکرد، یکی از موثرترین رویکردهای ابتکاری معرفی شده در حل این مسئله است. با وجود آنکه تعداد روش های ابتکای و فراابتکاری ارائه شده در ادبیات موضوع این مسئله با رویکرد ذکرشده اندک نیست، ولی همچنان دستیابی به جواب بهینه و کیفیت آن در زمانی مقبول از دغدغه های مطرح در این حوزه به شمار می آید. در مقاله حاضر، الگوریتم موثری برای تولید جواب های اولیه با کیفیت مطلوب به منظور آغاز فرآیندهای حل ابتکاری و یا فراابتکاری موجود با بهره گیری از مفاهیم تصمیم گیری گروهی ارائه می شود. در نهایت، برتری الگوریتم پیشنهادی بر دو نمونه از الگوریتم های موجود در ادبیات موضوع مسئله تعیین ترکیب تولید محصولات در بخش مثال عددی نشان داده شده است.
کلید واژگان: تولید جواب اولیه، روش های ابتکاری، نظریه محدودیت ها، تصمیم گیری گروهی، مسئله تعیین ترکیب تولیدThis paper deals with the product mix problem using the concept of Theory Of Constraints (TOC). Theory of constraints is one of the most efficient approaches which have been applied to solve the product mix problem heuristically. Although there are numerous heuristic and meta-heuristics to solve this problem, finding the optimal solution in a reasonable time is still a challenging issue. In this paper, a novel procedure inspired by multi-agent decision making concepts, is developed to generate better initial solutions upon which the existing TOC-based product mix algorithms can reach solutions with better quality. The superiority of the proposed procedure is validated by two existing algorithms through a well-known problem instance in the body of literature.Keywords: Heuristic algorithms, Multi, agent decision, making, Theory of constraints, Initial solution generation, Product mix problem -
تکنیک خوشه بندی از مهم ترین تکنیک های داده کاوی و شاخه ای از تحلیل آماری چند متغیره بوده و روشی برای گروه بندی داده های مشابه در خوشه های یکسان است. با بزرگ تر شدن بانک های داده ای، تلاش محققان برای یافتن روش های خوشه بندی کارا و موثر متمرکز شده است تا از این راه بتوانند زمینه تصمیم گیری سریع و منطبق با واقعیت را فراهم آورند. بدین منظور، در این مقاله تکنیک خوشه بندی بهبود یافته سیستم کلونی مورچگان (1IASC) با هدف ارائه یک الگوریتم خوشه بندی سریع و با دقت بالا پیشنهاد شده است. نتایج حاصل از اجرای الگوریتم روی داده های زلزله ایران، نشان از دقت و سرعت الگوریتم و کاهش زمان اجرا دارد. همچنین الگوریتم پیشنهادی قادر است داده های پرت را شناسایی کند.
کلید واژگان: تحلیل خوشه بندی، سیستم کلونی مورچگان، زلزله، الگوریتم های فراابتکاریClustering technique is one of the most important techniques of data mining and is the branch of multivariate statistical analysis and a method for grouping similar data in to same clusters. With the databases getting bigger, the researchers try to find efficient and effective clustering methods so that they can make fast and real decisions. Thus, in this paper, we proposed an improved ant system-based clustering algorithm (IASC) in order to providing the fast clusters with high accuracy. The goal of clustering analysis is to group similar objects together. There are many methods being applied in clustering analysis, like hierarchical clustering, partition-based clustering, density-based clustering, and artificial intelligence-based clustering. The ant colony system (ACS) is one of the newest meta-heuristics for combinatorial optimization problems, and this study uses the ant colony system to find the clusters effectively. The IASC algorithm is including four sub-procedures, that is Divide, Agglomerate_obj, Agglomerate, and Remove. First, initialize the parameters and group all the objects as a cluster. And then the sub-procedure Divide will divide the cluster into several sub-clusters and some object which does not belong to any sub-clusters through the consistency of the pheromone and some criterion. After Divide, the Agglomerate_obj is the next step at this algorithm in order to agglomerate the objects into the suitable sub-cluster. Fourth, Agglomerate is the sub-procedure to merge the similar two sub-clusters into a cluster. And then run Agglomerate_obj again. Sixth, after agglomerating the similar object into the suitable sub-cluster, the Remove sub-procedure tries to remove the un-similar from sub-cluster. Calculate the total within cluster variance (TWCV). If TWCV is not changed, stop the procedure. Otherwise, repeat the sub-procedure Divide, Agglomerate_obj, Agglomerate, Agglomerate_obj, Remove until TWCV is not changed. The implementation results on the Iran earthquake data show that the proposed method is able to provide more accurate and fast clusters and to determine the outliers. The computational time is also reduced.Keywords: Clustering analysis, Ant colony system, Meta, heuristic algorithms, Earthquake -
The Travelling Salesmen Problem (TSP) is one of the most important and famous combinational optimization problems that aim to find the shortest tour. In this problem, the salesman starts to move from an arbitrary place called depot and after visiting all nodes, finally comes back to depot. Solving this problem seems hard because program statement is simple and leads this problem belonging to NP-hard programs.In this paper, the researchers present a modified Elite Ant System (EAS) which is different from common EAS. There is a linear function used here for increasing coefficient pheromone of the best route activated when a better solution is achieved. This process will avoid the premature convergence and makes better solutions. The results on several standard instances show that this new algorithm would gain more efficient solutions compared to other algorithms.
Keywords: Ant Colony Optimization, Traveling Salesman Problem, NP, hard Problems, Meta, heuristic Algorithms -
در این مقاله، مساله زمانبندی جریان کارگاهی جایگشتی دوباره وارد شونده با هدف کمینه سازی حداکثر دیرکرد کارها مورد بررسی قرار می گیرد. محیط جریان کارگاهی دوباره وارد شونده (RFS) همان جریان کارگاهی است با این تفاوت که کارها، ماشین های مشخصی را بیش از یک بار ملاقات می کنند. در نوع RFS، اگر ترتیب کار روی هر ماشین در هر سطح یکسان باشد، به چنین مسایلی، مساله جریان کارگاهی جایگشتی دوباره وارد شونده (RPFS) عنوان می گردد. در این مقاله، ابتدا مدل ریاضی مساله کمینه سازی حداکثر دیرکرد کارها در RPFS چند ماشینه، توسعه داده می شود. برای حل این مساله، سه الگوریتم فراابتکاری مبتنی بر الگوریتم ژنتیک، شبیه سازی تبرید و جستجوی ممنوع طراحی و بکار گرفته می شود. الگوریتم های فراابتکاری همچنین با حل های بهینه ایجاد شده توسط رویکرد برنامه ریزی عدد صحیح مقایسه می گردند. نتایج آزمایشی نشان می دهد که الگوریتم ژنتیک در اکثر موارد کارایی بهتری نسبت به الگوریتم های تست شده دیگر دارد.
کلید واژگان: زمانبندی، جریان کارگاهی جایگشتی دوباره واردشونده، حداکثر دیرکرد کارها، الگوریتم های فراابتکاریInternational Journal of Industrial Engineering & Production Management, Volume:21 Issue: 4, 2011, P 179This investigation considers a reentrant permutation flowshop scheduling problem whose performance criterion is maximum tardiness. The reentrant flowshop (RFS) is a natural extension of the classical flowshop by allowing a job to visit certain machines more than once. The RFS scheduling problem, in which the job order is the same for each machine in each layer, is called a reentrant permutation flowshop (RPFS) problem. In this paper, a mathematical model is extended to solve the given problem minimizing the maximum tardiness on an m-machine RPFS problem. This problem is solved by three meta-heuristic algorithms, namely genetic algorithm, simulated annealing and tabu search. The results of these algorithms are compared to the optimal solutions obtained by the integer programming approach. The experimental results show that the genetic algorithm has a better performance than the others tested.Keywords: Flowshop scheduling, Reentrant permutation, Maximum tardiness, Meta, heuristic algorithms -
در این مقاله، مساله زمانبندی تولید کارگاه منعطف (Flexible Job Shop) با تعریف جدیدی از انعطاف پذیری مورد بررسی قرار می گیرد. در این نوع انعطاف پذیری برای مساله فرض می شود که در هر ایستگاه عملیاتی چند ماشین وجود دارند که کارها در هر ایستگاه می توانند به یکی از آنها تخصیص داده شود. تابع هدف کمینه سازی بازه ساخت (make span) است. ابتدا مدل ریاضی مساله ارائه شده و سپسNP-hard بودن مساله نشان داده می شود. بعلت NP-hard بودن مساله استفاده از روش های دقیق برای حل آن در زمان چندجمله ای ممکن نیست و باید از الگوریتمهای ابتکاری برای حل آن استفاده نمود. به این منظور دو الگوریتم ابتکاری به نامهای H1 و H2 به ترتیب برای مسائل با ابعاد بزرگ و معمولی برای حل مساله ارائه می شود. بعلت اینکه این مساله تا کنون در ادبیات موضوع مورد مطالعه قرار نگرفته است، معیار مناسبی برای ارزیابی الگوریتم های ارائه شده وجود ندارد. بنابراین به منظور ارزیابی الگوریتمهای ارائه شده، سه الگوریتم ابتکاری با نامهای H3، H4 و H5 و همچنین یک کران پایین برای آن ارائه می شود و نتایج الگوریتمهای H1 و H2 با آنها مقایسه شده است. نتایج محاسبات نشان می دهد که الگوریتم پیشنهادی H2برای مسائل با ابعاد کوچک، جوابهای بهتری را نسبت به الگوریتمهای دیگر ارائه می دهد. اما در مسائل با ابعاد بزرگ H1 به طور مجانبی کاراتر از H2 است. همچنین کارائی الگوریتم H3 پایین تر از سایر الگوریتمها است.
کلید واژگان: تولید کارگاهی انعطاف پذیر_ ماشینهای موازی، مدلسازی ریاضی، الگوریتمهای ابتکاریInternational Journal of Industrial Engineering & Production Management, Volume:20 Issue: 2, 2009, P 11In this paper the problem of job shop scheduling with parallel machines in each stages is discussed. The objective is to minimize the maximum completion time (makespan).�This problem is a combination of two classic problems of job shop and parallel machines which in this case parallel machines has been used as kind of flexibility in the job shop problem. The review of literature has shown that this problem has not been discussed yet. After presenting the mathematical mode, heuristic algorithms are used for solving this NP-hard problem. Regarding this, five algorithms are presented and a lower bound is developed. Finally all these algorithms have been analyzed. According to results the proposed algorithm of H2 works better than the others when there are few jobs. As the number of jobs increases H1 is more efficient than H2 asymptotically. Also the efficiency of H3 algorithm is the worst among the rest.Keywords: Flexible Job Shop, Parallel Machines, Mathematical Modeling, Heuristic Algorithms
- نتایج بر اساس تاریخ انتشار مرتب شده‌اند.
- کلیدواژه مورد نظر شما تنها در فیلد کلیدواژگان مقالات جستجو شده‌است. به منظور حذف نتایج غیر مرتبط، جستجو تنها در مقالات مجلاتی انجام شده که با مجله ماخذ هم موضوع هستند.
- در صورتی که می‌خواهید جستجو را در همه موضوعات و با شرایط دیگر تکرار کنید به صفحه جستجوی پیشرفته مجلات مراجعه کنید.
©2000-2025 magiran.com All Rights Reserved.