送货员送货最优路径VIP专享VIP免费

2012高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1送货路线设计问题摘要本文讨论了送货员的送货路线的最优路线问题，即在给定的地点，线路的条件下，结合考虑最大载重范围、最大带货体积及各个货物送货实现，确定送货员的最佳送货路线。对于问题一，我们针对30~1号货物所涉及的22个站点建立了最小生成树模型，结合Floyd算法算出的各顶点间的最短路径矩阵，画出了最佳线路，并求出了所用时间。在问题二的求解中先进行假设在问题一中找到的路线符合要求，并进行检验。接着我们采用分区域讨论以及最小生成树的方法进行寻找最佳路径，根据所得的数据进行分析，最后寻找到最佳路径，并得出路径的距离以及送货员完成任务并返回的时间。对于第三问，要将100件货物全部送到指定地点并返回，由于送货员一次送货的重量和体积有限制，所以我们考虑分区域送货。首先我们根据最小生成树将图上区域在满足条件下划分为尽可能少的区域块，在此基础上实现区域线路最短，从而实现全局最短。根据我们划分的区域，我们在每个区域里找出最短路径的回路。我们尽量用最小生成树的主干，如果遇到分支，考虑送货员要遍历区域内所有的点，同时利用Floyd模型，选择一条比较短的路径。通过我们的分析和比较，最终得出了最优路径。关键词：Floyd；最小生成树；最短路径；划分区域；送货问题2一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛。现有一快递公司，要求送货员以最快的速度及时将货物送达，且可以一人送多个地方，要求设计方案耗时最少。该地形图及图中各点的连通信息，各点的坐标，货物的相关信息，送货员的平均速度，和每件货物的交接时间都已给出。货物员最大载重50公斤，所带货物最大体积1立方米。同一地点有多件货物也按每件3分钟交接计算。现在该送货员要将100件货物送到50个地点，要求如下：1.设计最快将1~30号货物送到指定地点并返回的完成路线与方式，结果要求标出送货线路。2.若该送货员从早上8点上班开始要将1~30号货物的送达，时间不能超过指定时间，设计出最快完成路线与方式。3.若不考虑所有货物送达时间限制(包括前30件货物)，，将100件货物全部送到指定地点并返回。设计最快完成路线与方式。结果要求标出送货线路，给出送完所有快件的时间，另外，送货员可中途返回取货，不考虑中午休息时间。二、问题分析由题目已知条件可将送货问题看做是图论求解最佳路径问题。第一问要求算出将1~30号货物送到指定地点并返回的最快完成路线与方式，即最短时间。通过计算我们得出1~30号货物的总重量和总体积并没有超过送货员的最大承载量，且第一问没有货物送达的时间要求，故此问题转化为于找出一个遍历所有目的顶点并返回出发点的最短路径问题。在解决问题二的过程中，我们将30件货物按照不能超过的时间进行排序，并在图中标出相应的点，根据各个地点的位置分布，以及时间的要求，我们将这30个点进行区域划分，找到各个区域的最佳路径，最终将其连接就找到了送...