Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIterated tabu search for the circular open dimension problem
155
0
0.0
(
0
)
Added by
Zhanghua Fu
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper mainly investigates the circular open dimension problem (CODP), which consists of packing a set of circles of known radii into a strip of fixed width and unlimited length without overlapping. The objective is to minimize the length of the strip. An iterated tabu search approach, named ITS, is proposed. ITS starts from a randomly generated solution and attempts to gain improvements by a tabu search procedure. After that, if the obtained solution is not feasible, a perturbation operator is subsequently employed to reconstruct the incumbent solution and an acceptance criterion is implemented to determine whether or not accept the perturbed solution. This process is repeated until a feasible solution has been found or the allowed computation time has been elapsed. Computational experiments based on well-known benchmark instances show that ITS produces quite competitive results with respect to the best known results. For 18 representative CODP instances taken from the literature, ITS succeeds in improving 13 best known results within reasonable time. In addition, for another challenging related variant: the problem of packing arbitrary sized circles into a circular container, ITS also succeeds in improving many best known results. Supplementary experiments are also provided to analyze the influence of the perturbation operator, as well as the acceptance criterion.
rate research
Read More
This paper introduces a multi-period inspector scheduling problem (MPISP), which is a new variant of the multi-trip vehicle routing problem with time windows (VRPTW). In the MPISP, each inspector is scheduled to perform a route in a given multi-period planning horizon. At the end of each period, each inspector is not required to return to the depot but has to stay at one of the vertices for recuperation. If the remaining time of the current period is insufficient for an inspector to travel from his/her current vertex $A$ to a certain vertex B, he/she can choose either waiting at vertex A until the start of the next period or traveling to a vertex C that is closer to vertex B. Therefore, the shortest transit time between any vertex pair is affected by the length of the period and the departure time. We first describe an approach of computing the shortest transit time between any pair of vertices with an arbitrary departure time. To solve the MPISP, we then propose several local search operators adapted from classical operators for the VRPTW and integrate them into a tabu search framework. In addition, we present a constrained knapsack model that is able to produce an upper bound for the problem. Finally, we evaluate the effectiveness of our algorithm with extensive experiments based on a set of test instances. Our computational results indicate that our approach generates high-quality solutions.
The Flexible Job Shop Scheduling Problem (FJSP) is a combinatorial problem that continues to be studied extensively due to its practical implications in manufacturing systems and emerging new variants, in order to model and optimize more complex situations that reflect the current needs of the industry better. This work presents a new meta-heuristic algorithm called GLNSA (Global-local neighborhood search algorithm), in which the neighborhood concepts of a cellular automaton are used, so that a set of leading solutions called smart_cells generates and shares information that helps to optimize instances of FJSP. The GLNSA algorithm is complemented with a tabu search that implements a simplified version of the Nopt1 neighborhood defined in [1] to complement the optimization task. The experiments carried out show a satisfactory performance of the proposed algorithm, compared with other results published in recent algorithms and widely cited in the specialized bibliography, using 86 test problems, improving the optimal result reported in previous works in two of them.
Quantum Computing is considered as the next frontier in computing, and it is attracting a lot of attention from the current scientific community. This kind of computation provides to researchers with a revolutionary paradigm for addressing complex optimization problems, offering a significant speed advantage and an efficient search ability. Anyway, Quantum Computing is still in an incipient stage of development. For this reason, present architectures show certain limitations, which have motivated the carrying out of this paper. In this paper, we introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses. To assess the quality of our method, we have used 7 different Traveling Salesman Problem instances as benchmarking set. The obtained outcomes support the preliminary conclusion that our algorithm is an approach which offers promising results for solving partitioning problems while it drastically reduces the access to quantum computing resources. We also contribute to the field of Transfer Optimization by developing an evolutionary multiform multitasking algorithm as initialization method.
Quantum Computing is an emerging paradigm which is gathering a lot of popularity in the current scientific and technological community. Widely conceived as the next frontier of computation, Quantum Computing is still at the dawn of its development. Thus, current solving systems suffer from significant limitations in terms of performance and capabilities. Some interesting approaches have been devised by researchers and practitioners in order to overcome these barriers, being quantum-classical hybrid algorithms one of the most often used solving schemes. The main goal of this paper is to extend the results and findings of the recently proposed hybrid Quantum Computing - Tabu Search Algorithm for partitioning problems. To do that, we focus our research on the adaptation of this method to the Asymmetric Traveling Salesman Problem. In overall, we have employed six well-known instances belonging to TSPLIB to assess the performance of Quantum Computing - Tabu Search Algorithm in comparison to QBSolv, a state-of-the-art decomposing solver. Furthermore, as an additional contribution, this work also supposes the first solving of the Asymmetric Traveling Salesman Problem using a Quantum Computing based method. Aiming to boost whole communitys research in QC, we have released the projects repository as open source code for further application and improvements.
This paper describes an optimisation methodology that has been specifically developed for engineering design problems. The methodology is based on a Tabu search (TS) algorithm that has been shown to find high quality solutions with a relatively low number of objective function evaluations. Whilst the methodology was originally intended for a small range of design problems it has since been successfully applied to problems from different domains with no alteration to the underlying method. This paper describes the method and its application to three different problems. The first is from the field of structural design, the second relates to the design of electromagnetic pole shapes and the third involves the design of turbomachinery blades.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
