Matheuristics: Hybrid Algorithms for Transportation Problems

01.01.2008 - 31.10.2010
Forschungsförderungsprojekt
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. 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.

Personen

Projektleiter_in

Projektmitarbeiter_innen

Institut

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Forschungsschwerpunkte

  • Computational Intelligence: 100%

Schlagwörter

DeutschEnglisch
Matheuristicsmatheuristics
Metaheuristikenmeta heuristics
Ganzzahlige lineare Programmierunginteger linear programming
kombinatorische Optimierungcombinatorial optimization
Routenplanungsproblemevehicle routing problems

Externe Partner_innen

  • Universität Wien

Publikationen