Matheuristics: Hybrid Algorithms for Transportation Problems

Transportation problems appear in many practically highly relevant areas of our daily life. In general, they include the assignment of produced goods to customers and decisions on how and at which times the goods are picked up and delivered. Improvements in solutions often have a direct and substantial impact on costs and on other important factors like customer satisfaction. Because of the many facets and decisions to be made, such transportation problems are often complex combinations of assignment, scheduling, and routing problems. In this project, we will focus on special classes of transportation problems, namely those dealing with multiple visits. Multiple visits problems occur when customers from a fixed set have to be visited repeatedly. The basic form of this type of problems is given by the so-called periodic vehicle routing problem. Further reductions in costs may be achieved by exploiting the possibility of switching from the more frequent vendee managed inventory setup to a vendor managed inventory system. The resulting problem type, known as inventory routing problem, will also be considered in the project. A third important class is given by the periodic full truckload problem, where customers require repeatedly at least one full truckload of the transported unit. For all these problem types, both heuristic and exact algorithms exist. Exact algorithms have the aim to find an optimal solution and to prove its optimality; the run-time, however, often increases dramatically with a problem instance`s size, and only small or moderately sized instances can be solved to provable optimality in practice. For larger instances, one usually has to resort to heuristic algorithms that trade optimality for run-time; i.e., these algorithms are designed to obtain good but not necessarily optimal solutions in acceptable time. Two particularly successful categories of methods that traditionally can be distinguished by these aspects are mathematical programming techniques on one side and metaheuristics on the other. To some degree, they can be seen as complementary; therefore it is highly promising to combine concepts from both streams. Nevertheless, most of today`s hybrid optimizers of this type, for which the term "matheuristics" has been coined recently, follow rather simple combination schemes, despite a potential for farther-reaching synergies. More work is necessary in order to obtain a better general understanding as well as guidelines indicating under which circumstances which hybridization strategies are most promising. The general aim of the project is to develop and to investigate different hybrids of metaheuristics with integer linear programming methods for solving the indicated classes of transportation problems in a better way than by current state-of-the-art approaches. In more detail, we have the following major goals to which the project`s work plan is oriented: (i) boosting the performance of heuristic and of exact algorithms by exploiting hybridization possibilities, (ii) developing hybrid algorithms for bi-objective and stochastic problem formulations. The last two features are important insofar as in applications of periodic routing, situations requiring decisions under uncertainty and/or encompassing more than one single objective are frequently encountered. This project will be the first in which a variety of "matheuristic" solution techniques for real-world transportation problems with periodic visits will be developed and studied. Existing research results clearly indicate that such approaches are highly promising for the considered problem domain. A particularly innovative aspect of our project is the consideration of models that combine bi-objective and stochastic aspects; for such models, very few solution techniques are known at present. Finally, we expect the findings of this research also to be useful in the future development of solution approaches for other classes of combinatorial optimization problems.

In this projects innovative hybrid solution techniques of exact methods and metaheuristic search techniques have been investigated. As application primarily periodic vehicle routing problems also with multiple objectives and stochasticity were considered. Vehicle routing problems appear in many practically highly relevant areas of our daily life. In general, they include the assignment of produced goods to customers and decisions on how and at which times the goods are picked up or delivered. Improvements in solutions often have a direct and substantial impact on costs and other important factors like customer satisfaction. Unfortunately most of the problems are difficult to solve to optimality in reasonable times. For approaching such computationally difficult combinatorial optimization problems, a large number of algorithmic strategies has been proposed in the last decades. The available techniques can roughly be classified into two main categories: exact and heuristic algorithms. Exact algorithms are guaranteed to find an optimal solution and prove its optimality; the run-time, however, often increases dramatically with a problem instance`s size. For larger instances the only possibility is usually to turn to heuristic algorithms that trade optimality for run-time; i.e., they are designed to obtain good but not necessarily optimal solutions in acceptable time. Within this project a broad variety of different hybrid design patterns was developed and investigated. The developed methods often outperform other state-of-the art methods with respect to solution quality. Integrative hybrid methods and collaborative hybrid methods were investigated. The most successful design patterns are i) hybrid variants of column generation based approaches. This can be of benefit also for other problems where a standard branch-and-price approach is not applicable to larger instances. ii) Suitable integer linear programming based large neighborhood searches built upon a set covering model or a network flow model were applied to "richer" problems (e.g. location routing, free newspaper delivery, solid waste management, ready mixed concrete delivery). The developed hybrid methods mainly outperform pure metaheuristic approaches. iii) For even larger instances we proposed a seamless integration of the multilevel refinement strategy into a metaheuristic. iv) For the biobjective variant of a vehicle routing problem our developed approach shows that by a combination of mathematical programming techniques with a multiobjective metaheuristic, the efficiency of the exact solution approach can be improved. By proceeding to the stochastic and biobjective case, we have shown that also the complex (but frequently occurring) situation where multiobjective vehicle routing problems have to be solved under demand uncertainty can be handled by suitable computational methods.