最短路线问题论文

《最短路线问题论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

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

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

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

7、点的最短路，充分考虑车的容量和每个客户需要的货物量，最后的出最优路径。问题4：由于从第2个客户到第10个客户所需的货物量总和为86个单位，而每辆车的容量为25个单位，则至少需要4辆车，即至少要找4条最短路线。要使得所有路线行程之和最短，并保证每条路线上的客户总需求量不超过25个单位，我们用Dijkstra算法分别找出到下一客户点的最短路，充分考虑车的容量和每个客户需要的货物量。一、基本假设问题1：1：不考虑送货员走同一个客户点的情况。问题2：1：不考虑送货员走同一个客户点的情况。2：一、模型的建立与求解问题㈠：模型建立与求解问题一是由第2客户送货去第10客户

8、，这里就是最解路线问题，我们可以借用LINGO软件，