最短送货路线的设计论文

《最短送货路线的设计论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、货物运送线路问题最短送货路线的设计摘要：现今社会网络越来越普及，网购已成为一种常见的消费方式,随之物流行业也渐渐兴盛。为了配合现代大众的快节奏生活要求，每个送货员需要以最快的速度及时将货物送达。而这其中要涉及到送货路径、货物的送达吋间限制等诸多因素。这就要求在已知要送的货物的相关信息的前提下，怎样设计出最短的送货路径，以达到以最快的速度及时将货物送达的冃的。在本文中利用了计算最短距离的最常用的算法…Dijstra算法来计算得。在问题的解决中，分别采取多阶段、多区域等讨论方法，在时间、重量以及体积等因素的限制下利用优化模型求得是的距离最短的路线。关键字：最短距离Dijkstra算

2、法优化图论路程吋间路线Fl录一、问题的提出31、问题1的提出3.2、问题2的提出33、问题3的提出3二、问题的分析3三、模型的说明43.1模型的假设..43.3模型介绍4四、模型的建立以及求解44」问题1的模型建立和求解44.2问题2的模型建立和求解44.3问题3的模型建立和求解4五、模型的评价11六、参考文献12七、附录12一、问题的提出网络的普及不但方便了人们的交流、对信息的更广阔的涉猎，也在经济领域掀起了一场销售和消费方式的变革。网购就是反应这种变革的表现形式Z—，同时网购的兴起又带动了物流行业的发展。物流公司面对的问题则是在这种销售商和消费者的交易中，如何更加高效的完成

3、“传递者”的使命。物流公司雇佣的送货员在接收到耍送的货物以及相关信息(重量、体积、送达地点、送达时间等)之后，要对送货路线进行规划，以期达到以最快的速度及时将货物送达到消费者手中。如何选择送货路线便成为送货员面临的最棘手的问题。因此就有以下两个问题的提出：1.若将1〜30号货物送到指定地点并返冋。设计最快完成路线与方式。给岀结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货，要将1〜30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。耍求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设

4、计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。二、问题的分析由于送货员每次所送货的地点是确定的，但乂是不止一个的，因此最快完成送货任务的要求相应的转变成了在吋间、重量以及体积等限制下的最短路径的寻找的问题。在最短路径的计算中，最常用的算法是Dijkstra算法。利用Dijkstra算法求得送货地点中任意两点之间的距离。而在时间、重量以及体积等限制下的最短路径则是利用优化模型，按照类似“筛选”的思想，来获取在限制条件下的最短路径的距离、时间以及路线等结果。三、模型的介绍3」模型假设(1).一个地点的货物全部一次性带上，不考虑以后再经过此地再带上；(2).同一地点

5、多个货物的交接也按总共三分钟计算；(3).到达地点后超过规定时间的计算屮，不考虑交接的三分钟时间；(4).不考虑休息的时间；(5).所有的距离都精确到米，而所有的时间都精确到0.0001h；(6).送货员的速度是己知的常量；3.2符号说明i,j送货点的标号W从0点回到0点的总路程T从0点回到0点的总时间w(i,j)从i点到j点的最短距离v送货员的平均速度ti从0点到i点对应的最短时间mi到达i点所能带的货物的最大重量Vi到达i点所能带的货物的最大体积M每次从0点出发送货员所能携带的货物的最大重量V每次从0点出发送货员所能携带的货物的最大体积i,j=l,2,3……50M=50kg

6、V=lm33.3模型的介绍我们利用图论中常用的Dijkstra算法，求出各个点之间的最短路径，。w(i,j)表示第i个地点到j个地点的最短距离，但若第i个地点和第j个地点是不连通的则w(i,j)为无穷大，在matlab中用inf表示(在其他的计算机软件中也可以相应找到表示方式)。在计算中，引入集合t和s。其中，s表示那些己经确定了到i地点最短路径的地点，而t为全集u和s的差集，即那些还没有确定到i地点的最短路径的地点。设s的初值为{i},t的初值为u-{i}o另外再引入一个标记数组d[n],其屮在某一步d[k]表示当前从i到k的较短路径，d[k]的初值为w(i,k)。整个的计算

7、过程如下：1、在t屮选择一个d[k]最小的地点k,将其并入s,并从t中剔除k；如果t为空集{},则转到3；2、用k点与t中的其余点分别进行比较，如果d[i]>d[k]+w[k][i],则用d[k]+w[k][i],取代原来的d[i]；重复1；3、算法结束，此时d[k]中保存的就是从i点到k点的最短路径。四、模型的建立以及求解4.1问题一由给定的表1前面的三十个货物的总重量为：S48.5kg<50kg总体积为：Sv=O.88m3