  Combinatorial optimization is widely applied in a number of areas nowadays.
Unfortunately, many combinatorial optimization problems are NP-hard which
usually means that they are unsolvable in practice. However, it is often
unnecessary to have an exact solution. In this case one may use heuristic
approach to obtain a near-optimal solution in some reasonable time.
  We focus on two combinatorial optimization problems, namely the Generalized
Traveling Salesman Problem and the Multidimensional Assignment Problem. The
first problem is an important generalization of the Traveling Salesman Problem;
the second one is a generalization of the Assignment Problem for an arbitrary
number of dimensions. Both problems are NP-hard and have hosts of applications.
  In this work, we discuss different aspects of heuristics design and
evaluation. A broad spectrum of related subjects, covered in this research,
includes test bed generation and analysis, implementation and performance
issues, local search neighborhoods and efficient exploration algorithms,
metaheuristics design and population sizing in memetic algorithm.
  The most important results are obtained in the areas of local search and
memetic algorithms for the considered problems. In both cases we have
significantly advanced the existing knowledge on the local search neighborhoods
and algorithms by systematizing and improving the previous results. We have
proposed a number of efficient heuristics which dominate the existing
algorithms in a wide range of time/quality requirements.
  Several new approaches, introduced in our memetic algorithms, make them the
state-of-the-art metaheuristics for the corresponding problems. Population
sizing is one of the most promising among these approaches; it is expected to
be applicable to virtually any memetic algorithm.
