• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Computational logistics >The Maximum Flow Problem with Minimum Lot Sizes
【24h】

The Maximum Flow Problem with Minimum Lot Sizes

机译：最小批量的最大流量问题

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In many transportation systems, the shipment quantities are subject to minimum lot sizes in addition to regular capacity constraints. That is, either the quantity must be zero, or it must be between the two bounds. In this work, we consider a directed graph, where a mini mum lot size and a flow capacity are defined for each arc, and study the problem of maximizing the flow from a given source to a given termi nal. We prove that the problem is NP-hard. Based on a straightforward mixed integer programming formulation, we develop a Lagrangean relax ation technique, and demonstrate how this can provide strong bounds on the maximum flow. For fast computation of near-optimal solutions, we develop a heuristic that departs from the zero solution and gradually augments the set of flow-carrying (open) arcs. The set of open arcs does not necessarily constitute a feasible solution. We point out how feasibil ity can be checked quickly by solving regular maximum flow problems in an extended network, and how the solutions to these subproblems can be productive in augmenting the set of open arcs. Finally, we present re sults from preliminary computational experiments with the construction heuristic.
机译：在许多运输系统中，除了常规的运力限制外，装运数量还受最小批号的限制。也就是说，数量必须为零，或者必须在两个边界之间。在这项工作中，我们考虑一个有向图，其中为每条弧线定义了最小的批量大小和流量，并研究最大化从给定源到给定终端的流量的问题。我们证明问题是NP难的。基于简单的混合整数编程公式，我们开发了Lagrangean弛豫技术，并演示了该方法如何为最大流量提供强边界。为了快速计算接近最优的解，我们开发了一种启发式方法，该方法偏离零解，逐渐增加了载流（开放）弧的集合。一组开放弧不一定构成可行的解决方案。我们指出如何通过解决扩展网络中的常规最大流量问题来快速检查可行性，以及这些子问题的解决方案如何在扩大开放弧集方面产生作用。最后，我们通过构造启发式方法给出了初步计算实验的结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号