首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Multi-Dimensional Commodity Covering for Tariff Selection in Transportation
  • 作者:Felix G. K{\"o}nig ; Jannik Matuschke ; Alexander Richter
  • 期刊名称:OASIcs : OpenAccess Series in Informatics
  • 电子版ISSN:2190-6807
  • 出版年度:2012
  • 卷号:25
  • 页码:58-70
  • DOI:10.4230/OASIcs.ATMOS.2012.58
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Covering; Heuristics; Transportation; Tariff Selection
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有