中南大学数模培训-交通运输问题

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

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

3、，我们分析求解了第四个问题。第四个问题中决定方案优劣的因素有两个，一个是车辆数，一个是行车路程。所以，我们首先建立的优先考虑最短路径的模型对这个问题进行求解，求得了用5辆车总费用745元的方案。但结果中第一个客户的运送费用过高，基于货物可分的假设，我们对求得的结果进行调整，得到了4辆车总费用645元的更优方案。但这种方案受到应用范围的限制。优先考虑最短路径模型偏重路径最短，确定路径后货车辆不易调节，因此随后，我们又建立优先考虑送货车辆数模型对该问题进行求解。由于该问题数据较少，第二个模型收到的良好的效果，我们得出了用4辆车总费用680的近似最优路径。最后，我们对模型进行了评价和推广。一、问题的

4、重述运输公司配送货物的行驶路线直接影响到运输费用，运输公司往往希望通过合理的路线设计最大限度地提高人员、物资、金钱、时间等物流资源的效率(降低成本)，取得最大效益(提高服务)。同时，还可以去除多余的交错运输，并取得缓解交通、保护环境等社会效益。因此，设计合理的运输行驶路线具有很大的意义。现某运输公司有10个客户的配送任务，现针对该公司的配送路线提出如下问题：1、为已在第2个客户处的配送员设计临时为第10个客户送货的最短行驶路线；（给客户10的货已在车上）2、设计用一辆大型卡车一次为10个客户送货并回到提货点的最优行驶路线；（卡车可装下所有用户所需的货物）3、如果因资源紧张只能用两辆小型货车（车

5、容量为50个单位）运货，设计两辆货车的最短行驶路线；（已知每个客户所需货物量）4、用车容量25个单位的货车运货，在出车费、运费、行驶路程的约束条件下设计最优行驶路线。 二、问题的假设各段路况都是一样的，车子在各条路上行驶状况相同。货车在运货过程中不会发生意外。 三、符号说明 G 将客户作为顶点的赋权图Kn 赋权完全图 第i个客户 第i个客户到第j个客户的最短距离D 行车总距离C 车辆数 S 运货总费用 四、模型的建立及求解4.1问题一4.1.1用Dijkstra算法计算本题主要是求解最短路径问题，求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法。Dijkstra算法以起始点为中心向外

6、层层扩展，直到扩展到终点为止，其基本思想是按距 从近到远为顺序，依次求得到G 的各顶点的最短路和距离直至（或直至G 的所有顶点），算法结束。由问题中可得配货员从第二个客户处出发，以为起点，对原矩阵修改得 用matlab7.0对上述矩阵应用用迪克斯特拉（Dijkstra）算法计算得配送员从到的最短距离d=85。4.1.2 用Floyd算法计算Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。而Floyd算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行Dijkstra算法。可以算出任意两个节点之间的最短距离，并且代码编写简单；在matlab7.0中建

7、立如下函数对a矩阵进行处理即可得出配送员从到的最短距离d=85，路线为2-3-8-9-10。function D,R=floyd(a)n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j) v7 - v5 - v2 - v3 - v6 - v4 - v8 - v9 - v10 - v1然后我们又刚才算出来的Hamilton圈c2=1 7 5 2 3 6 4 8 9 10 1为初使圈用同样的算法计算得最短路径仍为230公里并得出新的路径。4.2.2近似算法邻近点法根据

8、题意，本题就是给定了赋权图G，然后求G 的一个权最小的Hamilton 圈的问题。首先我们要判断G是否有Hamilton 圈，在已知G 是Hamilton 图的情况下，求出一个权最小的Hamilton 圈来。给G 添加权为 的边，化为赋权完全图Kn。在Kn 中，共有(n-1)!/2个不同的Hamilton 圈。如果一一计算各Hamilton 圈的长度，再逐个比较出权最小的一个，则计算量很大，当n 较大时无法实现。对这样的问题，一般解决方法是设计较好的近似算法，求其近似最优解。用邻近法求解的一般步骤如下：Step1. 任选一点v1 V ，令 P1 = v 1, i=1.Step2. 设已得到Pi

9、= v1v2 vi, 选取Vi+1V v1,v2, vi 使得权w(vi,vi+1)最小。Step3. 若i = n ，则停止，C=Pn+VnV1= v1v2 vi v1 是一条近似的最小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。但是对于邻近点法求近似解的精

