To see the other types of publications on this topic, follow the link: Traveling-salesman problem. Genetic algorithms. Heuristic programming.
Journal articles on the topic 'Traveling-salesman problem. Genetic algorithms. Heuristic programming'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 35 journal articles for your research on the topic 'Traveling-salesman problem. Genetic algorithms. Heuristic programming.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Zhou, Ai-Hua, Li-Peng Zhu, Bin Hu, et al. "Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming." Information 10, no. 1 (2018): 7. http://dx.doi.org/10.3390/info10010007.
Full textAbstract:
The traveling-salesman problem can be regarded as an NP-hard problem. To better solve the best solution, many heuristic algorithms, such as simulated annealing, ant-colony optimization, tabu search, and genetic algorithm, were used. However, these algorithms either are easy to fall into local optimization or have low or poor convergence performance. This paper proposes a new algorithm based on simulated annealing and gene-expression programming to better solve the problem. In the algorithm, we use simulated annealing to increase the diversity of the Gene Expression Programming (GEP) population and improve the ability of global search. The comparative experiments results, using six benchmark instances, show that the proposed algorithm outperforms other well-known heuristic algorithms in terms of the best solution, the worst solution, the running time of the algorithm, the rate of difference between the best solution and the known optimal solution, and the convergent speed of algorithms.
2
Abdul-Niby, M., M. Alameen, A. Salhieh, and A. Radhi. "Improved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming." Engineering, Technology & Applied Science Research 6, no. 2 (2016): 927–30. http://dx.doi.org/10.48084/etasr.627.
Full textAbstract:
The Traveling Salesman Problem (TSP) is an integer programming problem that falls into the category of NP-Hard problems. As the problem become larger, there is no guarantee that optimal tours will be found within reasonable computation time. Heuristics techniques, like genetic algorithm and simulating annealing, can solve TSP instances with different levels of accuracy. Choosing which algorithm to use in order to get a best solution is still considered as a hard choice. This paper suggests domain reduction as a tool to be combined with any meta-heuristic so that the obtained results will be almost the same. The hybrid approach of combining domain reduction with any meta-heuristic encountered the challenge of choosing an algorithm that matches the TSP instance in order to get the best results.
3
da Silva, Felipe Augusto Moreira, Antonio Carlos Moretti, and Anibal Tavares de Azevedo. "A Scheduling Problem in the Baking Industry." Journal of Applied Mathematics 2014 (2014): 1–14. http://dx.doi.org/10.1155/2014/964120.
Full textAbstract:
This paper addresses a scheduling problem in an actual industrial environment of a baking industry where production rates have been growing every year and the need for optimized planning becomes increasingly important in order to address all the features presented by the problem. This problem contains relevant aspects of production, such as parallel production, setup time, batch production, and delivery date. We will also consider several aspects pertaining to transportation, such as the transportation capacity with different vehicles and sales production with several customers. This approach studies an atypical problem compared to those that have already been studied in literature. In order to solve the problem, we suggest two approaches: using the greedy heuristic and the genetic algorithm, which will be compared to small problems with the optimal solution solved as an integer linear programming problem, and we will present results for a real example compared with its upper bounds. The work provides us with a new mathematical formulation of scheduling problem that is not based on traveling salesman problem. It considers delivery date and the profit maximization and not the makespan minimization. And it also provides an analysis of the algorithms runtime.
4
Ahmadi, Bilal, and Devi Jayawati. "RANCANG BANGUN DECISION SUPPORT SYSTEM UNTUK PEMILIHAN RUTE PENGIRIMAN PAKET PADA PERUSAHAAN PENYEDIA JASA LOGISTIK." Jurnal Manajemen Industri dan Logistik 1, no. 2 (2018): 101–10. http://dx.doi.org/10.30988/jmil.v1i2.10.
Full textAbstract:
Traveling Salesman Problem (TSP) is a well-known route optimization problem in which a set of customers is visited only once and all demands are satisfied within single route. Package delivery by a courier company can be considered into this type of problem. While many of the previous research had been conducted, the application of the solutions were limited due to unreal distance measure. This paper developed a decision support system for route optimization using free online maps from Google and Google Maps Application Programming Interface (API). Genetic Algorithm was employed to generate solutions within relatively short time. Furthermore, the solutions was viewed as a function of distance and time. There were some limitations from Google in case of acquiring distance data with the free of charge mechanism. Future research can tackle this backdraw by putting more customer points. Other heuristic methods could also be used for comparison purpose
5
Jafarzadeh, H., N. Moradinasab, and M. Elyasi. "An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem." Engineering, Technology & Applied Science Research 7, no. 6 (2017): 2260–65. http://dx.doi.org/10.48084/etasr.1570.
Full textAbstract:
The generalized traveling salesman problem (GTSP) deals with finding the minimum-cost tour in a clustered set of cities. In this problem, the traveler is interested in finding the best path that goes through all clusters. As this problem is NP-hard, implementing a metaheuristic algorithm to solve the large scale problems is inevitable. The performance of these algorithms can be intensively promoted by other heuristic algorithms. In this study, a search method is developed that improves the quality of the solutions and competition time considerably in comparison with Genetic Algorithm. In the proposed algorithm, the genetic algorithms with the Nearest Neighbor Search (NNS) are combined and a heuristic mutation operator is applied. According to the experimental results on a set of standard test problems with symmetric distances, the proposed algorithm finds the best solutions in most cases with the least computational time. The proposed algorithm is highly competitive with the published until now algorithms in both solution quality and running time.
6
Saharidis, Georgios K. D. "Review of Solution Approaches for the Symmetric Traveling Salesman Problem." International Journal of Information Systems and Supply Chain Management 7, no. 1 (2014): 73–87. http://dx.doi.org/10.4018/ijisscm.2014010105.
Full textAbstract:
In this paper, the main known exact and heuristic solution approaches and algorithms for the symmetric Traveling Salesman Problem (TSP), published after 1992, are surveyed. The paper categorize the most important existing algorithm to 6 main groups: i) Genetic algorithms, ii) Ant colony methods, iii) Neural Methods, iv) Local search algorithms and Tabu search, v) Lagrangian methods and vi) Branch and bound and branch & cut algorithms.
7
Oltean, Mihai. "Evolving Evolutionary Algorithms Using Linear Genetic Programming." Evolutionary Computation 13, no. 3 (2005): 387–410. http://dx.doi.org/10.1162/1063656054794815.
Full textAbstract:
A new model for evolving Evolutionary Algorithms is proposed in this paper. The model is based on the Linear Genetic Programming (LGP) technique. Every LGP chromosome encodes an EA which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization, the Traveling Salesman Problem and the Quadratic Assignment Problem are evolved by using the considered model. Numerical experiments show that the evolved Evolutionary Algorithms perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.
8
El Hassani, Hicham, Said Benkachcha, and Jamal Benhra. "New Genetic Operator (Jump Crossover) for the Traveling Salesman Problem." International Journal of Applied Metaheuristic Computing 6, no. 2 (2015): 33–44. http://dx.doi.org/10.4018/ijamc.2015040103.
Full textAbstract:
Inspired by nature, genetic algorithms (GA) are among the greatest meta-heuristics optimization methods that have proved their effectiveness to conventional NP-hard problems, especially the traveling salesman problem (TSP) which is one of the most studied supply chain management problems. This paper proposes a new crossover operator called Jump Crossover (JMPX) for solving the travelling salesmen problem using a genetic algorithm (GA) for near-optimal solutions, to conclude on its efficiency compared to solutions quality given by other conventional operators to the same problem, namely, Partially matched crossover (PMX), Edge recombination Crossover (ERX) and r-opt heuristic with consideration of computational overload. The authors adopt a low mutation rate to isolate the search space exploration ability of each crossover. The experimental results show that in most cases JMPX can remarkably improve the solution quality of the GA compared to the two existing classic crossover approaches and the r-opt heuristic.
9
Pál, Károly F. "Genetic algorithms for the traveling salesman problem based on a heuristic crossover operation." Biological Cybernetics 69, no. 5-6 (1993): 539–46. http://dx.doi.org/10.1007/bf01185425.
Full text
10
Hamdan, Basma, Hamdi Bashir, and Ali Cheaitou. "A novel clustering method for breaking down the symmetric multiple traveling salesman problem." Journal of Industrial Engineering and Management 14, no. 2 (2021): 199. http://dx.doi.org/10.3926/jiem.3287.
Full textAbstract:
Purpose: This study proposes a new two-stage clustering method to break down the symmetric multiple traveling salesman problem (mTSP) into several single standard traveling salesman problems, each of which can then be solved separately using a heuristic optimization algorithm.Design/methodology/approach: In the initial stage, a modified form of factor analysis is used to identify clusters of cities. In the second stage, the cities are allocated to the identified clusters using an integer-programming model. A comparison with the k-means++ clustering algorithm, one of the most popular clustering algorithms, was made to evaluate the performance of the proposed method in terms of four objective criteria.Findings: Computational results and comparison on 63 problems revealed that the proposed method is promising for producing quality clusters and thus for enhancing the performance of heuristic optimization algorithms in solving the mTSP.Originality/value: Unlike previous studies, this study tackles the issue of improving the performance of clustering-based optimization approaches in solving the mTSP by proposing a new clustering method that produces better cluster solutions rather than by proposing a new or improved version of a heuristic optimization algorithm for finding optimal routes.
11
Fachini, Ramon Faganello, and Vinícius Amaral Armentano. "Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows." Optimization Letters 14, no. 3 (2018): 579–609. http://dx.doi.org/10.1007/s11590-018-1342-y.
Full text
12
Tesfaldet, Bereket T., and Augusto Y. Hermosilla. "A Lamarckian Genetic Algorithm Applied to the Travelling Salesman Problem." Advances in Complex Systems 02, no. 04 (1999): 431–57. http://dx.doi.org/10.1142/s0219525999000229.
Full textAbstract:
Genetic Algorithms (GAs) comprise a class of adaptive heuristic search methods analogous to genetic inheritance and Darwinian strife for survivial of individuals within a population. Today, GAs are widely used to solve complex optimization problems, including ill-conditioned and NP-complete types arising in business, commerce, engineering, large-scale industries, and many other areas. To address these wide areas of applications and to improve upon their drawbacks, many variations and modifications of GAs have been proposed. The GA variation proposed in this paper has four basic operators: reproduction, recombination and two mutation operators, particularly applied to the famous and extensively studied Traveling Salesman Problem (TSP) in large-scale combinatorial optimization. Three of the operators use diversity information (standard deviation of costs) from the current population to adjust the diversity of the next population. The fourth one is an introduced new mutation operator called p-displacement that simulates the Lamarckian evolutionary learning and training concepts of gene improvement to bring chromosomes to their local optimum. We call the proposed GA: Lamarckian Genetic Algorithm-Traveling Salesman Problem (LGA-TSP). Emprical results show performance improvements compared to the classic and other modified GAs, as well as simulated annealing.
13
Zaman, A. G. M., Sajib Hasan, and Mohammad Samawat Ulla. "Evaluation of TSP for Emergency Routing." International Journal of Information Technology and Computer Science 13, no. 1 (2021): 44–53. http://dx.doi.org/10.5815/ijitcs.2021.01.03.
Full textAbstract:
The paper considers the symmetric traveling salesman problem and applies it to sixty-four (64) districts of Bangladesh (with geographic coordinates) as a new instance of the problem of finding an optimized route in need of emergency. It approached three different algorithms namely Integer Linear Programming, Nearest-neighbor, and Metric TSP as exact, heuristic, or approximate methods of solving the NP-hard class of problem to model the emergency route planning. These algorithms have been implanted using computer codes, used IBM ILOG CPLEX parallel optimization, visualized using Geographic Information System tools. The performance of these algorithms also has been evaluated in terms of computational complexity, their run-time, and resulted tour distance using exact, approximate, and heuristic methods to find the best fit of route optimization in emergence thus contributing to the field of combinatorial optimization.
14
Xu, Liang, Yao Wang, Lin Liu, and Jiaxing Wang. "Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints." Mathematical Problems in Engineering 2016 (2016): 1–8. http://dx.doi.org/10.1155/2016/5040513.
Full textAbstract:
A new problem arises when an automated guided vehicle (AGV) is dispatched to visit a set of customers, which are usually located along a fixed wire transmitting signal to navigate the AGV. An optimal visiting sequence is desired with the objective of minimizing the total travelling distance (or time). When precedence constraints are restricted on customers, the problem is referred to as traveling salesman problem on path with precedence constraints (TSPP-PC). Whether or not it is NP-complete has no answer in the literature. In this paper, we design dynamic programming for the TSPP-PC, which is the first polynomial-time exact algorithm when the number of precedence constraints is a constant. For the problem with number of precedence constraints, part of the input can be arbitrarily large, so we provide an efficient heuristic based on the exact algorithm.
15
Ismkhan, Hassan, and Kamran Zamanifar. "Developing Programming Tools to Handle Traveling Salesman Problem by the Three Object-Oriented Languages." Applied Computational Intelligence and Soft Computing 2014 (2014): 1–17. http://dx.doi.org/10.1155/2014/137928.
Full textAbstract:
The traveling salesman problem (TSP) is one of the most famous problems. Many applications and programming tools have been developed to handle TSP. However, it seems to be essential to provide easy programming tools according to state-of-the-art algorithms. Therefore, we have collected and programmed new easy tools by the three object-oriented languages. In this paper, we present ADT (abstract data type) of developed tools at first; then we analyze their performance by experiments. We also design a hybrid genetic algorithm (HGA) by developed tools. Experimental results show that the proposed HGA is comparable with the recent state-of-the-art applications.
16
Taher, Ali Abdul Kadhim, and Suhad Malallah Kadhim. "Improvement of genetic algorithm using artificial bee colony." Bulletin of Electrical Engineering and Informatics 9, no. 5 (2020): 2125–33. http://dx.doi.org/10.11591/eei.v9i5.2233.
Full textAbstract:
Genetic algorithm (GA) is a part of evolutionary computing that simulates the theory of evolution and natural selection, where this technique depends on a heuristic random search. This algorithm reflects the operation of natural selection, where the fittest individuals are chosen for reproduction so that they produce offspring of the next generation. This paper proposes a method to improve GA using artificial bee colony (GABC). This proposed algorithm was applied to random number generation (RNG), and travelling salesman problem (TSP). The proposed method used to generate initial populations for GA rather than the random generation that used in traditional GA. The results of testing on RNG show that the proposed GABC was better than traditional GA in the mean iteration and the execution time. The results of testing TSP show the superiority of GABC on the traditional GA. The superiority of the GABC is clear in terms of the percentage of error rate, the average length route, and obtaining the shortest route. The programming language Python3 was used in programming the proposed methods.
17
Yousefikhoshbakht, Majid, Nasrin Malekzadeh, and Mohammad Sedighpour. "Solving the Traveling Salesman Problem Based on The Genetic Reactive Bone Route Algorithm whit Ant Colony System." International Journal of Production Management and Engineering 4, no. 2 (2016): 65. http://dx.doi.org/10.4995/ijpme.2016.4618.
Full textAbstract:
<p>The TSP is considered one of the most well-known combinatorial optimization tasks and researchers have paid so much attention to the TSP for many years. In this problem, a salesman starts to move from an arbitrary place called depot and after visits all of the nodes, finally comes back to the depot. The objective is to minimize the total distance traveled by the salesman. Because this problem is a non-deterministic polynomial (NP-hard) problem in nature, a hybrid meta-heuristic algorithm called REACSGA is used for solving the TSP. In REACSGA, a reactive bone route algorithm that uses the ant colony system (ACS) for generating initial diversified solutions and the genetic algorithm (GA) as an improved procedure are applied. Since the performance of the Metaheuristic algorithms is significantly influenced by their parameters, Taguchi Method is used to set the parameters of the proposed algorithm. The proposed algorithm is tested on several standard instances involving 24 to 318 nodes from the literature. The computational result shows that the results of the proposed algorithm are competitive with other metaheuristic algorithms for solving the TSP in terms of better quality of solution and computational time respectively. In addition, the proposed REACSGA is significantly efficient and finds closely the best known solutions for most of the instances in which thirteen best known solutions are also found.</p>
18
Bouzarth, Elizabeth L., Richard J. Forrester, Kevin R. Hutson, et al. "A Comparison of Algorithms for Finding an Efficient Theme Park Tour." Journal of Applied Mathematics 2018 (October 16, 2018): 1–14. http://dx.doi.org/10.1155/2018/2453185.
Full textAbstract:
The problem of efficiently touring a theme park so as to minimize the amount of time spent in queues is an instance of the Traveling Salesman Problem with Time-Dependent Service Times (TSP-TS). In this paper, we present a mixed-integer linear programming formulation of the TSP-TS and describe a branch-and-cut algorithm based on this model. In addition, we develop a lower bound for the TSP-TS and describe two metaheuristic approaches for obtaining good quality solutions: a genetic algorithm and a tabu search algorithm. Using test instances motivated by actual theme park data, we conduct a computational study to compare the effectiveness of our algorithms.
19
Paul, Victer, Ganeshkumar C, and Jayakumar L. "Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA Traveling Salesman Problems Based Assessment." International Journal of Applied Metaheuristic Computing 10, no. 2 (2019): 55–92. http://dx.doi.org/10.4018/ijamc.2019040103.
Full textAbstract:
Genetic algorithms (GAs) are a population-based meta-heuristic global optimization technique for dealing with complex problems with a very large search space. The population initialization is a crucial task in GAs because it plays a vital role in the convergence speed, problem search space exploration, and also the quality of the final optimal solution. Though the importance of deciding problem-specific population initialization in GA is widely recognized, it is hardly addressed in the literature. In this article, different population seeding techniques for permutation-coded genetic algorithms such as random, nearest neighbor (NN), gene bank (GB), sorted population (SP), and selective initialization (SI), along with three newly proposed ordered-distance-vector-based initialization techniques have been extensively studied. The ability of each population seeding technique has been examined in terms of a set of performance criteria, such as computation time, convergence rate, error rate, average convergence, convergence diversity, nearest-neighbor ratio, average distinct solutions and distribution of individuals. One of the famous combinatorial hard problems of the traveling salesman problem (TSP) is being chosen as the testbed and the experiments are performed on large-sized benchmark TSP instances obtained from standard TSPLIB. The scope of the experiments in this article is limited to the initialization phase of the GA and this restricted scope helps to assess the performance of the population seeding techniques in their intended phase alone. The experimentation analyses are carried out using statistical tools to claim the unique performance characteristic of each population seeding techniques and best performing techniques are identified based on the assessment criteria defined and the nature of the application.
20
Gladchenko, E. A., O. N. Saprykin, and A. N. Tikhonov. "Optimization of urban freight transportation based on evolutionary modelling." Information Technology and Nanotechnology, no. 2416 (2019): 95–103. http://dx.doi.org/10.18287/1613-0073-2019-2416-95-103.
Full textAbstract:
Logistics problems require special attention, because every year they become more complicated and multivariable. On the one hand, a supply chain management includes incessant monitoring of such issues as requests elaboration, paths determination, routing of shipments, multimodal choice, set up of transhipments, fleet choice and maintenance, warehousing, packaging and others. On the other hand, dozens of people are involved in the logistics process. All these moments complicate the decision-making that is why data driven decisions are required nowadays. As well as shipment problems are NP-hard, the heuristic methods should be applied to resolve them. In this article we propose a genetic algorithm to solve the complex problem that consists of the Travelling Salesman Problem combined with the Knapsack Problem. We have developed an urban freight transportation model which is focused on the minimization of the underway time as well as on the maximization of the truck’s loading. A significant contribution in our method is the census of traffic frequency by using traffic zoning. The developed approach has been implemented using the Python programming language in the Zeppelin environment. The first version of the system has been approved in the city of Samara (Russia) with test demand dataset.
21
Azadnia, Amir Hossein, Shahrooz Taheri, Pezhman Ghadimi, Muhamad Zameri Mat Saman, and Kuan Yew Wong. "Order Batching in Warehouses by Minimizing Total Tardiness: A Hybrid Approach of Weighted Association Rule Mining and Genetic Algorithms." Scientific World Journal 2013 (2013): 1–13. http://dx.doi.org/10.1155/2013/246578.
Full textAbstract:
One of the cost-intensive issues in managing warehouses is the order picking problem which deals with the retrieval of items from their storage locations in order to meet customer requests. Many solution approaches have been proposed in order to minimize traveling distance in the process of order picking. However, in practice, customer orders have to be completed by certain due dates in order to avoid tardiness which is neglected in most of the related scientific papers. Consequently, we proposed a novel solution approach in order to minimize tardiness which consists of four phases. First of all, weighted association rule mining has been used to calculate associations between orders with respect to their due date. Next, a batching model based on binary integer programming has been formulated to maximize the associations between orders within each batch. Subsequently, the order picking phase will come up which used a Genetic Algorithm integrated with the Traveling Salesman Problem in order to identify the most suitable travel path. Finally, the Genetic Algorithm has been applied for sequencing the constructed batches in order to minimize tardiness. Illustrative examples and comparisons are presented to demonstrate the proficiency and solution quality of the proposed approach.
22
Meng, QingBiao, Shingo Mabu, Lu Yu, and Kotaro Hirasawa. "A Novel Taxi Dispatch System Integrating a Multi-Customer Strategy and Genetic Network Programming." Journal of Advanced Computational Intelligence and Intelligent Informatics 14, no. 5 (2010): 442–52. http://dx.doi.org/10.20965/jaciii.2010.p0442.
Full textAbstract:
Taxi service usually benefits people by providing comfortable and flexible ride experiences. However, an inherent problem, the insufficient number of taxis at traffic peak, has baffled taxi service ever since it existed. This paper hereby proposes a Multi-Customer Taxi Dispatch System (MCTDS), where taxis are granted a right to take customers with different Origin-Destination (OD) pairs simultaneously, to shorten the total waiting time and traveling time. In addition, to mitigate the damage of detours, MCTDS is built based on Genetic Network Programming, a graph-based evolutionary algorithm that has shown excellent performances previously in some complicated applications. We also modify the structure of GNP to achieve an improvement in performance. In the simulation part, we demonstrate that MCTDS outperforms the conventional GNP and some heuristic taxi dispatch approaches.
23
Mirzaei-Khafri, Soheila, Mahdi Bashiri, Roya Soltani, and Mohammad Khalilzadeh. "A MATHEMATICAL MODEL FOR THE CAPACITATED LOCATION-ARC ROUTING PROBLEM WITH DEADLINES AND HETEROGENEOUS FLEET." Transport 34, no. 6 (2019): 692–707. http://dx.doi.org/10.3846/transport.2019.11145.
Full textAbstract:
This paper considers a Capacitated Location-Arc Routing Problem (CLARP) with Deadlines (CLARPD) and a fleet of capacitated heterogeneous vehicles. The proposed mixed integer programming model determines a subset of potential depots to be opened, the served roads within predefined deadlines, and the vehicles assigned to each open depot. In addition, efficient routing plans are determined to minimize total establishment and traveling costs. Since the CLARP is NP-hard, a Genetic Algorithm (GA) is presented to consider proposed operators, and a constructive heuristic to generate initial solutions. In addition, a Simulated Annealing (SA) algorithm is investigated to compare the performance of the GA. Computational experiments are carried out for several test instances. The computational results show that the proposed GA is promising. Finally, sensitivity analysis confirms that the developed model can meet arc routing timing requirements more precisely compared to the classical Capacitated Arc Routing Problem (CARP).
24
Barbosa, Eduardo Batista de Moraes, and Edson Luiz França Senne. "Improving the Fine-Tuning of Metaheuristics: An Approach Combining Design of Experiments and Racing Algorithms." Journal of Optimization 2017 (2017): 1–7. http://dx.doi.org/10.1155/2017/8042436.
Full textAbstract:
Usually, metaheuristic algorithms are adapted to a large set of problems by applying few modifications on parameters for each specific case. However, this flexibility demands a huge effort to correctly tune such parameters. Therefore, the tuning of metaheuristics arises as one of the most important challenges in the context of research of these algorithms. Thus, this paper aims to present a methodology combining Statistical and Artificial Intelligence methods in the fine-tuning of metaheuristics. The key idea is a heuristic method, called Heuristic Oriented Racing Algorithm (HORA), which explores a search space of parameters looking for candidate configurations close to a promising alternative. To confirm the validity of this approach, we present a case study for fine-tuning two distinct metaheuristics: Simulated Annealing (SA) and Genetic Algorithm (GA), in order to solve the classical traveling salesman problem. The results are compared considering the same metaheuristics tuned through a racing method. Broadly, the proposed approach proved to be effective in terms of the overall time of the tuning process. Our results reveal that metaheuristics tuned by means of HORA achieve, with much less computational effort, similar results compared to the case when they are tuned by the other fine-tuning approach.
25
Sathyan, Anoop, Nicholas D. Ernest, and Kelly Cohen. "An Efficient Genetic Fuzzy Approach to UAV Swarm Routing." Unmanned Systems 04, no. 02 (2016): 117–27. http://dx.doi.org/10.1142/s2301385016500011.
Full textAbstract:
Fuzzy logic is used in a variety of applications because of its universal approximator attribute and nonlinear characteristics. But, it takes a lot of trial and error to come up with a set of membership functions and rule-base that will effectively work for a specific application. This process could be simplified by using a heuristic search algorithm like Genetic Algorithm (GA). In this paper, genetic fuzzy is applied to the task assignment for cooperating Unmanned Aerial Vehicles (UAVs) classified as the Polygon Visiting Multiple Traveling Salesman Problem (PVMTSP). The PVMTSP finds a lot of applications including UAV swarm routing. We propose a method of genetic fuzzy clustering that would be specific to PVMTSP problems and hence more efficient compared to k-means and c-means clustering. We developed two different algorithms using genetic fuzzy. One evaluates the distance covered by each UAV to cluster the search-space and the other uses a cost function that approximates the distance covered thus resulting in a reduced computational time. We compare these two approaches to each other as well as to an already benchmarked fuzzy clustering algorithm which is the current state-of-the-art. We also discuss how well our algorithm scales for increasing number of targets. The results are compared for small and large polygon sizes.
26
Güyagüler, Baris, Roland N. Horne, Leah Rogers, and Jacob J. Rosenzweig. "Optimization of Well Placement in a Gulf of Mexico Waterflooding Project." SPE Reservoir Evaluation & Engineering 5, no. 03 (2002): 229–36. http://dx.doi.org/10.2118/78266-pa.
Full textAbstract:
Summary In this study, a hybrid optimization technique based on the genetic algorithm (GA), polytope algorithm, kriging algorithm, and neural networks is proposed to optimize a waterflooding project. Hybridization of the GA with these helper methods introduces hill climbing into the stochastic search and makes use of proxies created on the fly. It was observed that the number of simulations required was reduced significantly, as compared to conventional approaches. This reduction in the number of simulations reduced the computation time, enabling the use of full-scale simulation for optimization even for this full-scale field problem. It was also seen that the optimization technique was able to prevent convergence to local maxima owing to its stochastic nature. Introduction Determination of the location of new wells is a complex problem that depends on reservoir and fluid properties, well and surface equipment specifications, and economic criteria. Various approaches have been proposed for this problem. Among those, direct optimization using the simulator as the evaluation function, although accurate, is in most cases infeasible due to the number of simulations required. Optimal placement of up to four water-injection wells was studied for Pompano, an offshore field in the Gulf of Mexico. Injection rate was also optimized. The net present value (NPV) of the waterflooding project was used as the objective function. Profits and costs during the time period of the project were taken into consideration. Numerical models are detailed and powerful predictive tools in reservoir management. While not perfect, they are often the best representation of the subsurface available. Optimization methodologies run these numerical models perhaps thousands of times, searching for the most profitable solution to reservoir management questions. Because of the computational time involved, optimization methodologies are not used as much as they could be. Various researchers have explored speeding up optimization either by using a speedier evaluation of the objective function (i.e., a simpler model or a proxy for the full numerical model) or by improving the efficiency of the optimization search itself. This paper uses the latter approach (focusing on search improvement), yet it harnesses some of the techniques often used in proxy development to allow the search to step toward optimality more skillfully. Researchers have looked into the optimization of well placement and rate using numerical simulation. Beckner and Song1 formulated the problem as a traveling-salesman problem and used simulated annealing to optimize well location and drilling schedule. Bittencourt and Horne2 investigated optimization of well placement using a hybrid of the GA and the polytope method. Güyagüler and Gümrah3 optimized production rates for a gas storage field using GAs. Aanonsen et al.4 coupled a CPU-efficient reservoir simulator with an optimization algorithm and made use of a kriging proxy to find optimum well locations. Pan and Horne5 also used kriging to decrease the necessary number of simulations required to optimize well location. Rogers and Dowla6 and Centilmen et al.7 used neural networks as a substitute for numerical simulation. We have been exploring search improvements in GA8 to decrease the total number of individual simulations required for convergence of the optimization problem. The GA is popular for its strengths in avoiding suboptimal solutions, freedom from requiring derivatives, and ease of parallelization. The GA was chosen over other popular heuristic search algorithms, such as simulated annealing, because of the concept of population and the greater ease of parallelization. Parallelization obviously has the potential to speed calculations. The concept of population integrates well with the formulation of the search improvements of this work. Some of the same traits that make the GA robust and powerful also make it slow and inexact in refining the solution. The GA typically has rapid initial progress during the search, but it has problems locating the final optimal solution. Because of these limitations, this work investigated specific helper methods that can significantly improve the efficiency, speed, and exactness of the GA search. The two helper methods integrated into the GA search are the polytope method9 and the proxy method. The two types of proxies explored are derived from kriging10 and neural-network11 estimates. Other proxies, such as simple analytical models, could be considered. These helper methods were integrated into a hybrid GA and applied to a waterflood management problem for the Pompano field in the Gulf of Mexico. This field is a complex turbidite sequence with anticlinal structure and a bottom drive aquifer. It was thought that the addition of one or more injection wells could increase overall field production and profitability significantly. We considered well placement and well pumping rates to be decision variables. Maximizing NPV was the overall objective. Again, note that the searches ultimately relied on the full numerical model; however, the number of function evaluations required for the search was reduced with the guidance of the helper methods. Reservoir Description The Pompano field extends over five Gulf of Mexico blocks [Mississippi Canyon (MC) 27, 28, and 72 and Viosca Knoll (VK) 989 and 990] located approximately 24 miles southeast of the Mississippi River Delta. Operations for the Pompano field have been investigated previously in the literature.12,13 BP plc and Kerr Mc- Gee hold 75% and 25% equity, respectively. The Pompano platform sits in VK 989 in 1,290 ft of water and is a 40-slot, fixed-leg platform. It is the second-tallest fixed structure in the Gulf of Mexico. The platform receives production from three reservoirs: upthrown Pliocene, downthrown Pliocene, and Miocene. In this paper, we focus on the Miocene reservoir, which comprises two thirds of the field reserves. The Miocene sands are located in MC 28 and 72. Developing these sands has proved challenging, given the large distance from the platform. The longest drillable platform wells (approximately 18,000 ft of lateral step out) can only reach the northern one-third of the reservoir. Thus, the remaining two-thirds in the south were developed from a 10-slot subsea template located in MC 28 in 1,800 ft of water. The template is tied back to the VK989 platform by two 8-in. flowlines approximately 4.5 miles in length.
27
Khosravanian, Asieh, Mohammad Rahmanimanesh, and Parviz Keshavarzi. "Discrete Social Spider Algorithm for Solving Traveling Salesman Problem." International Journal of Computational Intelligence and Applications, August 13, 2021, 2150020. http://dx.doi.org/10.1142/s1469026821500206.
Full textAbstract:
The Social Spider Algorithm (SSA) was introduced based on the information-sharing foraging strategy of spiders to solve the continuous optimization problems. SSA was shown to have better performance than the other state-of-the-art meta-heuristic algorithms in terms of best-achieved fitness values, scalability, reliability, and convergence speed. By preserving all strengths and outstanding performance of SSA, we propose a novel algorithm named Discrete Social Spider Algorithm (DSSA), for solving discrete optimization problems by making some modifications to the calculation of distance function, construction of follow position, the movement method, and the fitness function of the original SSA. DSSA is employed to solve the symmetric and asymmetric traveling salesman problems. To prove the effectiveness of DSSA, TSPLIB benchmarks are used, and the results have been compared to the results obtained by six different optimization methods: discrete bat algorithm (IBA), genetic algorithm (GA), an island-based distributed genetic algorithm (IDGA), evolutionary simulated annealing (ESA), discrete imperialist competitive algorithm (DICA) and a discrete firefly algorithm (DFA). The simulation results demonstrate that DSSA outperforms the other techniques. The experimental results show that our method is better than other evolutionary algorithms for solving the TSP problems. DSSA can also be used for any other discrete optimization problem, such as routing problems.
28
Morshed Adib, Muhammed Yaseen, Jannatun Razia, and Md Toufiqur Rahman. "Experimental Comparison between Genetic Algorithm and Ant Colony Optimization on Traveling Salesman Problem." International Journal of Scientific Research in Science, Engineering and Technology, February 2, 2021, 155–62. http://dx.doi.org/10.32628/ijsrset218135.
Full textAbstract:
This paper is based on bio-inspired optimization algorithms. Optimization is the process of selecting the best element by following some rules and criteria from some set of available alternatives. In this paper, we have solved Traveling Salesman Problem (TSP) using Swarm Intelligence algorithms and we have compared them. First we have implemented the basic Genetic Algorithm (GA) on TSP. Then we have implemented Ant Colony Optimization (ACO) Algorithm on TSP. In optimization problem, Genetic Algorithm (GA) and Ant Colony Optimization (ACO) Algorithm have been known as good meta-heuristic techniques. GA is designed by adopting the natural law of evolution, while ACO is inspired by the foraging behavior of ant species. Balancing the exploitation-exploration tradeoff is required in ACO. In contrast with the GA implementation, ACO was much easier to control.
29
Vacic, Vladimir, and Tarek M. Sobh. "VEHICLE ROUTING PROBLEM WITH TIME WINDOWS." International Journal of Computing, August 1, 2014, 72–80. http://dx.doi.org/10.47839/ijc.3.2.289.
Full textAbstract:
The topic of this paper is a Genetic Algorithm solution to the Vehicle Routing Problem with Time Windows, a variant of one of the most common problems in contemporary operations research. The paper will introduce the problem starting with more general Traveling Salesman and Vehicle Routing problems and present some of the prevailing strategies for solving them, focusing on Genetic Algorithms. At the end, it will summarize the Genetic Algorithm solution proposed by K.Q. Zhu which was used in the programming part of the project.
30
Löffler, Maximilian, Nils Boysen, and Michael Schneider. "Picker Routing in AGV-Assisted Order Picking Systems." INFORMS Journal on Computing, August 23, 2021. http://dx.doi.org/10.1287/ijoc.2021.1060.
Full textAbstract:
To reduce unproductive picker walking in traditional picker-to-parts warehousing systems, automated guided vehicles (AGVs) are used to support human order pickers. In an AGV-assisted order-picking system, each human order picker is accompanied by an AGV during the order-picking process. AGVs receive the picked items and, once a picking order is complete, autonomously bring the collected items to the shipping area. Meanwhile, a new AGV is requested to meet the picker at the first storage position of the next picking order. Thus, the picker does not have to return to a central depot and continuously picks order after order. This paper addresses both the routing of an AGV-assisted picker through a single-block, parallel-aisle warehouse and the sequencing of incoming orders. We present an exact polynomial time routing algorithm for the case of a given order sequence, which is an extension of the algorithm of Ratliff and Rosenthal [Ratliff HD, Rosenthal AS ( 1983 ) Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem. Oper. Res. 1(3):507–521], and a heuristic for the case in which order sequencing is part of the problem. In addition, we investigate the use of highly effective traveling salesman problem (TSP) solvers that can be applied after a transformation of both problem types into a standard TSP. The numerical studies address the performance of these methods and study the impact of AGV usage on picker travel: by using AGVs to avoid returns to the depot and by sequencing in (near-) optimal fashion, picker walking can be reduced by about 20% compared with a traditional setting. Sharing AGVs among the picker workforce enables a pooling effect so that, in larger warehouses, only about 1.5 AGVs per picker are required to avoid picker waiting. Summary of Contribution: New technologies, such as automatic guided vehicles (AGVs) are currently considered as options to increase the efficiency of the order-picking process in warehouses, which is responsible for a large part of operational warehousing costs. In addition, picker-routing decisions are more and more often based on algorithmic decision support because of their relevance for decreasing unproductive picker walking time. This paper addresses both aspects and investigates routing algorithms for AGV-assisted order picking in parallel-aisle warehouses. We present a dynamic programming routine with polynomial runtime to solve the problem variant in which the sequence of picking orders is fixed. For the variant in which this sequence is a decision, we show that the problem becomes NP-hard, and we propose a greedy heuristic and investigate the use of state-of-the-art exact and heuristic traveling salesman problem solution methods to address the problem. The numerical studies demonstrate the effectiveness of the algorithms and indicate that AGV assistance promises strong improvements in the order-fulfillment process. Because of the practical relevance of AGV-assisted order picking and the presented algorithmic contributions, we believe that the paper is relevant for practitioners and researchers alike.
31
"Effect of Crossover Probability on Performance of Genetic Algorithm in Scheduling of Parallel Machines for BI- Criteria Objectives." International Journal of Engineering and Advanced Technology 9, no. 1 (2019): 2827–31. http://dx.doi.org/10.35940/ijeat.a9801.109119.
Full textAbstract:
Optimization of multi objective function gain the importance in the scheduling process. Many classical techniques are available to address the multi objective functions but the solutions yield the unsatisfactory results when the problem becomes complex and large. Evolutionary algorithm would be the solution for such problems. Genetic algorithm is adaptive heuristic search algorithms and optimization techniques that mimic the process of natural evolution. Genetic algorithms are a very effective way of obtaining a reasonable solution quickly to a complex problem. The genetic algorithm operators such as selection method, crossover method, crossover probability, mutation operators and stopping criteria have an effect on obtaining the reasonably good solution and the computational time. Partially mapped crossover operators are used to solve the problem of the traveling salesman, planning and scheduling of the machines, etc., which are having a wide range of solutions. This paper presents the effect of crossover probability on the performance of the genetic algorithm for the bi-criteria objective function to obtain the best solution in a reasonable time. The simulation on a designed genetic algorithm was conducted with a crossover probability of 0.4 to 0.95 (with a step of 0.05) and 0.97, found that results were converging for the crossover probability of 0.6 with the computational time of 3.41 seconds.
32
Goncharenko, V. I., G. N. Lebedev, and D. A. Mikhaylin. "Planning the search for separating parts of the launch vehicle using a group of unmanned aerial vehicles." Engineering Journal: Science and Innovation, no. 12 (108) (December 2020). http://dx.doi.org/10.18698/2308-6033-2020-12-2040.
Full textAbstract:
The paper deals with the processes of maintaining a special class of mobile objects, whose schedules are either given or require preassignment in order to maintain these objects at the right time and in the right place. The posed problem of planning the flight of a group of aerial vehicles is solved using a continuous form of dynamic programming, according to which the Bellman equation in partial derivatives corresponds to the optimality condition. An original approach to solving the problem of pre-flight and operational planning of actions of a group of unmanned aerial vehicles based on a genetic algorithm is proposed. The fundamental difference between the problem being solved and the well-known traveling salesman problem is in taking into account the required maintenance schedule. The developed planning automation tool makes it possible to increase the efficiency of measures to detect separating parts of launch vehicles using a group of unmanned aerial vehicles. Findings of research show that the developed genetic algorithm is better not only than algorithms based on one-parameter and two-parameter criteria, but even better than algorithms based on a three-parameter criterion.
33
Liu, Yi, Meng Joo Er, and Chen Guo. "Online time-optimal path and trajectory planning for robotic multipoint assembly." Assembly Automation ahead-of-print, ahead-of-print (2021). http://dx.doi.org/10.1108/aa-03-2021-0029.
Full textAbstract:
Purpose The purpose of this paper is to propose an efficient path and trajectory planning method to solve online robotic multipoint assembly. Design/methodology/approach A path planning algorithm called policy memorized adaptive dynamic programming (PM-ADP) combines with a trajectory planning algorithm called adaptive elite genetic algorithm (AEGA) for online time-optimal path and trajectory planning. Findings Experimental results and comparative study show that the PM-ADP is more efficient and accurate than traditional algorithms in a smaller assembly task. Under the shortest assembly path, AEGA is used to plan the time-optimal trajectories of the robot and be more efficient than GA. Practical implications The proposed method builds a new online and efficient path planning arithmetic to cope with the uncertain and dynamic nature of the multipoint assembly path in the Cartesian space. Moreover, the optimized trajectories of the joints can make the movement of the robot continuously and efficiently. Originality/value The proposed method is a combination of time-optimal path planning with trajectory planning. The traveling salesman problem model of assembly path is established to transfer the assembly process into a Markov decision process (MDP). A new dynamic programming (DP) algorithm, termed PM-ADP, which combines the memorized policy and adaptivity, is developed to optimize the shortest assembly path. GA is improved, termed AEGA, which is used for online time-optimal trajectory planning in joints space.
34
"Genetic algorithm of distribution of delivery routes." Bulletin of V. N. Karazin Kharkiv National University Economic Series, no. 98 (2020). http://dx.doi.org/10.26565/2311-2379-2020-98-12.
Full textAbstract:
Information technologies have become an integral part of the life of modern society. That is why they are actively used to solve the complicated tasks related to optimisation of activities in economy, management, finance, social and other spheres. Logistics are not an exception, and information technologies are used to automate delivery processes, which contributes to the efficient and cost-effective operation of enterprises. This is possible provided that the supplier's resources are managed rationally and provided with an efficient way of distributing delivery routes. This explains the relevance of this work. The purpose of the article is to develop a genetic algorithm to determine the optimal delivery plan, as well as to compare its work with some well-known delivery optimization methods. The object of study is the delivery routes. The subject of the study is the distribution route distribution algorithm. The article proposes a genetic algorithm for solving the traveling salesman problem with several routes. The statement of the problem of determining the optimal delivery plan is presented, the possibility of using a genetic algorithm for the task is considered, the type of the genetic algorithm is described and a block diagram of its implementation is presented. A software implementation of the genetic algorithm and other methods of distributing delivery routes has been prepared, which is carried out using the C++ programming language and the Qt framework. For the algorithms to work, you need to generate an order, vehicles and depots, as well as enter the necessary parameters. The results of the operation of the algorithm and other selected methods using the program were obtained, which made it possible to evaluate their effectiveness on the basis of experimental data for given parameters and to compare their work. The advantage of the proposed genetic algorithm over the well-known ant algorithm in randomly generated tests has been experimentally established. This indicates the applied value of the results obtained and the possibility of applying the algorithm in real conditions of distribution of supply routes.
35
López, J. Fabián. "A mixed integer programming model for a continuous move transportation problem with service constraints." Revista Innovaciones de Negocios 7, no. 13 (2017). http://dx.doi.org/10.29105/rinn7.13-2.
Full textAbstract:
Key words: Genetic algorithms, logistics routing, metaheuristics, scheduling, time windowsAbstract. We consider a Pickup and Delivery Vehicle Routing Problem (PDP) commonly encountered in real-world logistics operations. The problem involves a set of practical complications that have received little attention in the vehicle routing literature. In this problem, there are multiple vehicle types available to cover a set of pickup and delivery requests, each of which has pickup time windows and delivery time windows. Transportation orders and vehicle types must satisfy a set of compatibility constraints that specify which orders cannot be covered by which vehicle types. In addition we include some dock servicecapacity constraints as is required on common real world operations. This problem requires to be attended on large scale instances (orders ≥ 500), (vehicles ≥ 150). As a generalization of the traveling salesman problem, clearly this problem is NP-hard. The exact algorithms are too slow for large scale instances. The PDP-TWDS is both a packing problem (assign order tovehicles), and a routing problem (find the best route for each vehicle). We propose to solve the problem in three stages. The first stage constructs initials solutions at aggregate level relaxing some constraints on the original problem. The other two stages imposes time windows and dock service constraints. Our results are favorable finding good quality solutions in relatively short computational times.Palabras claves. Algoritmos genéticos, logística de ruteo, metahurística, programación, ventana de horarioResumen. En la solución de problemas combinatorios, es importante evaluar el costobeneficio entre la obtención de soluciones de alta calidad en detrimento de los recursos computacionales requeridos. El problema planteado es para el ruteo de un vehículo con entrega y recolección de producto y con restricciones de ventana de horario. En la práctica, dicho problema requiere ser atendido con instancias de gran escala (nodos ≥100). Existe un fuerte porcentaje de ventanas de horario activas (≥90%) y con factores de amplitud ≥75%. El problema es NP-hard y por tal motivo la aplicación de un método de solución exacta para resolverlo en la práctica, está limitado por el tiempo requerido para la actividad de ruteo. Se propone un algoritmo genético especializado, el cual ofrece soluciones de buena calidad (% de optimalidad aceptables) y en tiempos de ejecución computacional que hacen útil su aplicación en la práctica de la logística. Para comprobar la eficacia de la propuesta algorítmica se desarrolla un diseño experimental el cual hará uso de las soluciones óptimas obtenidas mediante un algoritmo de ramificación y corte sin límite de tiempo. Los resultados son favorables.