Current Research

Metaheuristics for Combinatorial Optimization Problems

OUTLINE
Combinatorial optimization problems, which arise in such applications as scheduling, network optimization, and so forth, include a wide range of important issues in the field of informatics and engineering; hence it is crucial to devise efficient algorithms for them. However, many are known to be NP-hard, and obtaining their exact optimal solutions is computationally intractable.
One realistic way to deal with such problems is using heuristics, which can quickly obtain good (although not necessarily optimal) solutions. Greedy methods and local searches are basic methodologies often used for this purpose. As the speed of computers continues to grow rapidly, on recent computers such basic methods usually require very short computation time. This motivates people to spend more computation time to obtain better solutions. A recent trend uses metaheuristics for this purpose, which gives frameworks for combining basic heuristic tools into more sophisticated algorithms. Included among representative metaheuristic algorithms are genetic algorithms, simulated annealing, tabu search, and so on.
Our research objectives include devising efficient algorithms based on metaheuristics and developing general problem solvers that can handle a wide range of problems.

TOPICS
Efficient algorithms for representative problems
Representative combinatorial optimization problems often arise as the basic substructures of real problems, and so it is important to devise efficient algorithms that can obtain high quality solutions in short computation time. We have proposed sophisticated metaheuristic algorithms for such important obstacles as the generalized assignment problem, the set covering problem, etc. Our algorithms incorporate elaborate techniques including ejection chain neighborhoods, adaptive control of parameters, Lagrangian relaxation, and efficient data structures to search for large neighborhoods. As a result, our algorithms achieve competitive results with state of the art algorithms and can deal with large-scale problem instances with up to 1, 000, 000 variables.

General problem solvers based on metaheuristics
We are also developing general problem solvers that can deal with a wide range of problems. Since it takes much time and effort to develop a heuristic algorithm from scratch, it would be more convenient if we had solvers applicable to various problems. For this purpose we have been developing metaheuristic algorithms for the generalized variants of the vehicle routing problem with time windows, the rectangle packing problem, the cutting stock problem, and so on.

Wooden puzzle
We made the above wooden puzzle so that people can experience the difficulty of combinatorial optimization. The objective of the puzzle is to arrange the rectangular pieces to minimize wasted space. The nine pieces of the puzzle are sufficient to experience the difficulty of combinatorial problems.

FUTURE WORK
Metaheuristics receives much attention due to its effectiveness; however, very little is known about its theoretical aspects. Giving a theoretical explanation to its success as well as devising practical metaheuristic algorithms are important future directions of our research.