• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >A branch-and-cut algorithm for the capacitated profitable tour problem
【24h】

A branch-and-cut algorithm for the capacitated profitable tour problem

机译：容量化获利旅行问题的分枝算法

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

摘要

This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.
机译：本文考虑的是获利的获利旅行问题（CPTP），它是具有资源约束的基本最短路径问题（ESPPRC）的特例。 CPTP属于被称为带利润的旅行推销员问题。在CPTP中，每个客户都与利润和需求相关联，目标是找到一个有容量的游览（植根于仓库节点），该游览将总行程距离减到拜访客户的利润最小化。在许多列生成应用程序中，CPTP可以被视为子问题，传统上是通过动态编程来解决的。在本文中，我们提出了一种基于无定向CPTP公式的替代框架，并通过分支剪切来解决。提出了有效不等式，其中我们引入了一个新的CPTP不等式族，表示为舍入多星不等式，我们证明了它们的有效性。对文献中已知的一组实例和一组新生成的实例进行计算实验。结果表明，所提出的算法与动态规划算法具有很高的竞争力。特别是，我们能够求解具有800个节点的实例，而动态编程算法无法求解具有200个以上节点的实例。此外，动态编程和分支剪切功能可以很好地互补，这给了我们希望通过混合方法解决更多一般问题的希望。本文旨在用作进一步开发CPTP分支剪切算法的平台，因此也可作为调查/指南。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号