运输问题-数学建模.docx

运输问题摘要本文针对某运输公司送货路线的问题进行了深入的研究设计。首先,针对第一问中临时为客户 10 配送货物的要求,我们用 Dijkstra 算法对其进行了求解,得出了最短 85 公里的运输路径。但是由于 Dijkstra 算法遍历计算的节点很多,所以效率低,我们又应用更为简单有效的 Floyd 算法进行求解, 最后得出与之前相同的结果,并确定路线为 v2->v3->v8->v9->v10 。其次,第二问类似于旅行商问题,目前还没有求解这样问题的有效算法,所以我们希望建立一个方法以获得相当好(但不一定最优)的解。我们采用了求最短 H--- 圈改良圈的算法。首先求一个 Hamilton 圈, 然后适当修改以得到具有较小权的另一个 Hamilton 圈。基于这种算法,应用 我们计算出最短行驶路线距离为 230 公里,路径为 v1 ->v 7 ->v 5 ->v 2 ->v 3 ->v 6 ->v 4 ->v8 ->v9 -> v10 ->v1 ,并且路线并不唯一,权为 230 的路径有很多条。另外,我们还用近似算法——邻近点法进行计算,最后得出最短距离 225 公里,同时也得出了相应的路线。最后我们还对上述算法进行了评价及推广。再次,针对第三问中改用两辆小型货车的路线设计问题。我们首先建立分步筛选模型对 10 个客户进行分组,使得每一组的路径最短。再应用第二问的模型分别求解为两组客户送货的最优路线。我们求得最后的分组情况为第一组 1 5 2 3 8 10 v v v v v v 以及第二组 1 7 6 4 9 v v v v v 。所走最短路程 305 公里。再次,我们分析求解了第四个问题。第四个问题中决定方案优劣的因素有两个,一个是车辆数,一个是行车路程。所以,我们首先建立的优先考虑最短路径的模型对这个问题进行求解,求得了用 5辆车总费用 745 元的方案。但结果中第一个客户的运送费用过高,基于货物可分的假设,我们对求得的结果进行调整, 得到了 4辆车总费用 645 元的更优方案。但这种方案受到应用范围的限制。优先考虑最短路径模型偏重路径最短,确定路径后货车辆不易调节,因此随后,我们又建立优先考虑送货车辆数模型对该问题进行求解。由于该问题数据较少,第二个模型收到的良好的效果,我们得出了用 4辆车总费用 680 的近似最优路径。最后,我们对模型进行了评价和推广。一、问题的重述运输公司配送货物的行驶路线直接影响到运输费用,运输公司往往希望通过合理的路线设计最大限度地提高人员、物资、金钱、时间等物流资源的效率(降低成本),取得最大效益(提高服务)。同时, 还可以去除多余的交错运输,并取得缓解交通、保护环境等社会效益。因此,设计合理的运输行驶路线具有很大的意义。现某运输公司有 10 个客户的配送任务,现针对该公司的配送路线提出如下问题: 1、为已在第 2个客户处的配送员设计临时为第 10个客户送货的最短行驶路线;(给客户 10的货已在车上) 2、设计用一辆大型卡车一次为 10个客户送货并回到提货点的最优行驶路线; (卡车可装下所有用户所需的货物) 3、如果因资源紧张只能用两辆小型货车(车容量为 50个单位)运货,设计两辆货车的最短行驶路线;(已知每个客户所需货物量) 4、用车容量 25个单位的货车运货,在出车费、运费、行驶路程的约束条件下设计最优行驶路线。二、问题的假设 1、各段路况都是一样的,车子在各条路上行驶状况相同。 2、货车在运货过程中不会发生意外。三、符号说明 G将客户作为顶点的赋权图 Kn赋权完全图 iv 第 i个客户 ijd 第i个客户到第 j个客户的最短距离 D行车总距离 C车辆数 S运货总费用四、模型的建立及求解 问题一 用 D ijk stra 算法计算本题主要是求解最短路径问题,求最短路已有成熟的算法:迪克斯特拉( D ijk stra )算法。 D ijk stra 算法以起始点为中心向外层层扩展, 直到扩展到终点为止,其基本思想是按距 1v 从近到远为顺序,依次求得 1v 到 G的各顶点的最短路和距离直至 10v (或直至 G 的所有顶点) ,算法结束。由问题中可得配货员从第二个客户处出发,以 2v 为起点,对原矩阵修改得 1 2 3 4 5 6 7 8 9 10 1 0 50 30 35 50 60 2 50 0 40 25 30 50 3 30 0 15 30 50 25 60 4 40 15 0 45 30 55 20 40 65 5 15 25 45 0 60 10 30 55 6 50 30 30 60 0 25 55 35 7 30 50 10 25 0 30 45 60 8 60 25 20 30 55