Abstract: Imperialist Competitive Algorithm (ICA) is a recent
meta-heuristic method that is inspired by the social evolutions for
solving NP-Hard problems. The ICA is a population-based algorithm
which has achieved a great performance in comparison to other metaheuristics.
This study is about developing enhanced ICA approach to
solve the Cell Formation Problem (CFP) using sequence data. In
addition to the conventional ICA, an enhanced version of ICA,
namely EICA, applies local search techniques to add more
intensification aptitude and embed the features of exploration and
intensification more successfully. Suitable performance measures are
used to compare the proposed algorithms with some other powerful
solution approaches in the literature. In the same way, for checking
the proficiency of algorithms, forty test problems are presented. Five
benchmark problems have sequence data, and other ones are based on
0-1 matrices modified to sequence based problems. Computational
results elucidate the efficiency of the EICA in solving CFP problems.
Abstract: Container handling problems at container terminals
are NP-hard problems. This paper presents an approach using
discrete-event simulation modeling to optimize solution for storage
space allocation problem, taking into account all various interrelated
container terminal handling activities. The proposed approach is
applied on a real case study data of container terminal at Alexandria
port. The computational results show the effectiveness of the
proposed model for optimization of storage space allocation in
container terminal where 54% reduction in containers handling time
in port is achieved.
Abstract: This paper proposes a bi-objective model for the
facility location problem under a congestion system. The idea of the
model is motivated by applications of locating servers in bank
automated teller machines (ATMS), communication networks, and so
on. This model can be specifically considered for situations in which
fixed service facilities are congested by stochastic demand within
queueing framework. We formulate this model with two perspectives
simultaneously: (i) customers and (ii) service provider. The
objectives of the model are to minimize (i) the total expected
travelling and waiting time and (ii) the average facility idle-time.
This model represents a mixed-integer nonlinear programming
problem which belongs to the class of NP-hard problems. In addition,
to solve the model, two metaheuristic algorithms including nondominated
sorting genetic algorithms (NSGA-II) and non-dominated
ranking genetic algorithms (NRGA) are proposed. Besides, to
evaluate the performance of the two algorithms some numerical
examples are produced and analyzed with some metrics to determine
which algorithm works better.
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: 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.