tabu search algorithm

Rail transit plays an increasingly important role in the public transportation system, and effectively reducing its huge energy consumption is of great practical significance. Wider use of public transport, particularly rail and metro, is one way to save energy. A growing trend of applying the rail network and metro by governments on one hand and the considerable energy consumption of a train during one year, on the other hand, demonstrate the necessity of considering the consumed energy by train. Railway transportation consumes amounts of energy. Direct energy consumption to complete the transport tasks is the main part of energy consumption of rail transportation, especially the traction system, which leads to the railway transportation costly. Optimization of the train speed curve plays an important role in minimizing train energy consumption. In this paper, first, there was a review on models of train energy optimization with different characteristics and corresponding other algorithms to find the optimum speed profile and accuracy of them, Second Tabu Search (TS) algorithm as a new approach for optimizing the train speed profile to save energy will be investigated. In this approach, after determining the appropriate points of acceleration, neural and braking, a speed profile in which train could cover its route with minimum energy consumption will be achieved. We call these points "the variables for changing the training strategy. The algorithm was implemented in alternative routes. In this study, the simulations of the proposed method are implemented in MATLAB software and are finally compared with the Genetic Algorithm method.

Completing the project in the shortest possible time, at the lowest cost, at the highest level of quality, can play a decisive role in profitability and competition. Time, cost and quality are the most important goals of any project, and their optimization is one of the topics in project planning and control. The aim of this study is to find the optimal combination of time, cost and quality in conditions of limited resources. The theory of constraints in project management has led to a new approach to project management and control called the critical chain. In this research, using the critical chain technique and the high ability of the tabu search algorithm (TS) in optimization, the problem of multi-objective optimization of time, cost and quality in conditions of resource constraints has been solved. The proposed algorithm was extracted with MATLAB coding software and the desired results were extracted. To validate the proposed model, two case studies with 7 and 18 activities have been solved. Also, a project with 60 activities in which time, cost and quality optimization was done, was used to validate the proposed algorithm in the research and the results were extracted and compared. The results showed that the tabu search algorithm had a correct and acceptable performance. In such a way that it has the ability to create multiple Pareto answers with different values ​​of the three objective functions of time, cost and quality. This allows project managers to choose the best solution in terms of time, cost and quality according to their needs and policies.

Rail transit plays an increasingly important role in the public transportation system, and effectively reducing its huge energy consumption is of great practical significance. Wider use of public transport, particularly rail and metro, is one way to save energy. A growing trend of applying the rail network and metro by governments on one hand and the considerable energy consumption of a train during one year, on the other hand, demonstrate the necessity of considering the consumed energy by train. Railway transportation consumes amounts of energy. Direct energy consumption to complete the transport tasks is the main part of energy consumption of rail transportation, especially the traction system, which leads to the railway transportation costly. Optimization of the train speed curve plays an important role in minimizing train energy consumption. In this paper, first, there was a review on models of train energy optimization with different characteristics and corresponding other algorithms to find the optimum speed profile and accuracy of them, Second Tabu Search (TS) algorithm as a new approach for optimizing the train speed profile to save energy will be investigated. In this approach, after determining the appropriate points of acceleration, neural and braking, a speed profile in which train could cover its route with minimum energy consumption will be achieved. We call these points "the variables for changing the training strategy. The algorithm was implemented in alternative routes. In this study, the simulations of the proposed method are implemented in MATLAB software and are finally compared with the Genetic Algorithm method.

