84快递.doc

2011年全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2011年全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：快递公司送货策略的数学模型摘要：本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规范的条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。首先，针对第一问提出的选择合理的送货策略的问题，以某业务员是否送货到某点建立0-1分布函数，以业务员总的运行公里数为目标函数，时间、货重等为约束条件,利用图和计算机编程知识得到了最优的解：需要5个业务员，最短路程为480km.然后，第二问在第一问的基础上引入了一些条件，主要从费用最省角度解决该问题，建立动态规划的数学模型。用动态规划的知识在一定的原则和约束条件下求得最优化结果：最少费用13830.7元。根据所建立的数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。针对问题三，结合前两种送货方案，最后，进行重新组合得到每个业务员的工作时间增加为8小时的业务员人数和费用的优化送货方案，经计算，可将业务员减少到4人。关键词：最优化图模型多目标动态规划TSP模型计算机1.问题重述：快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。这个问题可以描述为:一中心仓库(或配送调度中心)拥有最大负重为25kg的业务员m人,负责对30个客户进行货物分送工作,客户i的快件量为已知,求满足需求的路程最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:表一为题中所给的数据:表一最大载重量25kg重载时速20km/h途中的平均速度25km/h重载酬金3元/km*kg业务员工作时间上限6h空载时速30km/h每个送货点停留时间10min空载酬金2元/km处于实际情况的考虑,本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意要求的结果。2.问题分析：从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg。继续上述指派，直到各点总重量超过25kg，或者送货时间大于6小时。最后业务员返回总部，记录得到的可行行程（即路线）。对另一个业务员重复上述安排，直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。得到可行解的行程安排解后退出。根据题意的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕。且184.5825kgkg，故至少需要8条路线。表二列出了题中任意两配送点间的距离。表二：任意两点间的距离矩阵因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：表三给出了客户的需求，为了完成送快递的任务，每个人在工作时间范围内，可以承担两条甚至更多的线路。表中给出了送货点序号，送货点编号，快件量T，以及送货点的直角坐标。表三序号送货点快件量T坐标（km）序号送货点快件量T坐标（km）xyxY1183216163.5216228.21517175.86183365418187.51117445.54719197.815125630820153.4199654.531121216.2225777.27922226.8210882.39623232.4279991.410224247.6151910106.514025259.6151411114.11732626102017121212.7146272712211313135.812928286.0222014143.8101229298.1251615204.671430304.228183.模型假设与符号说明3.1模型的假设（1）送货运行路线均平行于坐标轴，且在该前提下，业务员可以任意选择路线。（2）业务员送快递途中不受任何外界因素影响。（3）业务员人数不限制。（4）每个业务员的路线一旦确定，便不再更改。（5）每个业务员送快递是独立的，每人之间互不影响。（6）业务员到某送货点后必须把该送货点的快件送完。（7）业务员装配邮件的时间不计。3.2符号说明iT：i送货点的快件重量(,)iixy：序号为i的送货点的坐标W重：业务员送货总重载费用W空：业务员送货总空载费用W总：业务员送货总费用n：业务员送货的总次数m：业务员人数jm：第j个业务员送货的次数1,0ia业务员在序号为i的送货点送快件，业务员在序号为i的送货点没有送快件1,ki0kiib第条路线选择序号为的送货点是最远点，第条路线选择序号为的送货点不是最远点4.模型的建立与求解4.1问题一解答本模型考虑用多目标动态规划求解。由于问题一中只要求给出一个合理的方案，且未涉及到业务员工资问题，故只要满足条件——业务员的工作时间上限是6个小时以及每条路线的最大载重量不大于25kg即可，本模型中追加两个目标——路程最短和人员最少。可以通过以下两种方法实现：（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数。（2）每一个行程的第一个送货点是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。然后比较两组结果，通过函数拟合即可得到最优化结果。本模型中以满足需求的路程最短的人员行驶路径,且使用尽量少的人数，即n30iiik1i1min(2*b*(x+y))且minm约束条件为：①时间约束：jm30112()1()6256iiijixya②每条路线的载重量约束：301*25iiiTa方法一：每一个行程的第一个送货点是距离总部最近的未服务的送货点。Step1:找离原该点最近的点v，且该点的访问标志设为被访问，该点快递重量为m，输出该点。Step2:找点v最近的点，快递重量为1m，且125mm，当其不成立时找次远点。Step3:找到符合条件的点，且不止一个时选择快递重量最重的那个点，访问标志设为被访问，并输出该点，赋值给v，且m=m+1m；返回step2,否则返回step1.第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处快件量之和为19.5kg，仍小于25kg,还可以继续指配。在剩下的未服务送货点中，5距离4最近（其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去。这里2，7被舍去，故选择了5）总快件量之和为24kg。再继续扩充，发现就会超出“25kg”这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点。用该算法得到的各路线为：（1）013450（2）0267130（3）09812100（4）01617201415230（5）0112221190（6）027260（7）01824250（8）02928300现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。由于0-1-3-0已经先构成了一个子回路，现在要将节点4插入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比较合适:1.插入到（0，1）间，总路程=7+4+5+1+4+9=30。2.插入到（1，3）间，总路程=5+6+4+9=24。3.插入到（3，0）间，总路程=5+4+4+11=24。比较上述三种情况的增量，插入到（3，0）间和（1，3）间增量最小，考虑到下一节点插入时路程最小问题，所以应当将4插入到送货点3和总部0之间。接下来，用同样的方法，将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km，历时1.9467h。结果子回路为T=0-1-3-4-5-0.因为街道平行于坐标轴方向，所以它就是最优化路线。第二条行程中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近点6，接着是7，然后13.这样，第二条优化路线0-2-6-7-13-0就确定了。用这种方法，依次可确定以下剩余六条路线。得到总的送货路线为：（1）013450（2）0267130（3）01012890（4）01617201415230（5）0191121220（6）01824250（7）027260（8）02930280具体数据见表4：表4运输员序号所经站数最近点所用时间(小时)总载重（kg）总路程（km）141（3，2）1.94672432242（1，5）2.506724.246349（10，2）1.866422.9304616（2，16）4.600023.5905411（17，3）4.213424.9726318（11，17）3.750024.7687227（21，13）3.706722768329（25，16）4.840018.396合计3028.2699184.5506改进前和改进后的路程，时间比较如下图一：020406080100线路一线路二线路三线路四线路五线路六线路七线路八路程比较改进前改进后012345线路一线路二线路三线路四线路五线路六线路七线路八时间比较改进前改进后图一然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最终只需要六名运输员，第一条线路和第二条线路有一人完成，第三条和第七条线路由一人完成，则各运输员到达各站点时间的情况如下表5所示：表5路线站点编号到各站点时间出发时间路线站点编号到各站点时间出发时间119：129：0051910：059：0039：321110：4149：522111：08510：142211：32212：0211：5861810：079：001312：482410：312713：102510：53613：3972713：4512：233109：349：002614：07129：5882910：389：00810：203011：00910：442811：244169：439：001710：072010：291410：511511：302311：59路径为：方法二：每一个行程的第一个送货点是距离总部最远的未服务的送货点。分析方法如一：得到的路径为：（1）030292823150（2）0262780（3）024251490（4）01817201660（5）0212211100（6）0191370（7