direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


A Multi-Dimensional Multi-Commodity Covering Problem with Applications in Logistics
Zitatschlüssel Report-009-2012
Autor König, Felix G. and Matuschke, Jannik and Richter, Alexander
Jahr 2012
Nummer 009
Zusammenfassung In this paper, we study a multi-commodity multi-dimensional covering problem which we encountered as a subproblem in optimizing large scale transportation networks in logistics. The problem asks for a selection of containers for transporting a given set of commodities, each commodity having different extensions of properties such as weight or volume. Each container can be selected multiple times and is specified by a fixed charge and capacities in the relevant properties. The task is now to find a cost minimal collection of containers and a feasible assignment of the demand to all selected containers. From theoretical point of view, by exploring similarities to the well known set cover problem, we derive NP-hardness and see that the non-approximability result known for set cover also carries over to our problem. For practical applications we need very fast heuristics to be integrated into a meta-heuristic framework that – depending on the context - either provide feasible near optimal solutions or only estimate the cost value of an optimal solution. Thus, in a second part we develop and analyze a flexible family of greedy algorithms that meet these challenges. In order to find best-performing configurations for different requirements of the meta-heuristic framework, we provide an extensive computational study on random and real world instance sets obtained from our project partner 4flow. We outline a trade-off between running times and solution quality and conclude that the proposed methods achieve the accuracy and efficiency necessary for serving as a key ingredient in more complex meta-heuristics.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag