送货员送货最优路径.doc

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