10、度，有如下定理：设赋权完全图Kn 各边的权均为正数，且权满足三角不等式：对于任意的vi，vj，vkV，w (vivj )+w (vjvk ) w( vi kv) ，则c0/c*( log2n+1)2其中c 是Kn 的最小Hamilton 圈的权，而c0是用邻近点法求得的Hamilton 圈的权。可见，邻近点法求近似解的精度也不高，且与初始点有关。4.2.3模型的评价求最短送货路线时，即是求最优圈的问题，目前还没有求解这样问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。我们采用了求最短H-圈改良圈的算法。这种算法是不可能求得最优解的，但可以我们随机选取了不同的初始圈，比较不同

11、圈的权取其中的最小值已得到最优的路径，虽然该路径与实际中的最优路径的近似程度不易衡量，但足可以满足实际应用的要求了。另外在寻找权最小Hamilton 圈,模型中给G添加了权为，就把图G转化成了赋权完全图，这样就省略了判定G 是否有Hamilton 圈的问题，使问题得到了简化。另外从邻近点法的精确度来看，由于N比较小，所以精确度相对来说还是很高的。从几种不同算法解出的结果也可以看出其精确性。4.3 问题三如果用两辆小型货车送货，势必要找出两个Hamilton 圈，我们考虑将10个客户分成两组，每辆货车负责一组客户的货物。将分好组的两组分别求出其最小权Hamilton 圈，将两个权相加即为最短路径

12、。但是，由于有一些客户间不能直达，以及车容量的限制（每辆车所载货物量50个单位），客户的分组并不能是完全严格的，一组中的点可以通过另一组中的点过度，达到最佳效果。也就是说，广义上我们将10个客户分为2组，但他们也可相交。4.3.1 分步筛选法求解进行近似计算我们可以以单程路程最短为衡量指标，货车从每一点出发都驶向离它最近的，那么最后总路程也应最短。因为问题中客户数仅为10个，所以以这种方法分组方便简单。具体做法如下：1、以为起点，那么离其最近的两点和则作为第二站分别分在两组中。2、分别以和为起点寻找到他们最近的下两个点。其中离最近的是和，已经分好组了，所以与分为一组。同理，将和分在一组。3、依

13、此类推，分组情况为：第一组 第二组 。按照我们的算法，应分在第二组，但是这样会导致第二辆货车超载，所以必须考虑将分给一组，但到不能直达，用Floyd算法计算得到最短路程30公里，经过。比将分到第而组多出10公里，权衡下为最佳选择。所以最后的分组情况为第一组 以及第二组 。分好组以后对每一组中的点利用前两个问题的算法求其最小权Hamilton 圈得到最短路径。将分组后的各点用matlab7.0处理得到两辆车的最短路径分别为c1=1 5 2 3 8 910 1 和 c2=1 7 6 4 9 1。计算得d1=160公里，d2=145公里。最后两辆车所走过的总距离为D=d1+d2=305公里。通过以上

14、算法我们得出的最后结果是：两辆车分别给客户1 5 2 8 10和客户 7 6 4 9 送货，所走的最短路程为305公里。4.4问题四这一问中约束条件更多，分析10个客户的需货量，车容量减少为25个单位使得每辆车最多不可能给超过4个的客户送货，另外每增加一辆车就会增加k（100元/辆）元的出车费，1元/公里的运费同时也给设计路线增加了约束条件。基于第二问的求解，我们还是希望先对10个客户进行分组。显然，运货总费用S=kC+D。4.4.1优先考虑最短路径模型所有货车在装好货物以后均要从v1出发，要得到最短路径，我们不妨先算出v1到各点的最短距离及路径。采用Dijkstra算法应用matlab7.0

15、进行求解得到如下结果：其中第一行为客户序号，第二行为各个客户的需货量，第三行为最短距离，第四行为得到最短距离的路径。每辆车所装货物不能超过车容量，分析客户需求量可得到每辆车最多能够送货的客户数M。设每条路径的路径度为完成路径所经历的节点个数，路径距离为完成路径所走过的路程。取Max（）最接近M的路径为第一主路径，检索其他路径，将重复点多的路径淘汰。留下路径单点，寻找含第一路径以外节点的高路径度路径以相同的方法处理，单点以路径最短为原则插入到已选的路径中去，依此类推，最后得到了以v1为顶点，遍游所有节点的路径束，且路径总路程最短。由于不考虑空车返回的费用，路径不必形成圈。最后以车容量为标准调整各

