...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs
【24h】

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

机译：带补给弧的非对称旅行商问题的多面体结果和精确算法

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

摘要

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 19941 by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems. (C) 2007 Elsevier B.V. All rights reserved.
机译：由与飞机路线相关的工作引起的带有补充弧（RATSP）的非对称旅行推销员问题是众所周知的ATSP的概括。在本文中，我们介绍了用于RATSP的多项式大小混合整数线性规划（MILP）公式，并改进了Zhu的现有指数大小ILP公式[飞机旋转问题，博士学位。论文，佐治亚理工学院，亚特兰大，19941，提出了两类更强的削减措施。我们提出的结果是，在某些条件下，这两类更强的切割对于RATS多表位是刻面定义的，并且可以提起ATSP刻面以提供RATSP刻面。我们实施了多面体的发现，并针对RATSP开发了基于拉格朗日松弛（LR）的分支定界（BNB）算法，并将此方法与使用ILOG Cplex 9.0求解多项式大小公式（使用随机生成的问题和飞机）进行了比较路由问题。最后，我们将我们的方法与Boland等人的现有方法进行了比较。 [带有补充弧的非对称旅行推销员问题，欧洲J. Oper。 Res。 123（2000）408-427]。事实证明，我们两种方法都比Boland等人的方法快得多。 [带有补充弧的非对称旅行推销员问题，欧洲J. Oper。 Res。 123（2000）408-427]，并且基于LR的BNB方法对于类似于飞机旋转问题的问题更为有效。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号