最优路径的设计.doc

《最优路径的设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D

2、中选择一项填写）：D我们的参赛报名号为（如果赛区设置报名号的话）：J3502所属学校（请填写完整的全名）：西安欧亚学院参赛队员(打印并签名)：1.隋艳龙2.胡勇3.马璐指导教师或指导教师组负责人(打印并签名)：教练组日期：2011年9月2日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号最优路径设计摘要本文是对送货

3、情况求最优路径问题，题中给出送货员的最大载重量和最大载货体积的限制，在有时间和无时间的限制下，送货员要以耗时最少，所走路程最短将货物送达目的地，我们先依据位置点的X坐标和Y坐标找出各个位置点，再根据相互连通的信息，利用matlab数学软件画图连接可以连通的位置点，建立合理优化的路线。问题一，根据题中所给数据可求出30件货物重量为48.5<50公斤、体积为0.88<1立方米，故在问题一的模型建立中我们不用考虑质量、体积的约束。只需要考虑路线的问题.利用Floyd算法求出所有点从一个点出发再回到这个点的最短路径，并且路径不重复，最后总体

4、量化处理去除重复的点和重复的路径，找出最短的路径，再利用某一段路径逐一替换其中的某段路径，使得路径最短为止。结果如下：最优路径为：最短送货路径的总长为：54985米，总时间（包括交货时间）为：226.8分。问题二，送货员从早上8点上班开始送货，要将1-30号货物送达指定地点，并且时间不能超过指定的时间，这样就增加了时间上的约束，但没有要求送完货返回到出发点。所以我们必须在满足各点的时间要求前提下，寻找一条最优的路径。我们根据时间优先的原则将时间划分为四个阶段，分别为：8:00-9:00、9:00-9:30、9:30-10:15、10

5、:15-12:00，然后朝时间最早的地点方向出发，并且一个时间段最后的地点要与下个时间段第一个地点接近，这样从一个时间段的地点到另一个时间段的地点不会浪费太长时间，由于时间的划分，将送货地点也划分成了多块，这样可以采用穷举法比较出其中耗时最短的路径，前三段时间送货员都在指定时间内完成了内务，但是走完第四时间段地点后此时的时间为12:30，已超出送货所要求的时间。所以即使按最佳路径走也无法按要求完成，但为了满足时间优先原则，使货物尽早到达相应地点结果如下：最优路径为：总路程为：51928米；总时间（包括交货时间）为：216分。问题三，

6、送货员要将100件货物以最快完成路线送到指定地点，虽然没有时间的限制，但是要考虑货物的总重量和总体积，根据货物信息可以得出100件货总质量为148公斤，总体积为2.8立方米，送货员最大载重50公斤，所带货物最大体积1立方米，所以送货员最少分三次送货，半途要返回o取货，可以根据图的遍历和最小生成树把整个图分成多个路径最小的区域，根据重合的地点和邻近的路径在满足重量和体积的情况下合并，为了方便和省时，最后将多条路径合并成三条。1号线路径的最短回路为：2号线路径的最短回路为：3号线路径的最短回路为：送货员将100件货物送完的总路程和总时间

7、为：总路程为：米；总时间为：656.16分。关键词：Floyd算法穷举法最小生成树图的遍历一、问题重述在物流行业中，送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。现有一快递公司，一送货员要按图1中的路径需将货物送至城市内多处，要求设计送货方案，使所用时间最少。并且送货员只能沿图中那些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。每件货物交接花费3分钟，同一地点有多件货物按照每件3分钟交

8、接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超