Dynamic Programming in Routing Problems

发表于 更新于 分类于 ， 阅读次数：

介绍动态规划在路径问题如旅行商问题及车辆路径问题中的应用.

1961 Bellman–Held–Karp Algorithm

提出于Held1961ADP, Bellman1962DynamicPT, 广为人知的求解ATSP的算法, 时间复杂度为\(O(2^nn^2)\), 空间复杂度为\(O(n2^n)\).

1977 Karp's Partitioning Heuristic

提出于Karp1977ProbabiliticAO, 为求解Euclidean TSP的算法. 思想为构造K-d Tree后, 运用Bellman–Held–Karp Algorithm求解子问题, 之后合并为Spanning Walk (偶度连通的顶点导出子图), 随后设计函数PASS(u, v, w)和LOOP(v)将其转化为可行解. (若e(u, v), e(v, w)不构成边割集, PASS(u, v, w)将其删去后加入e(u, w), 三角不等式能保证该操作使得环游长度减小; LOOP(v)则是删去Loop)

该算法效果不好, 一个可能原因是在子问题中调用了精确求解算法, 详见Gutin2007TheTS, 399-400.

1981 Christofides's Q-path Lower Bound

提出于Christofides1981ExactAF, 为求解VRP的方法. 可用于Weighted Girth Problem, 见Gutin2007TheTS, 612.

1995 Sergeev's Algorithm for the Minimax Problem of the Traveling Salesman

提出于Sergeev1995AlgorithmFT, 原文使用俄文书写. 仅有理论意义, 未曾被实现, 见Gutin2007TheTS, 705.

1996 \(O(n)\) Algorithm for Finding 4-opt Moves

提出于Glover1996FindingAB. 被Cirasella2001TheAT用于实现Kanellakis1980LocalSF提出的KP算法 (一种求解ATSP的Local Search方法)

见Gutin2007TheTS, 461.

1998 Arora Algorithm

提出于Arora1998PolynomialTA, 为求解Euclidean TSP的PTAS算法. 给定顶点个数为\(n\)的TSP实例, 对任意的\(\epsilon>0\), 该算法可以在\(n^{O(1/\epsilon)}\)的时间内找到\((1+\epsilon)\)近似的解, 之后此时间复杂度又被改进至\(n(\log n)^{O(1/\epsilon)}\).

见Gutin2007TheTS, 207-221.

1997 Balas's k-bounded Neighbor

提出于Balas1997LinearTD, 对一类多项式时间可解的TSP问题设计了一种动态规划算法, 原文如下:

Balas (1996) introduced a class of polynomially solvable TSPs with precedence constraints: Given an integer \(k>0\) and an ordering \(\sigma:=(1,\ldots,n)\) of \(N\), find a minimum cost tour, i.e. a permutation \(\pi\) of \(\sigma\), satisfying \(\pi(1)=1\) and \[ \pi(i)<\pi(j) \text { for all } i, j \in \sigma \text { such that } i+k \leq j \] Problems in this class can be solved by dynamic programming in time linear in \(n\), though exponential in k:

THEOREM 1 (Balas 1996). Any TSP with condition (1) can be solved in time \(O(k^22^{k-2}n)\).

因此可以定义一种邻域k-bounded neighbor, 使用动态规划在线性时间内搜索该邻域内的最优解, 下给出其定义, 详见Gutin2007TheTS, 432-433.

For any fixed \(k\), we say that such a tour \(T^\prime\) is a k-bounded neighbor of a tour \(T=c_{\pi[1]},c_{\pi[2]}\ldots,c_{\pi[N]}\) if for no \(i,j\) with \(i\ge j+k\) does city \(c_{\pi[j]}\) occur after \(c_{\pi[i]}\) in \(T^\prime\).

下面以\(\sigma=(1,\ldots,n)\)为初始序列, 给出一些例子:

  1. \(k=0\), 此时要求对任意\(i\le j\), 有\(\pi(i)<\pi(j)\), 不成立.
  2. \(k=1\), 此时要求对任意\(i+1\le j\), 即\(i<j\), 有\(\pi(i)<\pi(j)\), 该邻域内只有一个序列满足要求, 即\(\sigma\).
  3. \(k=2\), 此时要求对任意\(i+2\le j\), 即\(i+1<j\), 有\(\pi(i)<\pi(j)\), 该邻域内有\(n-1\)个序列满足要求, 即\((2, 1,3,4\ldots,n)\), \((1,3,2,4,5,\ldots,n)\), ..., \((1,2,\ldots,n-2,n,n-1)\). 以\((1,2,\ldots,n-2,n,n-1)\)为例做一个说明, 对于该序列中的顶点\(n-1\), 只要该序列中的前\(n-2\)个顶点比它小就满足邻域定义.

2001 HyperOpt

提出于Burke2001EffectiveLA, 为求解ATSP的Local Search方法. 思想为将解序列视为两部分, 其一视为整体, 其二打散, 然后用Bellman–Held–Karp Algorithm求解. 对TSPLIB中小至br17大至rbg443的实例进行了实验, 误差至多为9.43%.

见Gutin2007TheTS, 415.

2003 Tour Merging

提出于Cook2003TourMV, 为求解STSP的启发式方法. 对TSPLIB中小至dsj1000大至pla33810的实例进行了实验, 误差至多为0.41%.

见Gutin2007TheTS, 436-438.

Polynomially Solvable Cases of the TSP

一些多项式时间可解的特殊TSP问题, 包含很多前苏联学者的工作, 文献较少. 动态规划相关的有Klyaus1976GenerationOT, Kabadi1985ASC等, 详见Gutin2007TheTS, 489-583.