Urban transportation is one of the most important issues of urban life especially in big cities. Urban development, and subsequently the increase of routes and communications, make the role of transportation science more pronounced. The shortest path problem in a network is one of the most basic network analysis issues. In fact, finding answers to this question is necessity for higher level analysis. In general, shortest path solution methods using optimization algorithms are divided into two categories: exact and approximate algorithms. In exact algorithms, achieving the optimal solution requires time, and consequently more cost. On the opposite side, there are some approximate algorithms that work in a short period of time. Meta-heuristic algorithms are among approximate algorithms that are capable of finding optimal or near-optimal solutions in a reasonable period of time. The method used in this study is to solve the shortest path problem with the combination of Genetic meta-heuristic (GA) and Tabu Search (TS) algorithms. GA is inspired by genetic science and Darwin's theory of evolution; it is based on survival of the highest or natural selection. A common use of genetic algorithms is to be used as an optimization function. In GA, the genetic evolution of living things of life is simulated. Inspired by the evolutionary process of nature, these algorithms solve problems. GA forms a set of population (solutions), then it achieves an optimal set by acting some possess on the correct set. To solve a problem by genetic algorithms, it is necessary the problem is converted to the specific form required by GA. On the other hand, TS algorithm is not population-based. It obtains an answer, then it tries to direct the answer to the optimal solution by applying a series of operators. This algorithm is highly similar to the Simulated Annealing algorithm. In this paper, for solving the shortest path problem, a series of geometric pre-processing on the network is done to generate a search area around the source and destination nodes. In the proposed algorithm, the cost function is defined as a complex number, which the real part shows the sum of the weight of the real edges, and the imaginary part denotes the number of virtual edges. The innovation of this research is about applying Tabu Search algorithm in mutations process of genetic algorithm. The proposed method overcomes the inappropriate response of the pure genetic algorithm in terms of the final weight of the path especially the large networks. In order to evaluate the efficiency of the proposed algorithm, the algorithm was implemented on a real directional network which is part of Tehran city road networks including 739 nodes and 1160 edges. The results show that in the proposed algorithm, the length of the path is as close as possible to the solution obtained from the definitive Dijkstra’s algorithm. This algorithm predicts approximately the final path length of 5% more than Dijkstra’s algorithm. But in terms of running speed, it is 5.12 times faster than the Dijkstra’s algorithm. In comparison with the pure genetic algorithm, the proposed algorithm is 9% shorter in average in terms of path length. And about the running time, the speed of the proposed algorithm is approximately equal to the pure genetic algorithm. Regarding to repeatability, the proposed algorithm also shows 25.36% of repeatability.

Taking the advantage of transportation services for employees corporate, offices and factories is one of the outstanding solutions to reduce traffic congestion and fuel consumption. In this way planning and allocation of vehicles to passengers and also determining the transportation routes are major problems. Such problems are known as Vehicle Routing Problem (VRP) that fall into category of complex multi-purpose optimization problem. This paper attempts to simplify the problem by breaking it into several simple and single-purpose problems and also to propose a novel approach for path finding. At first, VRP converts to several single-purpose problems, using improvement k-means algorithm. Then, a hybrid method based on Saving and Tabu Search algorithms is developed to find shortest path. Results show that hybrid method of Saving and Tabu Search algorithms is better and faster than using only Tabu. Keywords: Vehicle Routing Problems (VRP), Tabu Search Algorithm, Saving Algorithm, K-means Algorithm, GIS

The traveling salesman problem (TSP) is a well-known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-hard problems. This means that no known algorithm is guaranteed to solve all TSP instances to optimality within reasonable execution time. Due to thedifferent nature of metaheuristics algorithms and the importance and application of TSP in different fields, in this paper the shortest Hamiltonian path is achieved between 423 Iranian cities by the two types of algorithms. for the first time Tabu search as a single-solution-based algorithm and memetic algorithm as a population-based algorithm is selected. To evaluate the accuracy and efficiency of the proposed algorithms, standard problems with size from 16 cities to 1060 cities have been used. Results demonstrate the performance and effectiveness of proposed algorithms. Java programming language to code algorithms has been used in this research. Parameters tuning for each algorithm is done separately and ultimately the best value for each parameter has been determined.Finally, the performances of each algorithm determined by quality of solution and CPU time and the results have been compared.