自动仓储系统中的规划问题

BlaXuan

前段时间我在运筹OR帷幄给了个talk（等出来了我更新链接）。让我又从新思考并整理了这个方向的一些问题。
仓储中很多问题是旅行商问题（TSP），但有些结构，使其存在多项式时间算法。为了简便阐述，本文中说的TSP实际上是个稍微松弛的版本，是找到每个顶点必须要走过至少一次(而不是有且仅有一次)的最短回路。
我们叫一类图为有界X图，如果这类图中X都小于等于一个常数。这里X是这个图上的一个参数。比如树宽（treewidth）。树宽是用来衡量一个图多么的像一颗树。有向图的树宽，是把方向去掉之后的无向图的树宽。注意这个和有向树宽（directed treewidth）不一样。因为本文之后再也不会用"有向图"这个词，所以有界有向树宽图的意思为有向树宽为常数的图。
对于有界树宽图，Courcelle's theorem得到图上能用一元二阶逻辑（monadic second-order logic）定义的优化问题都可以在线性时间解决。TSP问题就是其中一种。而有向树宽却没有类似的结论。有向树宽从发现到现在20年都没有一个像样的在优化算法中的用处。
本文调查了一些仓储领域中一些有多项式时间算法的问题。
货架拣货问题

有一些货架，货架上有些地方有需要被取出的货物。现在有个无限容量的机器人想要用最短的路径把每个货物都取到。
每个货架可以想象为一个线段，上面可以放置一些物品。这里可以想象货架布局为下图所示。



2行7列货架的布局以及抽象出来的图。[Roodbergen, de Koster 2001]

给了货架布局，也就可以为此抽象出来一个图。这就是在这个图上的一个几乎纯粹的TSP问题。但是这图真的很特殊。
Ratliff和Rosenthal给出了1行n列货架的多项式时间算法[1]。接近20年后，Roodbergen和de Koster给出了2行n列货架的多项式时间算法[2]。是一个非常复杂的有25种不同state的动态规划算法。
那么对于更多行货架呢？可以看出h行货架也不过是一个树宽，甚至路径宽度（pathwidth）为h的一个图。Courcelle's theorem拿来就能用：对于常数h，货架拣货问题存在线性时间的算法。实际上1990年了解这个结论的人可以直接给出完美的答案，但各个领域交叉不多。直到2018年才有人将这两个联系起来：Cambazard和Catusse给出了O(nh7^h)时间的算法，并且提到了treewidth的作用[3]。
未解问题

• 能否降低算法复杂度？
  
• 有限容量机器人呢？（我没细查，应该有人做过）
  

存取问题

和拣货问题有一定的区别，存取问题中，我们不仅仅有存还有取的操作。这个版本中考虑的是容量为1的机器人。
首先问题中需要一些进口和出口。每个存的请求是从某些进口拿到一个物体放到特定的位置，每个取的请求是说从某特定的位置拿物品到某些出口。注意，这里只有物体所在的地方是特定的，对应每个请求，可能有一个进口/出口，或者多个进口/出口。最终目标是最短时间让机器人完成所有的请求。
机器人常见的操作为完成一个存请求之后去完成一个取请求。一般来说存放了一个物体之后，移动到进出口的距离应该比移动到一个取请求的位置来说远一点。



机器存取的一个路径。注意机器回到进出口之前最多完成两个请求。

货架存取问题

考虑1行n列货架上的做存取。每一列货架的边缘处是进出口。每一次定义了哪一边是物品的进口，哪一边是物品的出口（不是机器人的进出口，机器人可以任何方向进）。Vis和Roodbergen给出存取问题的解法，也是利用DP得到多项式时间算法[4]。
这个问题中的图和这些货架问题一样，都是有界树宽图。有可能这方法可以扩展到任意有界树宽图。
从上文来看，所有的问题都能用Courcelle's theorem里的算法直接一统江湖啊。
那我们接下来看一个不能用有界树宽图上的算法的问题。
常数个进出口的存取问题

