论文部分内容阅读
近年来,由于经济日益发展,人均消费水平的逐年提高,使人民的生产能力、购买能力不断加强,从而货物运输在我国交通运输业的重视程度也愈发加剧。如何提高货物运输的效率成为了整个货物运输系统中最大的关注点。想要提升货物运输效率,主要从时间、地理环境、成本三个角度进行考虑。在需求明确方面,本文从多仓库多调度点的货物调度算法方向进行分析,并且结合多个根据经典的数据结构理论和多个改进的最短路径算法进行研究,最终,决定从时间复杂度,动态规划,最短路径这三个方面进行设计,改变多仓库多配送点的时间计算方式,尽可能的解决目前最短路径算法的存储冗余问题,统一时间复杂度,从而提升运输效率。本文主要参考了一些现有的算法,并且经过不断地对比每个算法的优劣,最终选择了Dijkstra和动态规划算法,它们的主要特点如下:(1)优化Dijkstra算法本文根据Dijkstra算法的拓扑结构,通过设置子集,选取子集中代价最小的节点作为开始节点。从此节点出发,寻找相邻子集中满足三角不等式的,并且未被访问过的节点作为最终节点,从而更新距离,重新设置最新子集。采用此方法不断改变拓扑结构。(2)优化动态规划算法动态规划算法的要素分为节点初始状态,递推公式和节点最终状态。拓扑结构中的子集节点作为初始状态,动态规划算法的背包问题作为动态转移方程,最新子集就相当于动态规划算法的最优解。根据优化的Dijkstra算法,每个节点获取分配目的地拓扑之后,结合坐标计算出的两节点之间的路径,形成带权邻接矩阵,从而计算出最短路径。通过对每个算法的分析,结合本文在时间、路径规划和成本三方面的要求,最后选择了Dijkstra算法和动态规划算法的混合算法来解决多仓库多配送点的货物运输路径规划问题。