16、个路径。基于以上算法解决题目中的问题如下：分析客户需求量得到此题中M=4。v1到各点的最短路径前面我们已经用Dijkstra算法求得。第一步选出与M相近的路径有：1-5-2、1-4-3、1-7-6、1-9-10，留下的单点为v8。用Floyd算法计算v8到各个路径末点的最短距离分别为：55、25、50、35 。显然单点v8应放在第三条路径中。最后得到的四条路径分别为：1-5-2、 1-4-3-8、 1-7-6 和 1-9-10 。车辆数C=4 。v1存在与每一条路径中，但无论将v1的货物放在哪一辆车上都会使该车超载。以算法中优先考虑最短路径为原则，应再派一辆车，以最短的路径0公里为v1送货。这

17、样求得的送货方案为：车辆号路径送货点费用11-5-25、2100+40=140元21-4-3-84、3、8100+80=180元31-7-67、6100+55=155元41-9-109、10100+70=170元511100元费用合计：S=745元。 C=5此方案中v1最近但是送货费用却最高。结果不尽如人意。在货物可分的情况下，我们考虑可以将v1的货物分装在1、2号车中，这样便节省了一辆车的出车费100元，大大的优化了方案。这样处理后的送货方案为：车辆号路径送货点费用11-5-21、5、2100+40=140元21-4-3-81、4、3、8100+80=180元31-7-67、6100+55=

18、155元41-9-109、10100+70=170元费用合计：S=645元。 C=4 以上模型优先考虑最短路径，对车辆数相对较难控制，分组方法相对粗糙。但是最短距离则比较控制，一个点的位置都可能在整体上很大程度的优化结果，而这个题目中数据很少，我们很容易得出最少车辆数为4辆，因此我们又建立的新的优先考虑车辆数的模型。 4.4.2优先考虑车辆数模型由题意可知,，货物总量为94，而每辆车的最大装载量为25，故可以很容易的得到至少需要4辆车完成送货。所以我们优先考虑用四辆车的情况。即将共计10个客户分成四组，再在组内求其最小路径。更方便的是题目要求不考虑空车返回的费用，我们只需求解单程路径最短。由于

19、本题的规模不是很大(包括提货点共10个点),所以我们仍可用邻近点法解决这个问题。算法思路是找出距离提货点v1最近的四个点，将它们分别分在四组中，再分别找离这四个点最近的点，依此类推，知道所有点都被分组。基于以上算法，我们应用Dijkstra算法求出各点到v1 的距离，找到v4, v5, v7, v9(v2)离v1最近。再分别找出距离v4, v5, v7, v9(v2)距离最近的点,依此类推,直到把点全部找完为止. 由于v9和v2到v1的距离相等，所以我们分成两种情况讨论：第一种情况（第一次分组选v9）经过两次分组后计算结果如下v1-v4-v3 v1-v5-v8 v1-v7-v6 v1-v2-v

20、9现在还有v10没有考虑进去，而1-2-9和1-7-6已经满载，所以只有可能将v10添加到路线1-4-3和1-5-8中,前面已经算出v3和v8到v10的最短路径分别为60公里和30公里，而且它们都能满足容量的要求。路径距离越短越好，自然将v10分给v8 。于是，第一条合理的路径为:v1-v4-v3, v1-v5-v8-v9-v10, v1-v7-v6, v1-v2-v9.这四辆车分别给1 4 3, 5 8 10, 7 6, 2 9客户送货。最小费用为295+400=695。得到最终结果如下:车辆号路径送货点费用11-4-31、4、3100+55=155元21-5-8-9-105、8、10100

