调度问题求解文献总结

发表于 | 分类于 | | 阅读次数

这段时间在研究自行车系统中的调度问题，进行了一些文献总结。

首先介绍下我们要研究的问题：自行车系统中由于用户需求的不平衡，导致站点经常会出现空和满的情况，那么这时候就需要调度车进行调度，在站点间（以及仓库）调运车辆，平衡各个站点的库存。

问题的简化

真实系统中的自行车调度网络，各个节点之间的行驶距离正反并不对称，也不确定能满足三角不等式，据07年的《Comments on: Static pickup and delivery problems: a classification scheme and survey》，General的TSP网络中进行路径规划求解是没法确定bound的，因此我们先简化为一个对称的满足三角不等式的网络进行研究。（怎么简化好？直接用站点间直线距离？）

symmetric

问题的类别确定

自行车调度问题和传统的pickup and delivery问题非常类似，因此，我们可以首先根据文献确定我们要研究的问题的类型：

根据07年的文章《Static pickup and delivery problems: a classification scheme and survey》，根据问题的structure，可以分为many-to-many problems和one-to-many-to-one problems，many-to-many就是说网络中任意节点都可以作为source或者destination，而one-to-many-to-one problems只能从一个存储点拿车，路径上pick up的东西是要带回存储点而不能放下来。由于我们研究的调度问题是可以从车较多的站点拿车去补充车比较少的站点，因此这是一个many-to-many的问题。

对于many-to-many的问题，大致又可以分为Swapping Problem，One-Commodity Pickup and Delivery Traveling Salesman Problem还有Q-Delivery Traveling Salesman Problem。

  • 第一种Swapping Problem是针对多种货物交换问题，不适合我们的场景；

  • 1-PDTSP是一辆车、单种货物的问题，然而要求解出的路径是Hamilton回路，而这里我们如果一定要求是Hamilton回路的话，假设一种极端情况，所有站点都是需要车，而且需要的数目大于调运车的容量，那么肯定是无解，因此，为了保证每种情况都有解，我们并不要求路径是Hamilton回路（1-PDTSP问题在2004年的两篇文章《A branck-and-cut algorithm for a traveling salesman problem with pickup and delivery》和《Heuristics for the one-commodity pickup-and-delivery traveling salesman problem》中分别提出了精确解法和启发式解法）；

  • Q-DTSP是1-PDTSP的特例，外加了每个点的需求必须是1或-1，仓库的需求设置为0。但是更general一些的是G-Q-DTSP，它就是不要求Hamilton回路的1-PDTSP问题。

综上，我们所研究的自行车调度问题是G-Q-DTSP问题，又称CTSPPD。

问题的解法

  1. Q-DTSP这个问题研究出现始于1999年的《Approximated capacitated routing and delivery problems》，作者给出了worst-case bound为9.5的启发式搜索算法。

  2. 1999年的《Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries》当中改进了前者的算法，给出了worst-case bound为(7-3/k)的启发式搜索算法，k是车的capacity（也是现在正在参考的）,大致思想是先把每个站点变为需求是1或者-1的许多站点（位置不变），把全部站点分为pickup和delivery两部分（数目相等），先在每个部分单独求解tsp，然后pickup部分走tsp的路径装满一辆车后，选择delivery部分的任一点，过去进行delivery，再回来，重复选择其他的delivery的点进行搜索。

  3. 普通图中有一篇2002年的paper《Algorithms for capacitated vehicle routing》给出了5-approximation算法。但是这个算法生成的路径起点不固定，如果起点和终点固定系数还会增加1，另外作者给出的证明实际也只给到了6.5-approximation，所以这样比99年的那个算法还差，于是决定放弃掉了。

  4. 另外一部分研究Q-DTSP的问题基本上都是基于line或者tree类型的问题，在2006年的paper《The one-commodity pickup and delivery traveling salesman problem on a path or a tree》中，作者提出了复杂度为$O(\frac{n^2}{min{Q,n}})$的算法，不过没给出bound。在文章《The capacitated traveling salesman problem with pickups and deliveries on a tree》中，Tree类型的问题还有2-approximation算法，甚至在一篇09年博士论文《Approximation algorithms for the capacitated vehicle routing problem》中号称approximation ratio做到了5/3。（但是我们的调度网络能够从一个graph改成tree结构吗？）

  5. 另外还有一些tabu search之类的启发式算法，这样的基本都是不给出bound的，但是也是目前最普遍的求解方法。

如何评估算法的性能

很多paper提出算法后，将其应用在某个很久之前就已经提出的网络中，网络的各种参数已经给出，最优解也已经给出，所以他们经常列出一个表格，和最优解进行对比，或者同时再和其他人的解进行对比。

evaluation