前面的问题图的结构特殊，但是进口出口数可以任意大。那我们反过来，进口和出口的个数是常数，但是机器走位是任意度量空间，我们还能保证多项式时间存取么？注意，这个问题里出现的图不是有界树宽图，也是本文第一次出现非有界树宽图。
从1997年开始跨越了20年，一个进出口的时候[5], 一个进口一个出口[6]，两个进出口的时候[7]都被解决。终于，我们给出了一个对于常数个进出口的时候的解答[8]。
因为这个图的树宽可以任意大，我们只好用另一种方法来解决问题：

• 一个顶点集合叫反馈顶点集，如果删了这个集合里的顶点，图就成为有向无环图。这个图存在一个反馈顶点集（feedback vertex set, FVS）的大小为k。
  
• 每个反馈顶点之间的简单路径长度最多为3。
  

通过这两个属性我们对常数个进出口的存取问题给出了多项式时间的算法。具体怎么做的可以看原文或者talk。
注意：虽然树宽不是有界的，但有向树宽（directed treewidth）是有界的。因为FVS有界表明有向树宽有界。
未解问题

• h行n列货架存取问题怎么求解？
  
• 如果每个请求的进出口和位置都是多对多呢？比如一个物品可以从某两个进口取到，不过可以放在某两个位置的任意一个。
  
• 机器人容量为2呢？（可以证明机器人容量为3是NP-hard的）
  
• 机器人容量为2，但物品之间有冲突呢？（比如红色物品和蓝色物品如果同时在机器上会引起爆炸）
  

山上拣货问题

最后来提一个山上拣货问题，是已经解决的存储问题的更一般化形式。
一个山上有k个不同的缆车站。这里k是一个常数。缆车站可以通过缆车直达山上的一些仓库。缆车都是向上移动的。 山上的仓库之间有路，但是这些路都是下山的路，也就是如果A仓库比B仓库高则无法通过路到达，而缆车站本身也是仓库。 有无限容量机器人正在1号缆车站，他想要知道能否能最快从每一个仓库提取货物并回到1号缆车站。机器人可以用缆车上山，也可以用路下山。但注意往上走必须通过缆车站。
这个可以建立一个简单的图。如果能通过路或者缆车直接从A到达B，则我们加一条边。山上拣货问题就是找这个图上的TSP。如果删掉所有的缆车站，则图变成有向无环图。也就是，反馈顶点集的大小为k。
未解问题

对于常数k, 山上拣货问题是否有多项式时间算法？同等的，有界FVS图，TSP是否可以多项式时间解决?
k=1 的特例是很容易解决的，因为能直接转换成为一个最小费用流问题。但 k=2 就不知道怎么做了。
前面已经提到这类型图有向树宽是有界的。而有界有向树宽图hamiltonian cycle可以多项式时间解决[9]。甚至，如果已知存在一个解最多上山f(k)次，并且所有的长度都是多项式大小的整数，则存在一个多项式时间算法[10]。如果我们这边规定的是真的TSP(也就是每个顶点只走一次)，则f(k)=k，所以在长度都是多项式大小的整数时，有多项式时间算法。不过这并不解决我们原始的问题：因为长度未必是多项式大小的整数，而且有的顶点可能要通过很多次。

有界有向树宽图上TSP是否有多项式时间算法？ 这个问题如果能得到肯定的答案，那可是非常强的结论。因为这将是第一个在有界有向树宽图上做的路径优化问题，证明了有向树宽这个概念在优化领域终于有用了。
货架整理问题

货架整理问题和前面存取类型的问题的一大区别是物品可以被放去任何指定的地方，而不是有固定的进出口可以去。这类型问题也在交通中叫做dial-a-ride问题。可惜这个问题我们只能解决最特殊的一个货架或者两个货架的版本。
有一个道图(path graph)。其中在顶点 v 有个机器人。图上有一些物品，物品 i 初始位置是顶点 s_i 。我们想把物品 i 移动到顶点 t_i 。机器人一旦拿起了物品i就必须直接去 t_i 。中途不能放下物品。目标是用最少的时间移动所有的物品到应该去的地方，并且机器人最终回到原始的顶点。
道图版本对应的是一个货架上的物品移动。这问题被看成一个有特殊的度量的TSP问题。我们可以定义这样一个图， ij 之间有个边，边的权值为 t_i 到 s_j 的距离。则这个图上找到的TSP可以解决原先的问题。
这问题有接近线性时间的算法[11]。不仅仅在道图上，同样的问题实际上可以问在任何一个图上。比如在一个环上（对应2个货架）。甚至可以证明环上问题和最小生成树问题是等价的：两个问题都能线性规约到另一个[12]。这也证明上述度量的TSP问题也是有多项式时间解的。
而问题的解法很有意思：首先利用拓扑性质（来自于基本群+类似winding number的东西）来局限解的可能。然后利用度量的特性求得满足那拓扑性质的最优解。（我用这样的描述方法只是为了以后可以推广到其他很简单的图上去。）
可惜这个问题在树上都是NP-hard的[13]。
未解问题

