最短路线问题论文

1、最短路线问题摘要： 由于市场的竞争，现在大多公司都采取送货上门的服务方式，在这送货过程中需要考虑路径最短问题和费用最省问题等。本文根据运输公司提供的提货点到各个客户点的路程数据和对问题的分析和理解 ，利用最短路径问题进行求解，得到相关问题的模型。 针对问题一 ，根据题目提供的数据，使用LINGO软件进行编程建立模型，通过运行程序并分析求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：V V V V V .总行程共85公里。 针对问题二: 通过对问题的理解要找到走完所有的客户点再回到提货点的最佳路径，我们采用Dijkstra算法逐一找到从i第个到第j个

2、客户的最短路程(i,j=1,2,3,4,5,6,7,8,9,10)，最后得到一条理想的回路是： V V V V V V V V VV 针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，采用Dijkstra算法建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的运输方案：（两辆车总和行程280公里）车号行车路线线路长度送货客户一号车1 5 2 3 4 8 9 1135公里2、3、4、5、8二号车1 7 6 9 10 1145公里6、7、9、10针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型

3、，设计一个较好的解决方案进行求解可得到一种理想的运输方案：车号线路路线长度载货量一号车40公里20单位二号车50公里20单位三号车80公里25单位四号车70公里21单位方案总消费：645元关键字：配送问题 LINGO软件 Dijkstra算法 最短路问题 消耗最低一、 问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置。问题：运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行驶路线。问题：现在运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满1

4、0个客户所需要的全部货物吗，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行驶的尽可能短的行驶路线？对所设计的算法进行分析。问题：现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给哪几个客户陪送货物以及行驶怎样的路线使它们从提货点出发最后回到提货点所行驶的距离之和尽可能短？对所设计的算法进行分析。问题：如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第三问，并假设每出一辆车的出车费为100元，运货

5、的价格为1元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？二、 问题分析 问题1：运送员在给第二个客户卸完货后，即从此处赶到第十个客户处，路程越短越好，是一个最短路径问题，为此我们采用LINGO软件进行编程，通过程序运行的结果加以分析和验证，最后得出路径最短的行使路线。程序将在下文列出。问题2：很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，我们考虑送货员送完所有货以后再返回提货点的情况。要找到送完货的最短路径我们使用Dijkstra算法依次找出从一个客户点到下一个客户点的最短距离。再用同样的方法

6、找出回到提货点的最佳路径。问题3：用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。可根据货物需求量的大小将其分为前后两部分，并将之分别构成回路。（注：由于提货点在客户1所在的位置，故不必考虑为客户1送货的情况。）首先找出两条提货点到下一客户点的最短路，再依次使用Dijkstra算法分别找出到下一客户点的最短路，充分考虑车的容量和每个客户需要的货物量，最后的出最优路径。问题4：由于从第2个客户到第10个客户所需的货物量总和为86个单位，而每

7、辆车的容量为25个单位，则至少需要4辆车，即至少要找4条最短路线。要使得所有路线行程之和最短，并保证每条路线上的客户总需求量不超过25个单位，我们用Dijkstra算法分别找出到下一客户点的最短路，充分考虑车的容量和每个客户需要的货物量。三、 基本假设问题1：1：不考虑送货员走同一个客户点的情况。问题2：1：不考虑送货员走同一个客户点的情况。2：四、 模型的建立与求解问题：模型建立与求解 问题一是由第2客户送货去第10客户，这里就是最解路线问题，我们可以借用LINGO软件，进行最优路线选择。运行程序： SETS:CITIES /1.10/:F;ROADS(CITIES,CITIES)/1,4

