Bounds for the general capacitated routing problem
Bounds for the general capacitated routing problem
复制标题
一般容量路由问题的界限
DOI：
10.1002/net.3230230304
复制
发表时间：
1993
期刊：
影响因子：
2.1
通讯作者：
K. Jansen
中科院分区：
文献类型：
--
作者：
K. Jansen
本文提出了一种基于一般路径规划的路径分割算法来求解一般能力约束路径规划问题。该问题是车辆路径问题（VRP）和带能力约束的弧路径问题（CARP）的推广。对于VRP，由Christofides生成的TSP行程的最优划分组成的算法是已知的，并且对于偶数q具有7/2 − 3/q的最坏情况误差，其中q是车辆的容量。如果我们对一个最优TSP路径进行划分，最坏情况下的误差为3 − 2/q（对于偶数q）。我们将这些结果推广到GCRP，并给出了一些下界。John Wiley & Sons，Inc.
This paper presents heuristics that are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP). For the VRP, heuristics that consist of an optimum partitioning of a TSP tour generated by Christofides are known and have a worst-case error of 7/2 − 3/q for even q, where q is the capacity of the vehicles. If we apply a partitioning to an optimum TSP tour, the worst-case error becomes 3 − 2/q for even q. We generalize these results to the GCRP and give also some lower bounds. © 1993 John Wiley & Sons, Inc.