• 在path和cycle的版本里，如果对机器人转向需要的时间呢？可以看出interval graph染色问题可以被规约到这个问题上。
  
• 如果图是一个"日"字形状呢？（3个货架）
  

总结

我们看到一系列不同的类似TSP的问题中，树宽能对其的多项式时间解法有一定的作用。
这让我们怀疑以下猜想为真。

猜想
有界有向树宽图上TSP问题有多项式时间算法。

若猜想为真，则本文中除了物品移动问题可以用同一个算法来解决，真美好。
这堆多项式时间算法的文章中OR方向的有OR 2篇，IIE Trans 1篇，EJOR 4篇，Computers & Industrial Engineering 1篇。没有很差的期刊呢。
题图：Hyatt Regency Zhuzhou
参考

• ^Ratliff, H. Donald; Rosenthal, Arnon S. (1983). Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem. Operations Research, 31(3), 507–521. doi:10.1287/opre.31.3.507
  
• ^Kees Jan Roodbergen; René de Koster (2001). Routing order pickers in a warehouse with a middle aisle. , 133(1), 32–43. doi:10.1016/s0377-2217(00)00177-6
  
• ^Cambazard, Hadrien; Catusse, Nicolas (2018). Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the plane. European Journal of Operational Research, (), S0377221718302716–. doi:10.1016/j.ejor.2018.03.042
  
• ^Vis, Iris F. A.; Roodbergen, Kees Jan (2009). Scheduling of Container Storage and Retrieval. Operations Research, 57(2), 456–467. doi:10.1287/opre.1080.0621
  
• ^Lee, H. F., S. K. Schaefer. 1997. Sequencing methods for automated storage and retrieval systems with dedicated storage. Computers & Industrial Engineering 32(2) 351 – 362.
  
• ^Van den Berg, J. P., A. J. R. M. Gademann. 1999. Optimal routing in an automated storage/retrieval system with dedicated storage. IIE Transactions 31(5) 407.
  
• ^Gharehgozli, A. H., Y. Yu, X. Zhang, R. de Koster. 2017b. Polynomial time algorithms to minimize total travel time in a two-depot automated storage/retrieval system. Transportation Science 51(1) 19–33.
  
• ^Gharehgozli, Amir, Chao Xu, and Wenda Zhang. “High Multiplicity Asymmetric Traveling Salesman Problem with Feedback Vertex Set and Its Application to Storage/Retrieval System.” European Journal of Operational Research 289, no. 2 (March 2021): 495–507. https://doi.org/10.1016/j.ejor.2020.07.038.
  
• ^Johnson, Thor, Neil Robertson, P.D. Seymour, and Robin Thomas. “Directed Tree-Width.” Journal of Combinatorial Theory, Series B 82, no. 1 (May 2001): 138–54. https://doi.org/10.1006/jctb.2000.2031.
  
• ^Oliveira Oliveira, Mateus de. “An Algorithmic Metatheorem for Directed Treewidth.” Discrete Applied Mathematics 204 (May 2016): 49–76. https://doi.org/10.1016/j.dam.2015.10.020.
  
• ^Atallah, Mikhail J., and S. Rao Kosaraju. “Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel.” SIAM Journal on Computing 17, no. 5 (October 1988): 849–69. https://doi.org/10.1137/0217053.
  
• ^Frederickson, Greg N. “A Note on the Complexity of a Simple Transportation Problem.” SIAM Journal on Computing 22, no. 1 (February 1993): 57–61. https://doi.org/10.1137/0222005.
  
• ^G.N. Frederickson; D.J. Guan (1993). Nonpreemptive Ensemble Motion Planning on a Tree. , 15(1), 29–60. doi:10.1006/jagm.1993.1029