8、1,2 1,5 1,7 1,92,3 2,5 2,6 2,83,4 3,6 3,7 3,8 3,104,5 4,6 4,7 4,8 4,9 4,105,6 5,7 5,8 5,106,7 6,8 6,97,8 7,9 7,108,99,10/:D;ENDSETSDATA:D=40 50 25 30 5030 35 50 6015 30 50 25 60 45 30 55 20 40 6560 10 30 55 25 55 35 30 45 6010 20;ENDDATAF(SIZE(CITIES)=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS

9、(i,j):D(i,j)+F(j);END 运行结果： 0 Variable Value F( 1) 70.00000 F( 2) 85.00000 F( 3) 55.00000 F( 4) 50.00000 F( 5) 55.00000 F( 6) 55.00000 F( 7) 60.00000 F( 8) 30.00000 F( 9) 20.00000 F( 10) 0.000000 D( 1, 4) 40.00000 D( 1, 2) 50.00000 D( 1, 5) 25.00000 D( 1, 7) 30.00000 D( 1, 9) 50.00000 D( 2, 3) 30.00

10、000 D( 2, 5) 35.00000 D( 2, 6) 50.00000 D( 2, 8) 60.00000 D( 3, 4) 15.00000 D( 3, 6) 30.00000 D( 3, 7) 50.00000 D( 3, 8) 25.00000 D( 3, 10) 60.00000 D( 4, 5) 45.00000 D( 4, 6) 30.00000 D( 4, 7) 55.00000 D( 4, 8) 20.00000 D( 4, 9) 40.00000 D( 4, 10) 65.00000 D( 5, 6) 60.00000 D( 5, 7) 10.00000 D( 5,

11、8) 30.00000 D( 5, 10) 55.00000 D( 6, 7) 25.00000 D( 6, 8) 55.00000 D( 6, 9) 35.00000 D( 7, 8) 30.00000 D( 7, 9) 45.00000 D( 7, 10) 60.00000 D( 8, 9) 10.00000 D( 9, 10) 20.00000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10

12、0.000000所以又程序结果可以的出由2到10的最短距离为：V问题：模型建立与求解、首先与1有直接相连的线路点有2、4、5、7、9 S= V , =V,V,V,V,V L(V) =0 L(V)=L(V)+W=50用同样的方法可有： S= V，V , =V,V,V,V L(V)=L(V)+W=40 S= V，V , V , = V ,V,V L(V)=L(V)+W=25 S= V，V , V, V , = V,V L(V)=L(V)+W=30 S= V，V , V, V , V , = V L(V)=L(V)+W=50由上面运算可以看出，最短路线为1到5.、与5由直接相连的点有1,2,4,6,

13、7,8,10 S= V , = V，V，V ，V, V，V L(V) =0 L(V)=L(V)+W=15 S= V ，V , = V，V ，V, V，V L(V)=L(V)+W=45依此方法，类推有：L(V)=60 L(V)=10 L(V)=30 L(V)=55 所以由运算结果可知，最短路线为：5到7.、与7直接由连线的点有3、5、6、8、9、10 S= V , = V，V ，V, V，V L(V) =0 L(V)=L(V)+W=50 S= V ，V , = V ， V，V ，V L(V)=L(V)+W=25依此方法，类推有：L(V)=30 L(V)=45 L(V)=60所以由运算结果可知，最

14、短路线为：7到6.、与6有直接相连的线路点有3,4，8,9 S= V , = V，V ，V, V L(V) =0 L(V)=L(V)+W=30 S= V ，V , = V ， V，V L(V)=L(V)+W=30依此方法，类推有：L(V)=30 L(V)=55 L(V)=35所以由运算结果可知，最短路线为：6到3.、与3有直接相连的路线点有2、4、8、10 S= V , = V， V， V,V L(V) =0 L(V)=L(V)+W=30 S= V ，V , = V ， V，V L(V)=L(V)+W=15依此方法，类推有：L(V)=20 L(V)=60所以由运算结果可知，最短路线为：3到4.

15、、与4直接相连的路线点有8、9、10 S= V , = V, V，V L(V) =0 L(V)=L(V)+W=20 S= V ，V , = V ，V L(V)=L(V)+W=40依此方法，类推有： L(V)=65所以由运算结果可知，最短路线为：4到8.、与8有直接连接的线路点有 2,9 S= V , = V ， V L(V) =0 L(V)=L(V)+W=60 S= V ，V , = V L(V)=L(V)+W=10所以由运算结果可知，最短路线为：8到9.、与9直接相连的就是10 L(V)=20 ，与9相连的最短距离就是客户10.与10直接相连的就是2 L(V)=20与2直接相连的就是1 L(

16、V)=50 结论：所以，货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的方便的行使路线为：1 5 7 6 3 4 8 9 10 2 1行使的总路程为225公里问题：模型建立与求解公司派出两辆容量为50个单位的小货车配送货物，则需找出两条最短路线。首先找第1个客户到第j个客户的最短路线，最短路线为1 5，其次是1 7，即为两车出发路线。第一辆车的路线：现在找第5个客户到第j个客户的最短路线，此时与5直接相连且和第二辆车的路线中的节点不重复的有2，4，6，8，10，于是有：S=V，=V，V，V，V，VL(V)=0L(V)= L(V)+W=15S= V，V，= V，V，V，VL

17、(V)= L(V)+W=45依此类推，L(V)=60， L(V)=30， L(V)=55，则最短路线为5 2，此时车的载货量为7+13=20个单位。第2个客户到第j个客户的最短路线，此时与2直接相连且与以上路线中的节点不重复的有3，6，8，于是有： S=V，=V，V，VL(V)=0L(V)= L(V)+W=30S=V，V，= VL(V)= L(V)+W=50依此类推，L(V)=60，则最短路线为2 3，此时车的载货量为20+6=26个单位。第3个客户到第j个客户的最短路线，此时与3直接相连且与以上路线中的节点不重复的有4，6，8，10，于是有： S=V，=V，V，V，VL(V)=0L(V)=

18、L(V)+W=15S=V，V，= V，V，VL(V)= L(V)+W=15 依此类推，有L(V)=25， L(V)=60，则最短路线为3 4，此时车的载货量为26+9=35个单位。第4个客户到第j个客户的最短路线，此时与4直接相连且与以上路线中的节点不重复的有6，8，9，10，于是有： S=V，=V，V，V，VL(V)=0L(V)= L(V)+W=30 S=V，V，= V，V，VL(V)= L(V)+W=20依此类推，L(V)=40，L(V)=65，则最短路线为4 8，此时车的载货量为35+5=40个单位。此车最多能加10个单位的货物，满足此条件的有第7、10个客户。现在考虑与第二辆车所走路线

19、中的节点不重复，而第8个与第10个客户之间无直接的路线到达，所以此车只为2、3、4、5、8这几个客户送货。现在找地8个客户到提货点的最短路线，第8个客户没有直接到达地1个客户的路线，而与第8个客户直接相连的有2，3，4，5，6，7，9，于是有: S=V，=V，V，V，V，V，V，VL(V)=0L(V)= L(V)+W=60S= V，V，= V，V，V，V，V，VL(V)= L(V)+W=25依此类推，L(V)=20， L(V)=30， L(V)=55， L(V)=30， L(V)=10 ，则最短路线为8 9，而第9个客户有直接到第1个客户的路线，且路线长度是最小的。所以第一辆车的路线为1 5

20、2 3 4 8 9 1第二辆车的路线：此车应先从1到7，此时车的载货量为10个单位。现在找第7个客户到第j个客户的最短路线，此时与7直接相连且与第一辆车的送货点不重复的有6，9，10，于是有： S=V，=V，V，VL(V)=0L(V)= L(V)+W=25S= V，V，= V，VL(V)= L(V)+W=45 依此类推，L(V)=60，则最短路线为7 6，此时车的载货量为10+15=25个单位。现在只有第9、10个客户的货没有送，而第8个客户到第10个客户没有直接路线到达，且不考虑重复走，所以此时第二辆车的路线已确定，路线为：1 7 6 9 10 1由以上方案得出，运输公司派出的两辆车的行驶路

21、线、路线长度及每条路线上的货物量总需求量如下表：车号行驶路线路线长度货物需求量该车负责的客户一号车1 5 2 3 4 8 9 1135402，3，4，5，8二号车1 7 6 9 10 1145466，7，9，1，0辆车行驶全程总和为280公里。问题：模型建立与求解由于第2到第10个客户所需货物量总和为86个单位，而每辆车的容量为25个单位，则至少需要4辆车。、第一辆车的路线：首先找第1个客户到第j个客户的最短路；与1直接相连的客户j有2，4，5，7，9于是有： S= V , =V,V,V,V,V L(V) =0 L(V)=L(V)+W=50 用同样的方法可有： S= V，V , =V,V,V,

22、V L(V)=L(V)+W=40 S= V，V , V , = V ,V,V L(V)=L(V)+W=25 S= V，V , V, V , = V,V L(V)=L(V)+W=30 S= V，V , V, V , V , = V L(V)=L(V)+W=50则，从第1个客户到第j个客户的路线距离从近到远的排序为1 到5，1到 7，到4,1到9,1到2最短路为1 5，此时车的载重量为第5个客户所需要货物量7个单位；接下来找第5个客户到第j（j=2，3，4，6，7，8，9，10）个客户的最短路，此时与5直接相连的j客户有2,4,6,7,8,10； S= V , = V，V，V ，V, V，V L(

23、V) =0 L(V)=L(V)+W=15 S= V ，V , = V，V ，V, V，V L(V)=L(V)+W=45结论：用同样的方法，我们可以依此类推得到L(V)=60 L(V)=30 L(V)=55;则最短路线为5 2，此时车的载货量为第5个客户与第2个客户所需要货物量的总和20；这时，此车最多能再装5个单位的货物，所需要货物量为5的只有第8个客户，但是第2个客户到第8 个客户的距离为60公里，显然这不是最短的路线，所以此车只为第2、5个客户送货，路线为1 5 2.、第二辆车的路线：由知：第二辆车应先从1到7，此时车的载货量为10个单位。现在找与第7个客户到第j个客户的最短路线，与7相连

24、的最短路线的点有1、3、6、8、10.于是有： S= V , = V ，V ， V ， V，V L(V) =0 L(V)=L(V)+W=30 S= V ，V , = V，V ， V，V L(V)=L(V)+W=50依此方法，类推有： L(V)=25 L(V)=30 L(V)=60 则最短路线为 7 6，此时车的载货量为25个单位，已经是达到了最大载重量，所以此车路线为: 1 7 6 、第三辆车的路线：由知，第三辆车应先从1到4，此时车的载货量为9个单位，现在找第4个客户到第j个客户的最短路线，此时与4直接相连的点有3、8、9、10.于是有： S= V , = V ， V ，V ，V L(V)

25、=0 L(V)=L(V)+W=15 S= V ，V , = V ，V ，V L(V)=L(V)+W=20依此方法，类推有： L(V)=40 L(V)=65 则最短路线为4 3，此时车的载货量为15个单位，再找第3个客户到第j个客户的最短路线，此时与3直接相连的有8、10于是有： S= V , = V ， V L(V) =0 L(V)=L(V)+W=25 S= V ，V , = V L(V)=L(V)+W=60则最短路线为3 8，此时车的载货量为20个单位，此车不能再加货，所以此车只为了第3、4、8个客户送货，路线为：1 4 3 8、第四辆车的路线：由和知，此车应先从1到9，此时车的载重量为12

26、个单位，再由、知道，只有第10个客户没有车送货，则第四辆车就会有最后的送货线路，及：1 9 10 此时车的载重量为21个单位。结论：由、辆车就可以将获送完，而且线路最短，花销最少。路线长度及每条路线上的货物总需求如下表：车号行车路线路线长度货物需求量一号车1 5 2. 40 20二号车1 7 6 55 20三号车1 4 3 8 80 25四号车1 9 10 70 21显然每条发车路线上货物载重量没有超过25个单位，故方案可行，公司运货的总费用为： Z=（40+55+80+70）*1+4*100=645 （元）五、模型评价从我们建立的模型来看，无论是理论上或者是和现实的接近性上，都是比较合理的，

27、我们主要从模型的假设合理性、建模的创造性、运算的效率和结果的正确性对其做出客观的评价：1，我们的假设均考虑客观性合乎情理，模型(1)与模型(2)在现实中也可以广泛的应用，与现实状况紧密相连；例如：最优路径问题，在现实生活已经应运范围很广了。2.对模型（1）我们使用的LINGO软件较为简单，便于使用，容易懂，是问题简单化，准确性较高。3.我们使用的Dijkstra算法能得出路径的最优方案，但步骤较为复杂，要计算的节点多，计算效率较低。4.就是模型求解的效率性了，由于本题目的数据量不大，我们的程序运行均能瞬间完成。5.就是结果的正确性了，通过模型的求解，我们得到与现实很接近的结果，可以说是合理、正

28、确的。六、 模型推广 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路问题在实际生活中有广泛的运用，如在运输网络结构的分析，交通运输线路的选择，通讯线路的建造与维护，运输货量的最小成本分析等都有直接的应用价值。七、 参考文献八、 附录 程序1：SETS:CITIES /1.10/:F;ROADS(CITIES,CITIES)/1,4 1,2 1,5 1,7 1,92,3 2,5 2,6 2,83,4 3,6 3,7 3,8 3,104,5 4,6 4,7 4,8 4,9 4,105,6 5,7 5,8 5,106,7 6,8 6,97,8 7,9 7,108,99,10/:D;ENDSETSDATA:D=40 50 25 30 5030 35 50 6015 30 50 25 60 45 30 55 20 40 6560 10 30 55 25 55 35 30 45 6010 20;ENDDATAF(SIZE(CITIES)=0;FO