HEURISTICS FOR DELIVERY PROBLEMS WITH CONSTANT ERROR GUARANTEES. TECHNICAL NOTE
分析了单位重量配送问题的分区启发式算法，证明了两种算法（QIOTP和BOTP）的最坏情况误差不超过2-1/Q，其中Q是车辆最多可服务的客户数。
This paper analyzes partitioning heuristics for the unit weight delivery problem and proves nontrivial bounds on their worst case error behavior. Two heuristics, Q Iterated Optimal Tour Partitioning (QIOTP) and Best Optimal Tour Partitioning (BOTP), which take as the input an optimal TSP tour through all points, are described. It is proven that the worst case error of both heuristics cannot exceed 2-1/Q, where Q is the maximal number of customers a vehicle could visit. Similar worst case error bounds are shown when the algorithms are applied to an alpha-optimal traveling salesman tour.