...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Transportation Science >An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns
【24h】

An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns

机译：基于源和汇模式匹配的固定电荷运输问题的精确算法

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

摘要

This paper describes an exact algorithm for the fixed charge transportation problem based on a new integer programming formulation that involves two sets of variables representing flow patterns from sources to sinks and from sinks to sources. The formulation states to select a pattern for each source and each sink and to match the corresponding flows. The linear relaxation of this new formulation is enforced by adding a pseudo-polynomial number of equations that are shown to contain, as special cases, different valid inequalities recently proposed for the problem. The resulting lower bound dominates the lower bounds proposed in the literature. Such a lower bound is embedded into an exact branch-and-cut-and-price algorithm. Computational results on benchmark instances show that the proposed algorithm is several times faster than the state-of-the-art exact methods and could solve all open instances. New harder instances with up to 120 sources and 120 sinks were solved to optimality.
机译：本文基于一种新的整数规划公式，描述了解决固定电荷运输问题的精确算法，该公式涉及两组变量，分别代表从源到汇以及从汇到源的流动模式。该公式陈述为每个源和每个接收器选择一个模式并匹配相应的流。通过添加伪多项式方程组，可以增强这种新公式的线性松弛性，这些方程组显示为包含（在特殊情况下）最近针对该问题提出的不同有效不等式。所产生的下限主导了文献中提出的下限。这样的下限被嵌入到精确的分枝和割价算法中。在基准实例上的计算结果表明，所提出的算法比最新的精确方法快几倍，并且可以解决所有开放实例。解决了具有120个源和120个接收器的新的更困难的实例，从而达到了最佳状态。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号