首页>
外文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.
展开▼