基于改进的Kruskal算法的运输规划方法  

Transportation planning method based on improved Kruskal algorithm

作　　者：汪勤思 何毓辉 WANG Qinsi;HE Yuhui(School of Optical and Electronic Information,Huazhong University of Science and Technology,Wuhan Hubei 430070,China)

机构地区：[1]华中科技大学光学与电子信息学院,武汉430070

出　　处：《计算机应用》2021年第S01期149-152,共4页journal of Computer Applications

基　　金：国家重点研发计划项目(2018YFB0804002)。

摘　　要：针对带转运中心约束的运输规划问题,通过重心法计算转运中心的约束点,从图论角度出发构建带约束条件的最小生成树模型,采用改进的Kruskal算法对模型进行求解。首先,研究影响运输成本的相关因素,通过运输成本模型构建和对运输距离、运输总载货量、货物密度三个因素的综合考虑,将最小总运输成本问题转化为部分节点固定的连通网最短路径问题;对Kruskal算法进行改进给出了解决此问题的方法;最后通过对实际应用进行优化求解,给出了该模型下各一级代理管辖代理商以及具体运输及转运方案。实验结果表明运用该方法提出的运输方案比现有距离判断法给出的运输方案节约成本约84.23%。所提方法有效解决了带转运中心约束的运输问题,给出了一个相对精确的完整解。Concerning the transportation planing problem with transshipment center,the center-of-gravity method was used to calculate the constraint point of the transshipment center,and the improved Kruskal algorithm was used to calculate the minimal spanning tree model with constraints constructed from the perspective of graph theory.First,the relevant factors that affected the transportation cost were studied,by constructing transportation cost and considering transportation distance,total cargo capacity and cargo density,the problem of minimum total transportation cost was transformed into the problem of the shortest path in the network with some fixed nodes.Then the Kruskal algorithm was improved to solve this problem.Finally,the distribution of the agents and the specific transportation and trans-shipment scheme under the model were given by optimizing and solving the actual applications.Experimental results show that the transportation scheme proposed by the proposed method saved about 84.23% of the cost compared with the transportation scheme given by the existing distance judgment methods.The proposed method can effectively solve the transportation problem with transshipment center constraints and has a relatively accurate complete solution.

关 键 词：运输路径规划 约束 KRUSKAL算法 最小总运输成本 重心法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]