详情

原文传递带集结点的多源最短路径算法

论文题名：	带集结点的多源最短路径算法
关键词：	物流配送;集结点;多源最短路径;斯坦纳树类算法;动态规划
摘要：	城市物流业务的高速发展使得物流配送业务对路径规划算法提出了更高的要求。多源最短路径最短距离查询问题是路网中基础且常见的问题，并且该问题在确定集结点位置和运输路线规划计算中起到基础支撑作用。本文研究从多个源点出发的运输品集结到集结点，再从集结点统一配送来缩短总运输距离，进而节约运输成本的运输方式，并证明该问题是NP-hard的。在该问题中，集结点的位置是未知的，确定集结点的位置和计算最短路径两个目标作为条件是彼此约束的。本文主要提出了分支界定法、基本动态规划算法和高级动态规划算法来解决该问题。　　第一，在假设集结点的位置已知条件下，将该问题转化为搜索问题。在集结点位置确定后，用贪心算法来计算集结点到源点的最短距离。通过暴力枚举所有可能的集结点的位置，选择最优的集结点的集合。为了减少暴力枚举的搜索空间，本文提出在距离图上基于搜索树的分支界限法的方法，通过剪枝，提前排除不可能的集结点集合，逐个确定最有可能的最优集结点的位置。然而，集结点在整张地图上出现的排列组合的方式本身是指数级别的，剪枝后的计算量仍然无法在接受时间内给出解。因此，通过观察解本身的性质本文提出了另外两种算法。　　第二，在分析路径本身树结构性质的条件下，将搜索问题转化为最优化问题。通过分析路径本身在距离图上的结构，发现解路径本身具有树的性质。并且，可以确认将本问题分解成更小的独立子问题，子问题有最优子结构，因此，逐个解决子问题后，通过将子问题合并，最终可得该问题的解。通过定义子树的状态和状态转移方程，针对该问题本文提出基本动态规划的算法来计算所有子树的距离和。实验表明该算法比分支界限法要最快要快1000倍。然而，距离图忽略了图本身的局部信息。图中每个节点都受其邻居的约束。　　第三，在考虑到图本身的局部约束下，提出高级动态规划算法。该算法相较于基本动态规划算法引入一个新的维度，并且该算法更精细的考虑了每个顶点的邻居信息，减少了不必要的超出近邻范围的搜索，使算法随着图的大小近似线性的增长。通过对比实验很好的证明了提出的高级动态规划算法相较于分支界定法和基本动态规划算法的优越性，并且通过在城市规模的图上的运行实验，证明了高级动态规划算法在实际运行中有良好的表现。
作者：	王卓然
专业：	计算机技术
导师：	张帆
授予学位：	硕士
授予学位单位：	广州大学
学位年度：	2022