Current Research

Efficient Algorithms for Combinatorial Optimization Problems

 A combinatorial optimization problem is a problem that its solution space or constraints are discrete and the objective is to find a feasible solution minimizing given objective function. It has a very wide range of applications and a variety of problems in real-world situation can be expressed as combinatorial optimization problems. However, these problems are often NP-hard problems and it is difficult to obtain an optimal solution in reasonable time. On the other hand, optimal solutions are rarely necessary in real-world situation and we are satisfied with good solutions obtained in reasonable computation time even if we are not able to obtain an exact optimal solution. In this way, efficient algorithms that find a good solution in reasonable time are important. Recently such approaches (e.g., local search, metaheuristics) have been intensively studied.
  The aim of my research is to develop efficient algorithms for combinatorial optimization problems. In particular, I'm interested in designing a high performance algorithm by a mathematical method utilizing a good structure of a target problem. The current research topics are as follows:

• vehicle routing problem
• scheduling problem
• graph partition problem
• design of real-time system, and so on.

  Here, I introduce the vehicle routing problem. This problem is strongly related to real-world problems. It have been intensively studied from the aspect of engineering and is one of the most successful applications in the field of operations research. The vehicle routing problem is the problem of minimizing the total travel cost of a number of vehicles, under various constraints, where every customer must be visited exactly once by a vehicle. Among various constraints, the capacity constraint and the time window constraint are typical. The capacity constraint signifies that the total load on a route cannot exceed the capacity of the assigned vehicle. The time window constraint signifies that each vehicle must start the service at each customer in the period specified by the customer. In the previous research, we proposed an algorithm which is based on local search and, now, we are working to develop an efficient algorithm using mathematical programming approach.
  Although a problem arising in real world situations is often complicated and developed algorithms can not be  directly used, I would like to conduct research in order to contribute to achieving better solutions.