21、+80=185元31-7-67、6100+55=155元41-2-92、9100+100=200元费用合计：S=695元 C=4第二种情况可以得到 ：v1-v4-v3 v1-v5-v2 v1-v7-v6 v1-v9-v10,最后剩下v8再讨论。在上面找出的任一条路线中,都无法直接去v8，因为这样总会有车超载.，类似于深探法的思想，将v8分别换到v4或v5，v7，v9的后面,再分别讨论。 又1-7-6恰好满载，而且是最短路线，因此先不考虑。 如果将v8排v10后，虽然v8到v10的最短距离只有30公里，但是只要v9和v10到一起，就不能再给其它客户送货，如果放到v3后面，v3到v8的最短距离只有

22、25，但是会使小货车超载，因为如果按这条路线，第四辆车就只能给v1 v5 v2 送货，不满足容量的要求。所以只能将v8排在v2后面。得出结果如下：车辆号路径送货点费用11-4-31、4、3100+55=155元21-5-2-85、2、8100+100=200元31-7-67、6100+55=155元41-9-109、10100+70=170元费用合计：S=680元 C=4另外还可以考虑用如下算法求解：此题数据较少，由于货物总量为94，而每辆车的最大装载量为25，故可以很容易的得到至少需要4辆车完成送货。要使送货所需费用最小，则尽可能的使每辆车都走最短的路线。首先，仍然是应用Dijkstra算法

23、算出v1到各个节点的最短距离及路径： 40 55 40 25 55 30 55 50 70各个点所需货物数量如下8 13 6 9 7 15 10 5 12 9我们发现路线刚好使一辆车满载，而且所走的距离也最短，故我们先确定了这一条路线。剩下的三辆车总有一辆要去离最远的点，从上面所求的数据我们不难看出，从到最短的路线为，而我们又发现距离最近的点为，距离才为10，所以选择路线。由到点的距离也为10，所以可以选择路线，剩下的可通过路线连起来，最后通过计算，第一条路线装载和的货物，第二条路线装载点、和的货物，第三条路线装载点、和的货物，最后一条路线装载和的货物，每一辆车都没超载且运载量也大致相当，也尽

24、可能的沿着最短的路线走，因而所走的距离也很短，所需费用就很接近最优解。最后得到的结果为：车辆号路径送货点费用11-7-67、6100+55=155元21-9-10-31、10、3100+80=180元31-5-8-95、8、9100+65=165元41-4-3-24、3、2100+85=185元费用合计：S=680元 C=4综合以上算法的计算结果，多个小型货车送货问题的最优解为S=680，C=4路径为1 7 6、1-9-10-3、1-5-8-9、1-4-3-2和1-4-3、1-5-2-8、1-7-6、1-9-10。若假设第一个客户的货物可分则得到最优解S=645，C=4路径为1-5-2、1-4

25、-3-8、1-7-6、1-9-10。 五、模型的推广我们建立的模型解决了一系列运送货物最小路径的问题。如果我们把距离该做两点之间的直达时间则可运用我们建立的模型求解最短时间完成任务的最优路径等外围类似问题。而在现实生活中类似于运输路径的问题有很多，比如说保安在住宅区用最短的时间巡逻、邮递员走最短的距离送信、环形旅游花费最少等等。针对这些问题都可以通过我们的模型进行求解。本题所建立的模型,都是根据现有的数据资料设置变量,各变量之间关系明确,且各个参数可比较方便地得到. 参考文献1 戴一奇等 编著，图论与代数结构，北京，清华大学出版社，1995年2 徐金明 主编， MATLAB实用教程，北京 ，清

26、华大学出版社*北京交通大学出版社，2005年7月3 姜启源等 编，大学数学实验，北京，清华大学出版社，2005年2月4 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，20035 徐俊明，图论及其应用，中国科技大学出版社，19986 王树禾，图论及其算法，中国科技大学出版社，1994。 附录clear; %求一点到其他各点的距离及路径clc;M=10000;a=0 50 M 40 25 M 30 M 50 M;50 0 30 M 35 50 M 60 M M;M 30 0 15 M 30 50 25 M 60;40 M 15 0 45 30 55 20 40 65;25 15 M 45 0

27、60 10 30 M 55;M 50 30 30 60 0 25 55 35 M;30 M 50 M 10 25 0 30 45 60;M 60 25 20 30 55 30 0 10 M;20 M M 40 M 15 25 45 0 20;35 20 10 45 20 M 60 M 30 0;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1); end index2(temp)=index;endd, index1, index2function d,path=floyd(a,sp,ep) %求任意亮点间的距离和路径n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1