运输问题-数学建模.docxVIP

运输问题 摘要 本文针对某运输公司送货路线的问题进行了深入的研究设计。 首先，针对第一问中临时为客户10配送货物的要求，我们用Dijkstra算法对其进行了求解，得出了最短85公里的运输路径。但是由于Dijkstra算法遍历计算的节点很多，所以效率低，我们又应用更为简单有效的Floyd算法进行求解，最后得出与之前相同的结果，并确定路线为v2-v3-v8-v9-v10。 其次，第二问类似于旅行商问题，目前还没有求解这样问题的有效算法，所以我们希望建立一个方法以获得相当好（但不一定最优）的解。我们采用了求最短H---圈改良圈的算法。首先求一个Hamilton圈 ，然后适当修改以得到具有较小权的另一个Hamilton圈。基于这种算法，应用matlab7.0我们计算出最短行驶路线距离为230公里，路径为v1-v7 -v5 -v2 -v3 -v6 -v4- v8 - v9 - v10-v1，并且路线并不唯一，权为230的路径有很多条。另外，我们还用近似算法——邻近点法进行计算，最后得出最短距离225公里，同时也得出了相应的路线。最后我们还对上述算法进行了评价及推广。 再次，针对第三问中改用两辆小型货车的路线设计问题。我们首先建立分步筛选模型对10个客户进行分组，使得每一组的路径最短。再应用第二问的模型分别求解为两组客户送货的最优路线。我们求得最后的分组情况为第一组 以及第二组 。所走最短路程305公里。 再次，我们分析求解了第四个问题。第四个问题中决定方案优劣的因素有两个，一个是车辆数，一个是行车路程。所以，我们首先建立的优先考虑最短路径的模型对这个问题进行求解，求得了用5辆车总费用745元的方案。但结果中第一个客户的运送费用过高，基于货物可分的假设，我们对求得的结果进行调整，得到了4辆车总费用645元的更优方案。但这种方案受到应用范围的限制。优先考虑最短路径模型偏重路径最短，确定路径后货车辆不易调节，因此随后，我们又建立优先考虑送货车辆数模型对该问题进行求解。由于该问题数据较少，第二个模型收到的良好的效果，我们得出了用4辆车总费用680的近似最优路径。 最后，我们对模型进行了评价和推广。 一、问题的重述 运输公司配送货物的行驶路线直接影响到运输费用，运输公司往往希望通过合理的路线设计最大限度地提高人员、物资、金钱、时间等物流资源的效率(降低成本)，取得最大效益(提高服务)。同时，还可以去除多余的交错运输，并取得缓解交通、保护环境等社会效益。因此，设计合理的运输行驶路线具有很大的意义。现某运输公司有10个客户的配送任务，现针对该公司的配送路线提出如下问题： 1、为已在第2个客户处的配送员设计临时为第10个客户送货的最短行驶路线；（给客户10的货已在车上） 2、设计用一辆大型卡车一次为10个客户送货并回到提货点的最优行驶路线；（卡车可装下所有用户所需的货物） 3、如果因资源紧张只能用两辆小型货车（车容量为50个单位）运货，设计两辆货车的最短行驶路线；（已知每个客户所需货物量） 4、用车容量25个单位的货车运货，在出车费、运费、行驶路程的约束条件下设计最优行驶路线。 二、问题的假设 各段路况都是一样的，车子在各条路上行驶状况相同。 货车在运货过程中不会发生意外。 三、符号说明 G 将客户作为顶点的赋权图 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算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。而Floyd算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行Dijkstra算法。可以算出任意两个节点之间的最短距离，并且代码编写简单；在matlab7.0中建立如下函数对a矩阵进行处理即可得出配送员从到的最短距离d=