Abstract: This paper reviews the major contributions to the Motion Planning (MP) field throughout a 35-year period, from classic approaches to heuristic algorithms. Due to the NP-Hardness of the MP problem, heuristic methods have outperformed the classic approaches and have gained wide popularity. After surveying around 1400 papers in the field, the amount of existing works for each method is identified and classified. Especially, the history and applications of numerous heuristic methods in MP is investigated. The paper concludes with comparative tables and graphs demonstrating the frequency of each MP method's application, and so can be used as a guideline for MP researchers.
Abstract: This paper presents a heuristic approach to solve the Generalized Assignment Problem (GAP) which is NP-hard. It is worth mentioning that many researches used to develop algorithms for identifying the redundant constraints and variables in linear programming model. Some of the algorithms are presented using intercept matrix of the constraints to identify redundant constraints and variables prior to the start of the solution process. Here a new heuristic approach based on the dominance property of the intercept matrix to find optimal or near optimal solution of the GAP is proposed. In this heuristic, redundant variables of the GAP are identified by applying the dominance property of the intercept matrix repeatedly. This heuristic approach is tested for 90 benchmark problems of sizes upto 4000, taken from OR-library and the results are compared with optimum solutions. Computational complexity is proved to be O(mn2) of solving GAP using this approach. The performance of our heuristic is compared with the best state-ofthe- art heuristic algorithms with respect to both the quality of the solutions. The encouraging results especially for relatively large size test problems indicate that this heuristic approach can successfully be used for finding good solutions for highly constrained NP-hard problems.
Abstract: The paper describes a new approach for fingerprint
classification, based on the distribution of local features (minute
details or minutiae) of the fingerprints. The main advantage is that
fingerprint classification provides an indexing scheme to facilitate
efficient matching in a large fingerprint database. A set of rules based
on heuristic approach has been proposed. The area around the core
point is treated as the area of interest for extracting the minutiae
features as there are substantial variations around the core point as
compared to the areas away from the core point. The core point in a
fingerprint has been located at a point where there is maximum
curvature. The experimental results report an overall average
accuracy of 86.57 % in fingerprint classification.
Abstract: This paper presents a novel approach for optimal
reconfiguration of radial distribution systems. Optimal
reconfiguration involves the selection of the best set of branches to
be opened, one each from each loop, such that the resulting radial
distribution system gets the desired performance. In this paper an
algorithm is proposed based on simple heuristic rules and identified
an effective switch status configuration of distribution system for the
minimum loss reduction. This proposed algorithm consists of two
parts; one is to determine the best switching combinations in all loops
with minimum computational effort and the other is simple optimum
power loss calculation of the best switching combination found in
part one by load flows. To demonstrate the validity of the proposed
algorithm, computer simulations are carried out on 33-bus system.
The results show that the performance of the proposed method is
better than that of the other methods.
Abstract: Facility Layout Problem (FLP) is one of the essential
problems of several types of manufacturing and service sector. It is
an optimization problem on which the main objective is to obtain the
efficient locations, arrangement and order of the facilities. In the
literature, there are numerous facility layout problem research
presented and have used meta-heuristic approaches to achieve
optimal facility layout design. This paper presented genetic algorithm
to solve facility layout problem; to minimize total cost function. The
performance of the proposed approach was verified and compared
using problems in the literature.
Abstract: Connected dominating set (CDS) problem in unit disk
graph has signi£cant impact on an ef£cient design of routing protocols
in wireless sensor networks, where the searching space for a
route is reduced to nodes in the set. A set is dominating if all the
nodes in the system are either in the set or neighbors of nodes in the
set. In this paper, a simple and ef£cient heuristic method is proposed
for £nding a minimum connected dominating set (MCDS) in ad hoc
wireless networks based on the new parameter support of vertices.
With this parameter the proposed heuristic approach effectively
£nds the MCDS of a graph. Extensive computational experiments
show that the proposed approach outperforms the recently proposed
heuristics found in the literature for the MCD
Abstract: Network reconfiguration in distribution system is realized by changing the status of sectionalizing switches to reduce the power loss in the system. This paper presents a new method which applies an artificial bee colony algorithm (ABC) for determining the sectionalizing switch to be operated in order to solve the distribution system loss minimization problem. The ABC algorithm is a new population based metaheuristic approach inspired by intelligent foraging behavior of honeybee swarm. The advantage of ABC algorithm is that it does not require external parameters such as cross over rate and mutation rate as in case of genetic algorithm and differential evolution and it is hard to determine these parameters in prior. The other advantage is that the global search ability in the algorithm is implemented by introducing neighborhood source production mechanism which is a similar to mutation process. To demonstrate the validity of the proposed algorithm, computer simulations are carried out on 14, 33, and 119-bus systems and compared with different approaches available in the literature. The proposed method has outperformed the other methods in terms of the quality of solution and computational efficiency.
Abstract: The main goal of this work is to propose a way for
combined use of two nontraditional algorithms by solving topological
problems on telecommunications concentrator networks. The
algorithms suggested are the Simulated Annealing algorithm and the
Genetic Algorithm. The Algorithm of Simulated Annealing unifies
the well known local search algorithms. In addition - Simulated
Annealing allows acceptation of moves in the search space witch lead
to decisions with higher cost in order to attempt to overcome any
local minima obtained. The Genetic Algorithm is a heuristic approach
witch is being used in wide areas of optimization works. In the last
years this approach is also widely implemented in
Telecommunications Networks Planning. In order to solve less or
more complex planning problem it is important to find the most
appropriate parameters for initializing the function of the algorithm.
Abstract: In the modern manufacturing systems, the use of
thermal cutting techniques using oxyfuel, plasma and laser have
become indispensable for the shape forming of high quality complex
components; however, the conventional chip removal production
techniques still have its widespread space in the manufacturing
industry. Both these types of machining operations require the
positioning of end effector tool at the edge where the cutting process
commences. This repositioning of the cutting tool in every machining
operation is repeated several times and is termed as non-productive
time or airtime motion. Minimization of this non-productive
machining time plays an important role in mass production with high
speed machining. As, the tool moves from one region to the other by
rapid movement and visits a meticulous region once in the whole
operation, hence the non-productive time can be minimized by
synchronizing the tool movements. In this work, this problem is
being formulated as a general travelling salesman problem (TSP) and
a genetic algorithm approach has been applied to solve the same. For
improving the efficiency of the algorithm, the GA has been
hybridized with a noble special heuristic and simulating annealing
(SA). In the present work a novel heuristic in the combination of GA
has been developed for synchronization of toolpath movements
during repositioning of the tool. A comparative analysis of new Meta
heuristic techniques with simple genetic algorithm has been
performed. The proposed metaheuristic approach shows better
performance than simple genetic algorithm for minimization of nonproductive
toolpath length. Also, the results obtained with the help of
hybrid simulated annealing genetic algorithm (HSAGA) are also
found better than the results using simple genetic algorithm only.
Abstract: This paper presents a heuristic to solve large size 0-1 Multi constrained Knapsack problem (01MKP) which is NP-hard. Many researchers are used heuristic operator to identify the redundant constraints of Linear Programming Problem before applying the regular procedure to solve it. We use the intercept matrix to identify the zero valued variables of 01MKP which is known as redundant variables. In this heuristic, first the dominance property of the intercept matrix of constraints is exploited to reduce the search space to find the optimal or near optimal solutions of 01MKP, second, we improve the solution by using the pseudo-utility ratio based on surrogate constraint of 01MKP. This heuristic is tested for benchmark problems of sizes upto 2500, taken from literature and the results are compared with optimum solutions. Space and computational complexity of solving 01MKP using this approach are also presented. The encouraging results especially for relatively large size test problems indicate that this heuristic can successfully be used for finding good solutions for highly constrained NP-hard problems.