论文标题
双堆堆的双旅行人员问题的近似
Approximation of the Double Travelling Salesman Problem with Multiple Stacks
论文作者
论文摘要
双重旅行推销员的问题有多个堆栈，DTSPM，处理两个不同城市的n个商品的收集和交付，在这里，取货和送货旅行与LIFO约束有关。在接送之旅中，商品被装入具有容量c的k行或堆栈的容器中。本文着重于DTSPM的计算方面，即NP-HARD。 我们首先回顾了两个关键子问题的复杂性：确定给定的接送和送货旅行是否可行，鉴于装载计划，在K和C的某些条件下，找到一对最佳的拾取和送货旅行，都是多项式的。 然后，我们证明了MinMetrickDTSPMS的A（3K）/2标准近似值，其中K是通用常数，并且对于各种问题的各种版本而言，其他近似结果。 我们最终为2DTSPM提供了基于匹配的启发式启发式，当距离为对称时，这是一个特殊情况，k = 2行。这产生了分别为Max2DTSPM的1/2-O（1），3/4-O（1）和3/2+O（1）标准近似值，其限制为Max2DTSPMS-（1,2），距离为1和2，Min2DTSPMS-（1,2），以及A 1/2-O（1/2-o（1）和A 1/2-O（1），SPMS SPSS和MAXSSPSSSSP和MAX2DTTSSSP。
The Double Travelling Salesman Problem with Multiple Stacks, DTSPMS, deals with the collect and delivery of n commodities in two distinct cities, where the pickup and the delivery tours are related by LIFO constraints. During the pickup tour, commodities are loaded into a container of k rows, or stacks, with capacity c. This paper focuses on computational aspects of the DTSPMS, which is NP-hard. We first review the complexity of two critical subproblems: deciding whether a given pair of pickup and delivery tours is feasible and, given a loading plan, finding an optimal pair of pickup and delivery tours, are both polynomial under some conditions on k and c. We then prove a (3k)/2 standard approximation for the MinMetrickDTSPMS, where k is a universal constant, and other approximation results for various versions of the problem. We finally present a matching-based heuristic for the 2DTSPMS, which is a special case with k=2 rows, when the distances are symmetric. This yields a 1/2-o(1), 3/4-o(1) and 3/2+o(1) standard approximation for respectively Max2DTSPMS, its restriction Max2DTSPMS-(1,2) with distances 1 and 2, and Min2DTSPMS-(1,2), and a 1/2-o(1) differential approximation for Min2DTSPMS and Max2DTSPMS.
