License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2012.58
URN: urn:nbn:de:0030-drops-37034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3703/
König, Felix G. ;
Matuschke, Jannik ;
Richter, Alexander
Multi-Dimensional Commodity Covering for Tariff Selection in Transportation
Abstract
In this paper, we study a multi-dimensional commodity 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 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 SetCover 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. 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 AG.
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 enabling the optimization of large-scale networks.
BibTeX - Entry
@InProceedings{knig_et_al:OASIcs:2012:3703,
author = {Felix G. K{\"o}nig and Jannik Matuschke and Alexander Richter},
title = {{Multi-Dimensional Commodity Covering for Tariff Selection in Transportation}},
booktitle = {12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {58--70},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-45-3},
ISSN = {2190-6807},
year = {2012},
volume = {25},
editor = {Daniel Delling and Leo Liberti},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3703},
URN = {urn:nbn:de:0030-drops-37034},
doi = {10.4230/OASIcs.ATMOS.2012.58},
annote = {Keywords: Covering, Heuristics, Transportation, Tariff Selection}
}
|
Keywords: |
|
Covering, Heuristics, Transportation, Tariff Selection |
|
Collection: |
|
12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
13.09.2012 |
