运输问题-数学建模

《运输问题-数学建模》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、运输问题摘要本文针对某运输公司送货路线的问题进行了深入的研究设计。首先，针对第一问中临时为客户10配送货物的要求，我们用Dijkstra算法对其进行了求解，得出了最短85公里的运输路径。但是由于Dijkstra算法遍历计算的节点很多，所以效率低，我们又应用更为简单有效的Floyd算法进行求解，最后得出与之前相同的结果，并确定路线为v2->v3->v8->v9->v10□其次，第二问类似于旅行商问题，目前述没有求解这样问题的有效算法，所以我们希望建立一个方法以获得相当好（但不一定最优）的解。我们采用了求最短H…圈改良圈的算法。首先求一个Ham讥on圈,然后适

2、当修改以得到具有较小权的另一个Hamilton圈。基于这种算法，应用matlab7.0我们计算出最短行驶路线距离为230公里，路径为vl->v7->v5->v2->v3->v6->v4->v8->v9->vl0->vl,并且路线并不唯一，权为230的路径有很多条。另外，我们还用近似算法一一邻近点法进行计算，最后得出最短距离225公里，同时也得出了相应的路线。最后我们还对上述算法进行了评价及推广。再次，针对第三问中改用两辆小型货车的路线设计问题。我们首先建立分步筛选模型对10个客户进行分组，使得每一组的路径最短。再应用第二问的模型分别求解为两组客户送货的最优

3、路线。我们求得最后的分组情况为第一组V1V5V2V3V8V10以及第二组V1V7V6V4V9o所走最短路程305公里。再次，我们分析求解了第四个问题。第四个问题中决定方案优劣的因素有两个，一个是车辆数，一个是行车路程。所以，我们首先建立的优先考虑最短路径的模型对这个问题进行求解，求得了用5辆车总费用745元的方案。但结果中第一个客户的运送费用过高，基于货物可分的假设，我们对求得的结果进行调整,得到了4辆车总费用645元的更优方案。但这种方案受到应用范围的限制。优先考虑最短路径模型偏垂路径最短，确定路径后货车辆不易调节，因此随后，我们又建立优先考虑送货车辆数

4、模型对该问题进行求解。由于该问题数据较少，第二个模型收到的良好的效果，我们得岀了用4辆车总费用680的近似最优路径。最后，我们对模型进行了评价和推广。一、问题的重述运输公司配送货物的行驶路线直接影响到运输费用，运输公司往往希望通过合理的路线设计最大限度地提高人员、物资、金钱、时间等物流资源的效率（降低成本），取得最大效益（提高服务）。同时，述可以去除多余的交错运输，并取得缓解交通、保护环境等社会效益。因此，设计合理的运输行驶路线具有很大的意义。现某运输公司有10个客户的配送任务，现针对该公司的配送路线提出如下问题：1、为己在第2个客户处的配送员设计临时为第

5、10个客户送货的最短行驶路线；（给客户10的货已在车上）2、设计用一辆大型卡车一次为10个客户送货并回到提货点的最优行驶路线;（卡车可装下所有用户所需的货物）3、如果因资源紧张只能用两辆小型货车（车容量为50个单位）运货，设计两辆货车的最短行驶路线；（已知每个客户所需货物量）4、用车容量25个单位的货车运货，在出车费、运费、行驶路程的约束条件下设计最优行驶路线。二、问题的假设1、各段路况都是一样的，车子在各条路上行驶状况相同。2、货车在运货过程中不会发生意外。三、符号说明G将客户作为顶点的赋权图Kn赋权完全图Vi第i个客户dij第i个客户到第j个客户的最短

6、距离D行车总距离C车辆数s运货总费用四、模型的建立及求解4.1问题一4.1.1用Dijkstra算法计算本题主要是求解最短路径问题，求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法。Dijkstra算法以起始点为中心向外层层扩展，直到扩展到终点为止，其基木思想是按距M从近到远为顺序，依次求得卩1到G的各顶点的最短路和距离直至V10（或直至G的所有顶点），算法结束。由问题中可得配货员从第二个客户处出发，以卩2为起点，对原矩阵修改得123456789101「05030OO3550OO60OOOO2500OO4025OO30OO50OO330OO015

7、OO305025OO604OO4015045305520406551525OO450601030OO55650OO3030600255535OO7OO3050OO10250304560860OO2520305530010OO9OO20OO40OO152545020102035104520OO60OO300用matlab7.0对上述矩阵应用用迪克斯特拉（Dijkstra）算法计算得配送员从卩2到V10的最短距离d=85o4.1.2用Floyd算法计算Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。而Floyd算法简单有效，

8、由于三重循环结构紧凑，对于稠密图，效率要高于执行Dijkstra算