首页> 外文OA文献 >An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree
【2h】

An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree

机译:带有树的拾取和传递的带电容TSP的一种改进的近似算法

摘要

In this research, we study the capacitated traveling salesman problem with pickup and delivery (CTSPPD) on a tree, which aims to determine the best route for a vehicle with a finite capacity to transport amounts of a product from pickup points to delivery points on a tree network, such that the vehicle's total travel distance is kept to a minimum. It has several applications in logistics and is known to be NP-hard. We develop a 2-approximation algorithm that is a significant improvement over the best constant approximation ratio of 5 derived from existing CTSPPD literature. Computational results show that the proposed algorithm also achieves good average performance over randomly generated instances.
机译:在这项研究中,我们研究了树上具有接送能力的有能力的旅行推销员问题(CTSPPD),该问题旨在确定容量有限的车辆从接载点到接载点的产品运输能力的最佳路线。树网络,使车辆的总行驶距离保持最小。它在物流中有多种应用,并且已知是NP难处理的。我们开发了一种2近似算法,它是对从现有CTSPPD文献中得出的最佳恒定近似值5的重大改进。计算结果表明,该算法在随机生成的实例上也具有良好的平均性能。

著录项

  • 作者

    Xu Z; Lai X; Lim A; Wang F;

  • 作者单位
  • 年度 2014
  • 总页数
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号