运输问题摘要本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal 算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。
关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。
考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。
关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。
首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。
即最短路线为：-9-10-2-1。
但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。
关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。
这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。
因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。
得到优化结果为：第一辆车：-1，第二辆车：，总路程为280公里。
关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。
根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。
最短总路线为245公里，最小总费用为645。
关键词： Floyd算法 Kruskal算法整数规划旅行商问题一、问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(,)i j(,1,,10)i j=位置上的数表示（其中∞表示两个客户之间无直接的路线到达）。
1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。
2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。
3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。
每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。
4、如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？二、问题分析关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd 算法对其进行分析。
考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab 软件对其进行编程求解。
关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是寻找一条最短的行车路线。
首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal 算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：21098436751v v v v v v v v v v →→→→→→→→→；然后利用问题一的Floyd 算法和程序，能求得从客户2到客户1（提货点）的最短路线是：12v v →，路程为50公里。
但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文又根据路程最短建立以路程最短为目标函数的整数规划模型；最后，利用LINGO 软件对其进行编程求解。
关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。
这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。
因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal 算法结合题中所给的邻接矩阵进行优化。
关于问题四，我们首先用Matlab 软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。
三、模型假设1.假设客户级别平等；2.假设不考虑装卸车费用；3.假设货车不发生意外事故；4.假设运输过程中货物无损失；四、符号说明:ij v 不同的客户102.1;102.1 ==j i ；:ij l 从客户i v 到客户j v 的距离；个客户的距离个客户到第从第j i c ij :；个客户所需的货物量第j a j :；:z 总路程；五、模型的建立与求解问题一模型的建立与求解问题一是要找出从客户2到客户10的最短路径，本文利用Floyd 算法对此文进行求解。
为计算方便，令网络的权矩阵为j i ij n n ij v v l d D 到为,)(⨯=的距离。
Floyd 算法基本步骤为：（1）输入权矩阵D D =)0(。
（2）计算),,3,2,1()()()(n k d D n n k ij k ==⨯其中 ],min[)1()1()1()(---+=k jk k ik k ij k ij d d d d（3）n n n ij n d D ⨯=)()()(中元素)(n ijd 就是i v 到j v 的最短路长。
在本文计算中10=n ，对Floyd 算法进行编程（程序见附录1），利用Matlab 软件进行求解。
运行结果如下：a =0 40 55 40 25 55 30 55 50 7050 0 30 45 35 50 45 55 65 8555 30 0 15 55 30 50 25 35 5540 45 15 0 45 30 50 20 30 5025 15 45 45 0 35 10 30 40 5555 50 30 30 35 0 25 50 35 5530 25 50 50 10 25 0 30 40 6030 45 25 20 30 25 30 0 10 3020 40 30 40 35 15 25 45 0 2035 20 10 25 20 40 30 35 30 0path =1 5 4 4 5 7 7 5 9 91 2 3 3 5 6 5 3 3 34 2 3 4 8 6 7 8 8 81 3 3 4 5 6 8 8 8 81 2 2 4 5 7 7 8 8 107 2 3 4 7 6 7 4 9 9153****88109 5 3 4 5 9 7 8 9 91 10 10 4 7 6 7 8 9 101 2 3 3 5 3 5 3 9 10请输入起点2请输入终点10238910由运行结果可以得出运货员从客户2到客户10的最短路径是：总路程为85公里。
问题二模型的建立与求解运输公司为这10个客户配送货物问题实际上是寻找一条最短的行车路线。
当不考虑送货员返回提货点的时候，本文利用最小生成树问题中的Kruskal 算法结合题中所给的邻接矩阵，很快可以得到无回路的最短路线。
Kruskal 算法基本步骤：每步从未选的边中选取边e ，使它与已选边不够成圈，且e 是未选边中的最小权边，知道选够1-n 条边为止。
利用最小生成树问题中的Kruskal 算法结合题中所给的邻接矩阵，很快可以得到以下最小生成树：这两棵生成树不同之处就在于从客户6到达客户8的路径不一样，而实际路程经过计算后是一样的，路线的总行程为175公里。
利用问题一的Floyd 算法和程序，能求得从客户2到客户1（提货点）的最短路线是12v v →，路程为50公里。
这样该回路，即最短的行车路线为：行车路线总行程为225公里。
以最小生成树法解决此问题速度快，结果较精确，但是只适合数目较少时，不适宜推广，因此本文又根据路程最短建立整数规划模型。
为了更好的防止子巡回的产生，根据哈米尔顿回路，须附加一个约束条件：当访问客户i 后必须要有一个即将访问的确切客户；访问客户j 前必须要有一个刚刚访问过的确切客户。
依次设立约束条件。
利用Lingo 求解模型部分结果（附录2）：Global optimal solution found.Objective value:Objective bound:Infeasibilities:Extended solver steps: 0Total solver iterations: 86Variable Value Reduced CostX( 1, 5)X( 2, 1)X( 3, 4)X( 4, 8)X( 5, 7)X( 6, 3)X( 7, 6)X( 8, 9)X( 9, 10)X( 10, 2)由此可得，行程路线最短的回路：总路程为225公里。
问题三模型的建立与求解用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短。
这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。
此问与问题二有相似之处都要考虑回到提货点的情形,因此本文在模型2的基础上进行改进, 重新建立相应的整数线性规划模型。
目标函数：101011min ij ij i j z c x ===⨯∑∑利用Lingo 求解模型部分结果（附录3）：Global optimal solution found.Objective value:Objective bound:Infeasibilities:Extended solver steps: 0Total solver iterations: 224Variable Value Reduced CostX( 1, 5)X( 2, 3)X( 3, 6)X( 5, 2)X( 6, 7)X( 7, 1)Global optimal solution found.Objective value:Objective bound:Infeasibilities:Extended solver steps: 0Total solver iterations: 224Variable Value Reduced CostX( 1, 4)X( 4, 8)X( 5, 1)X( 8, 9)X( 9, 10)X( 10, 5)由此可得，两辆车的行车路线及路程：第一辆车：1763251v v v v v v v →→→→→→，包含的客户有2,3,6,7，运货总量为44，路程为155公里。