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

运输问题摘要本文针对某运输公司送货路线的问题进行了深入的研究设计。首先，针对第一问中临时为客户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个客户进行分组，使得每一组的路径最短。再应用第二问的模型分别求解为两组客户送货的最优路线。我们求得最后的分组情况为第一组1523810vvvvvv以及第二组17649vvvvv。所走最短路程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运货总费用四、模型的建立及求解4.1问题一4.1.1用Dijkstra算法计算本题主要是求解最短路径问题，求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法。Dijkstra算法以起始点为中心向外层层扩展，直到扩展到终点为止，其基本思想是按距1v从近到远为顺序，依次求得1v到G的各顶点的最短路和距离直至10v（或直至G的所有顶点），算法结束。由问题中可得配货员从第二个客户处出发，以2v为起点，对原矩阵修改得123456789101050303550602500402530503300153050256044015045305520406551525450601030556503030600255535730501025030456086025203055300109204015254502010203510452060300用matlab7.0对上述矩阵应用用迪克斯特拉（Dijkstra）算法计算得配送员从2v到10v的最短距离d=85。4.1.2用Floyd算法计算Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。而Floyd算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行Dijkstra算法。可以算出任意两个节点之间的最短距离，并且代码编写简单；在matlab7.0中建立如下函数对a矩阵进行处理即可得出配送员从2v到10v的最短距离d=85，路线为2-3-8-9-10。function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRend4.1.3模型的评价对于该问题我们建立了图论中求最短路径的模型，在求两个客户之间的最短路线时我们使用了Dijkstra和Floyd两种算法，两算法的时间复杂度都为O(n^3)，在计算机上运行的时间挺短，在实际应用中处理不多的数据时具有很强的实时性。4.2问题二4.2.1旅行商问题模型这个问题可以看做是一个旅行商问题，求解的一个可行的办法是首先求一个Hamilton圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈。（i）对于nji11，构造新的Hamilton圈:,12112121vvvvvvvvvvvCnjjijjjiij它是由C中删去边1iivv和1jjvv，添加边jivv和11jivv而得到的。若)()()()(1111jjiijijivvwvvwvvwvvw，则以ijC代替C，ijC叫做C的改良圈。（ii）转（i），直至无法改进，停止。用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。这个算法的优劣程度有时能用Kruskal算法加以说明。假设C是G中的最优圈。则对于任何顶点v，vC是在vG中的Hamilton轨，因而也是vG的生成树。由此推知：若T是vG中的最优树，同时e和f是和v关联的两条边，并使得)()(fwew尽可能小，则)()()(fwewTw将是)(Cw的一个下界。基于以上算法，应用matlab7.0以Hamilton圈c1=[157634891021]为初始圈计算得最短路程为230公里，路径为v1-v7-v5-v2-v3-v6-v4-v8-v9-v10-v1然后我们又刚才算出来的Hamilton圈c2=[175236489101]为初使圈用同样的算法计算得最短路径仍为230公里并得出新的路径。4.2.2近似算法－邻近点法根据题意，本题就是给定了赋权图G，然后求G的一个权最小的Hamilton圈的问题。首先我们要判断G是否有Hamilton圈，在已知G是Hamilton图的情况下，求出一个权最小的Hamilton圈来。给G添加权为∞的边，化为赋权完全图Kn。在Kn中，共有(n-1)!/2个不同的Hamilton圈。如果一一计算各Hamilton圈的长度，再逐个比较出权最小的一个，则计算量很大，当n较大时无法实现。对这样的问题，一般解决方法是设计较好的近似算法，求其近似最优解。用邻近法求解的一般步骤如下：Step1.任选一点v1∈V，令P1=v1,i=1.Step2.设已得到Pi=v1v2…vi,选取Vi+1∈V\{v1,v2,…vi}使得权w(vi,vi+1)最小。Step3.若i=n，则停止，C=Pn+VnV1=v1v2…viv1是一条近似的最小Hamilton圈；否则i=i+1，转step2。用邻近点法当n=10时，从v1出发，根据邻近法，可得两个近似解：v1-v5-v7-v6-v3-v4-v8-v9-v10-v2-v1，权为225；v1-v5-v7-v6-v4-v3-v8-v9-v10-v2-v1,，权为230。所以最优解是：v1-v5-v7-v6-v3-v4-v8-v9-v10-v2-v1，权为225。但是对于邻近点法求近似解的精度，有如下定理：设赋权完全图Kn各边的权均为正数，且权满足三角不等式：对于任意的vi，vj，vk∈V，w(vivj)+w(vjvk)≥w(vikv)，则c0/c*≤([log2n]+1)\2其中c∗是Kn的最小Hamilton圈的权，而c0是用邻近点法求得的Hamilton圈的权。可见，邻近点法求近似解的精度也不高，且与初始点有关。4.2.3模型的评价求最短送货路线时，即是求最优圈的问题，目前还没有求解这样问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。我们采用了求最短H---圈改良圈的算法。这种算法是不可能求得最优解的，但可以我们随机选取了不同的初始圈，比较不同圈的权取其中的最小值已得到最优的路径，虽然该路径与实际中的最优路径的近似程度不易衡量，但足可以满足实际应用的要求了。另外在寻找权最小Hamilton圈,模型中给G添加了权为∞，就把图G转化成了赋权完全图，这样就省略了判定G是否有Hamilton圈的问题，使问题得到了简化。另外从邻近点法的精确度来看，由于N比较小，所以精确度相对来说还是很高的。从几种不同算法解出的结果也可以看出其精确性。4.3问题三如果用两辆小型货车送货，势必要找出两个Hamilton圈，我们考虑将10个客户分成两组，每辆货车负责一组客户的货物。将分好组的两组分别求出其最小权Hamilton圈，将两个权相加即为最短路径。但是，由于有一些客户间不能直达，以及车容量的限制（每辆车所载货物量≤50个单位），客户的分组并不能是完全严格的，一组中的点可以通过另一组中的点过度，达到最佳效果。也就是说，广义上我们将10个客户分为2组，但他们也可相交。4.3.1分步筛选法求解进行近似计算我们可以以单程路程最短为衡量指标，货车从每一点iv出发都驶向离它最近的jv，那么最后总路程也应最短。因为问题中客户数仅为10个，所以以这种方法分组方便简单。具体做法如下：1、以1v为起点，那么离其最近的两点5v和7v则作为第二站分别分在两组中。2、分别以5v和7v为起点寻找到他们最近的下两个点。其中离5v最近的是2v和7v，7v已经分好组了，所以2v与5v分为一组。同理，将6v和7v分在一组。3、依此类推，分组情况为：第一组15238vvvvv第二组17649vvvvv。按照我们的算法，10v应分在第二组，但是这样会导致第二辆货车超载，所以必须考虑将10v分给一组，但8v到10v不能直达，用Floyd算法计算得8v到10v最短路程30公里，经过9v。比将分到第而组多出10公里，权衡下为最佳选择。所以最后的分组情况为第一组1523810vvvvvv以及第二组17649vvvvv。分好组以后对每一组中的点利用前两个问题的算法求其最小权Hamilton圈得到最短路径。将分组后的各点用matlab7.0处理得到两辆车的最短路径分别为c1=[152389101]和c2=[176491]。计算得d1=160公里，d2=145公里。最后两辆车所走过的总距离为D=d1+d2=305公里。通过以上算法我们得出的最后结果是：两辆车分别给客户152810和