Jump to content
AIT Logo

Hybrid approaches for combinatorial optimization problems

In our daily lives we are often confronted with situations in which hard decisions have to be made. In many cases this decision-making process can be formalized and modelled as a combinatorial optimization problem. Examples of such decision problems include route planning and activity scheduling. Also, in the corporate world, we can identify numerous combinatorial optimization problems, e.g., in production and transport planning, logistic operations, or staff scheduling. More general, a combinatorial optimization problem is characterized by having a finite set of possible choices, potentially constrained by several side conditions, such that a target value is maximized or minimized. Our goal at the AIT is to develop mathematical models, novel methodologies, and efficient solution algorithms to find the optimal or near-optimal decision.

Transportoptimierung

In the field of transport optimization and logistics almost all relevant problems can be modelled as a combinatorial optimization problem. Therefore, the mindsef of AIT’s transport optimization and logistics team takes the following four steps to solve a (real-world) problem:

  • First, the problem statement is mathematically modelled in order to have a formal problem description.
  • Second, the problem is modelled via integer linear programming or constraint programming methods to obtain an exact solution method.
  • As in most situations, instances of the underlying real-world problem requires highly scalable solution methods, (meta-)heuristic or hybrid solutions approaches are developed.
  • Finally, the proposed solution methods are evaluated with respect to (standard) KPIs, such as performance and solution quality.

AIT’s approach focuses on real-world problems originating in the field of transport science. Therefore, AIT developed an algorithmic framework DynaTOP which is capable of solving standard transportation problems out-of-the-box such that real-world constraints stated by users (which are typically project partners) can be easily integrated. As this framework is based on metaheuristic approaches (since typical instances of the tackled real-world problems are too large for (pure) exact approaches) a switch between different metaheuristic approaches can be applied. Therefore, we can evaluate different metaheuristic approaches such that the best performing one for the given problem statement can be chosen for further development.

 

Publications

G. Hiermann, M. Prandtstetter, A. Rendl, J. Puchinger, G. Raidl: 
"Metaheuristics for Solving a Multimodal Home-Healthcare Scheduling Problem"; 
Central European Journal of Operations Research, 23 (2015), 1; S. 89 - 113.