【国家级精品课程】-中南大学-数学建模-lingo-matlab-优化建模-数模培训-全国赛论文-交通运输问题.doc

运输问题 摘要 本文针对某运输公司送货路线的问题进行了深入的研究设计。 首先，针对第一问中临时为客户10配送货物的要求，我们用Dijkstra算法对其进行了求解，得出了最短85公里的运输路径。但是由于Dijkstra算法遍历计算的节点很多，所以效率低1-v7 -v5 -v2 -v3 -v6 -v4- v8 - v9 - v10-v1，并且路线并不唯一，权为230的路径有很多条。另外，我们还用近似算法——邻近点法进行计算，最后得出最短距离225公里，同时也得出了相应的路线。最后我们还对上述算法进行了评价及推广。 再次，针对第三问中改用两辆小型货车的路线设计问题。我们首先建立分步筛选模型对10个客户进行分组，使得每一组的路径最短。再应用第二问的模型分别求解为两组客户送货的最优路线。我们求得最后的分组情况为第一组 以及第二组 。所走最短路程305公里。 再次，我们分析求解了第四个问题。第四个问题中决定方案优劣的因素有两个，一个是车辆数，一个是行车路程。所以，我们首先建立的优先考虑最短路径的模型对这个问题进行求解，求得了用5辆车总费用745元的方案。但结果中第一个客户的运送费用过高，基于货物可分的假设，我们对求得的结果进行调整，得到了4辆车总费用645元的更优方案。但这种方案受到应用范围的限制。优先考虑最短路径模型偏重路径最短，确定路径后货车辆不易调节，因此随后，我们又建立优先考虑送货车辆数模型对该问题进行求解。由于该问题数据较少，第二个模型收到的良好的效果，我们得出了用4辆车总费用680的近似最优路径。 最后，我们对模型进行了评价和推广。 一、问题的重述 运输公司配送货物的行驶路线直接影响到运输费用，运输公司往往希望通过合理的路线设计最大限度地提高人员、物资、金钱、时间等物流资源的效率(降低成本)，取得最大效益(提高服务)。还可以去除多余的交错运输，并取得缓解交通、保护环境等社会效益。Kn 赋权完全图 第i个客户 第i个客户到第j个客户的最短距离 D 行车总距离 C 车辆数 S 运货总费用 四、模型的建立及求解 4.1问题一 4.1.1用Dijkstra算法计算 本题主要是求解最短路径问题，求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法。Dijkstra算法以起始点为中心向外层层扩展，直到扩展到终点为止 从近到远为顺序，依次求得到G 的各顶点的最短路和距离直至（或直至G 的所有顶点），算法结束。由问题中可得配货员从第二个客户处出发，以为起点，对原矩阵修改得 用matlab7.0对上述矩阵应用用迪克斯特拉（Dijkstra）算法计算得配送员从到的最短距离d=85。 4.1.2 用Floyd算法计算 Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。到的最短距离d=85，路线为2-3-8-9-10。 function [D,R]=floyd(a) 　　n=size(a,1); 　　D=a 　　for i=1:n 　　for j=1:n 　　R(i,j)=j; 　　end 　　end 　　R 　　for k=1:n 　　for i=1:n 　　for j=1:n 　　if D(i,k)+D(k,j)D(i,j) 　　D(i,j)=D(i,k)+D(k,j); 　　R(i,j)=R(i,k); 　　end 　　end 　　end 　　k 　　D 　　R 　　end ，构造新的Hamilton圈: , 它是由C 中删去边 和 ，添加边 和 而得到的。若 ，则以 代替C ， 叫做 C的改良圈。 （ii）转（i），直至无法改进，停止。 用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。 这个算法的优劣程度有时能用Kruskal算法加以说明。假设C 是 G中的最优圈。则对于任何顶点v ， 是在 中的Hamilton轨，因而也是 的生成树。由此推知：若 T是 中的最优树，同时 e和 f是和 v关联的两条边，并使得 尽可能小，则 将是 的一个下界。 基于以上算法，应用matlab7.0以Hamilton圈c1=[1 5 7 6 3 4 8 9 10 2 1]为初始圈计算得最短路程为230公里，路径为 v1- v7 - v5 - v2 - v3 - v6 - v4 - v8 - v9 - v10 - v1 然后我们又刚才算出来的Hamilton圈c2=[1 7 5 2 3 6 4 8 9 10 1]为初使圈用同