




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数学建模论文 题目:快递公司的运送策略 学校:中原工学院信息商务学院组成员:邝光辉、魏胜伦、唐锦锦2012年8月29日 快递公司送货策略摘要.本论文是关于快递公司送货策略的优化问题,就是在给定送货地点和给定送货量和送货时间的约束条件下,确定所需业务员人数,每个业务员的运行线路,总的运行公里数,以及费用最少的策略。本文主要从最短路径和费用最省两个角度来考虑问题,建立三个数学模型。 模型一:本题主要运用的的最优化线性规划中的0-1整数规划建立约束条件,将送货点抽象为一个点,且任意两点间的距离为这两点横纵坐标差的绝对值之和。先从最远点开始出发,一次查找临近点,并考虑总重量小于25kg,以此来划分区域
2、,最后利用最近插入法来寻求最优解,假设每条线路由不同的业务员来完成。模型二:运用的是图论中最小生成树的原理,在满足约束条件的前提下求的最短距离。模型三:在问题一的基础上,重新建立模型求解,得到目标结果。关键词: 快递公司送货 最优化 0-1整数规划 最近插入法 最小生成树 1问题重述目前,快递行业正蓬勃发展,为我们的生活带来更多方便。一般地,所有快件到达某地后,先集中存放在总部,然后由业务员分别进行派送;对于快递公司,为了保证快件能够在指定的时间内送达目的地,必须有足够的业务员进行送货,但是,太多的业务员意味着更多的派送费用。由此我们得知,确定业务员的人数和各自行走路线是本题的主要步骤。求满足
3、需求的路程最短的人员行驶路线,且使用尽量少的人数,并满足以下条件:(1) 每天的快件必须在规定的时间9:0017:00(8小时)内全部送完。(2) 每个业务员每天平均工作时间不超过6小时,在每个送货点停留的时间为10分钟,途中速度为25km/h。(3) 每次出发业务员所携带的快件重量不超过25kg。(4) 为了计算方便,我们将快件一律用重量来衡量,平均每天收到总重量为184.5千克。(5) 下表所给的数据为每个送货点的位置和快件重量,并且公司总部位于坐标原点处(如图2),并且假设送货运行路线均为平行于坐标轴的折线。送货点快件量T (kg)坐标(km)送货点快件量T(kg)坐标(km)xyxy1
4、832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818 图2 送货点分布图(1)请你运用有关数学建模的知识,给该公司提供一个合理的送货策略(即需要多少业务员,每个业务员的运行线路,以及总的运行公里数);
5、(2)如果业务员携带快件时的速度是20km/h,获得酬金3元/kmkg;而不携带快件时的速度是30km/h,酬金2元/km,请为公司设计一个费用最省的策略;(3)如果可以延长业务员的工作时间到8小时,公司的送货策略将有何变化?2.问题的分析在问题1中:平均每天收到的总重量为184.5千克,每个人的最大负重是25千克,即184.5/25=7.38,可知需要8条路线对这些快件进行运送。利用从最远点出发依次查找符合条件限制的各个区域,求得8条行走路线,然后根据最近插入法对路线进行优化。根据优化后得出的路线求的各条路线的路程,和在速度为25km/h的条件下得出走完每条路所需的时间。有题意知:每个业务员
6、的工作时间不小于6小时,在此基础上将工作时间短的路线进行合并,进而求的在完成总的送货量且工作时间小于6小时的条件下,所需的总的业务员数。在问题2中:业务员的速度改变,分成携带快件和不携带两种情况下的具有不同的速度,分别为20km/h,30km/h,且业务员的薪酬与其工作过程中的行走的总路程有关。以费用最省建立目标函数,建立动态规划数学模型,每人工作时间不超过6小时且每次出发最多只带25千克的重量,列出目标函数和约束条件,来找出每条路线的送货点。问题3 将业务员工作时间延长至8小时,在1的基础上将时间约束条件改为8个小时,在满足条件基础下,对问题1的路线进行合并,得出公司的送货策略。3.模型的假
7、设与符号说明3.1模型的假设(1)初始模型中,假设每条路线对应不同的业务员。(2)每个业务员每天的工作时间不超过6个小时,且送完货后必须再回公司报到。(3)业务员的休息时间不包括在最大工作时间6个小时内。(4)每个业务员送快递是独立的,每人之间互不影响。(5)业务员到某送货点后必须把该送货点的快件送完。(6)假设业务员送货运行路线均为平行于坐标轴的折线。(7)无塞车现象,即业务员送快递途中不受任何外界因素影响,且业务员的休息时间不包括在最大工作时间6个小时内。3.2符号说明(1) (2) (3) :表示第j个送货点坐标(4): 第j个送货点所需快件重量。4.模型的建立与求解问题(1):本题中考
8、虑一个目标:总运行公里数最短。可以用以下方法:先假设每条线路由不同的业务员来完成,即需要8名业务员来完成运送快递;然后在人数不变的情况下,本题先从最远点开始出发,依次查找临近点,并考虑总重量小于25kg,以此来划分区域,最后利用最近插入法来寻求最优解,最后根据表中的时间的约束,对业务员人数安排进行重新调整。根据题意每个业务员工作时间不超过6小时,又因为184.5/25=7.38;即派送这些快件至少需要8个业务员。因此问题(1)只需满足两个条件即可:1. 业务员工作时间不超过6小时;2. 每条线路上最大载重不超过25kg由于快递员从公司出发最多只能载25kg,因此: (1)在每一条线路上,每一个
9、送货点只能选择一次,因此: (2)在每条线路上只有一个最远点,即: (3)一条线路上至少有一个货点, (4)业务员在每个货点停留10min,而业务员每天工作不超过6小时,因此: (6)因此,此模型满足路程最短目标函数,建立如下模型:约束条件为:因为30这个点距原点最远,因此假设先从30出发,29是距离30最近的送货点,而且两点的快件重量和为12.3kg小于每个人的最大负重,可以继续指配。接着28是距离29最近的点,此时三点的快件重量和为18.3kg仍小于25还可以继续指配,剩余送货点中23距离28最近(其实距离28最近的点有23,24,26,27四个点,但是结合快递重量,将其从小到大依次排列,
10、快递重量大者先选,但需满足总重量要求,综合考虑选择23),同理确定下一个点选择15,再继续扩充,会超出最大限载重,故返回原点,该路线总送货重量为24.1,所以第一条路线为。用该算法得到的所有路线为: 现在这五个送货点之间的最优访问路径的是一个典型单回路问题。可以根据单回路运输模型TSP求解。一般而言,用比较法求解TSP模型求解有最邻近法和最近插入法两种。由最近插入法比最近邻点法得到的结果更好,由于已经构成一个子回路,但现在要将28插入,但是28送货点有3个位子可以插入:1、插入到0和30之间2、插入到30和29之间3、插入到29和0之间。分析比较,得出插入到0和30之间,增量最小。同理将23和
11、15用最近插入法,可以得出最优化路线为。用这种方法可以依次对剩下的七条路线进行优化,进而得出所有的优化送货路: 每个业务员所工作的具体情况如下表所示:业务员编号过站数所用时间(小时)总路程(千米)总载重量(千克)154.8310024.1233.547624.3343.396822.4453.155824.4542.835423.6632.665420.8732.184224.2831.632820.7合计3024.21480184.5根据上述表格中的时间,可以读出每个业务员每天工作不超过6小时的最佳匹配方案,又考虑每个业务员所经过工作站之间的距离,即:1) 业务员3和业务员8的工作可以合并为
12、一个人来做;2) 业务员4和业务员7的工作可以合并为一个人来做。3) 业务员5和业务员6的工作可以合并为一个人来做。由此得出每位快递员的送货路线为: 现列表如下:业务员编号过站数所用时间(小时)总载重量(千克)总路程(千米)154.8324.1100233.5424.37634+33.39+1.6322.4+20.768+2845+33.15+2.1824.4+24.258+4254+32.83+2.6623.6+20.854+54合计3024.211845480下图为各条路线优化前与优化后所用时间比较下图为各条路线优化前与优化后经过路程比较运行路线如下:路线进行合并后每个人的行走路线:问题(
13、2):问题二中由于业务员所得的费用是最主要的,业务员安排、路线选择都是为了总费用的最小化提供条件,所以应首先考虑路费,之后再考虑业务员的安排。为了使总能够费用最少,总的思路是先送货给离快递公司最近且快件最重的送货点,以此类推,在保证时间、载重量有限的前提下,沿途把快递送完,最终让业务员最远点空载返回。根据这一思路,全部路线业务员的重载费用可表示为:某路线业务员经过的路径选择应遵循以下原则:(1)近者优先原则。某业务员最近起始送货点的选择直接关系到费用的多少,所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完,不让下一条路线再把较近点作为起始送货站。(2)少走重复路原则。由于在路途相等的条
14、件下,重载费用要比空载费用大得多,因此,尽量让业务员空载行走。(3)坐标贴近原则。在同一条路线中,离原点较近送货点的坐标仅次于较远点的坐标。(4)路线较少原则。路线多,一方面,相对最远点的选择多,跑的空路多,费用就多;另一方面,过分地强调短暂效益,出动路线多,会引起业务员的反感,不利于以后的人员控制。根据上述分析及基本假设,业务员送货的费用可以表示如下:重载费用:空载费用: 根据题意可知,业务员在第i条线路运送与不运送货物,所需时间:所以总约束条件为:(1) 时间约束: (2) 载重量约束: (3) 路线约束:; 问题二选货物点的方法类似于问题一,例如:第一条行程中访问了节点0-1-3-4-5
15、-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就为第一条路线所含有的送货点。并且因为每个点周围的临近点中,之间距
16、离最短,其所需路费就越少。根据路线约束条件(3)以及坐标知:送货点1、2首先必须作为某路线的最近起始送货点,再结合时间约束条件、载重量约束条件:每次出发不能超过25kg以及上述分析的有关内容,依次选出各路线的次近点,并做统筹兼顾,一直到满足约束条件的最大值为止。 因此得出八个业务员的行进路线: 由此我们得知各业务员的具体路线和所得费用现列表如下:业务员编号过站总数所用时间(小时)总载重(千克)总费用(元)142.0324767.5242.7324.21390.6342.5722.91357.5443.1017.71438.4555.2022.92680.6633.33252310.2734.1
17、723.52620834.3024.32891.9合计3027.46184.515456.7由上表可知:(1) 第一条路线和第六条路线可以由一名业务员来完成;(2) 第二条路线和第三条路线可以由一名业务员来完成,所以总共需要6名业务员。即最后确定行走路线为: 在以上方案中,本问题得到的总费用最小值为15456.7元。每条路线行走的过程如下:问题(3):由于问题将业务员的工作时间延长到8个小时,又因为业务员的工作时间加上休息时间总和不能超过8个小时,所以只需在问题一所建模型与假设的基础上,只需对问题中对时间的约束进行改变即可。、因此,此模型满足路程最短目标函数,建立如下模型:约束条件为: 根据题
18、意可知,问题三和问题一的目标函数一样,约束条件只是增加其中工作时间为8小时,不优先考虑费用,即:此问题所建立模型所得行进路线与问题一的行进路线一样,即:每个业务员所工作的具体情况如下表所示:业务员编号过站数所用时间(小时)总路程(千米)总载重量(千克)154.8310024.1233.547624.3343.396822.4453.155824.4542.835423.6632.665420.8732.184224.2831.632820.7合计3024.21480184.5因为工作时间增为8小时,所以用类似于问题一的方法可进一步优化,但考虑到每个业务员工作时间尽量相差不大,即安排如下:1) 第一个业务员和第八个业务员可以有一个人来完成;2) 第二名业务员和第七名业务员可以有一个人来完成;3) 第三名业务员和第六名业务员可以有一个人来完成;4
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 花儿生肖测试题及答案
- 涪陵教师面试题及答案
- 普通遗传学 试题及答案
- 数学在生活中的应用试题及答案
- 施工工艺与安全管理关联试题及答案
- 供应链风险管理体系在资源优化配置领域的应用与案例分析报告
- 英语商业演示技巧与表达能力试题及答案
- 河南特岗招聘试题及答案
- 老年教育课程设置与教学模式创新:2025年发展趋势报告
- 家具设计中的用户参与设计考题及答案
- 机动车维修竣工出厂合格证样式
- 幼儿园中班歌唱:《母鸡孵蛋》 课件
- GB/T 36447-2018多媒体教学环境设计要求
- GB/T 14832-2008标准弹性体材料与液压液体的相容性试验
- 电机检测报告
- 内镜下逆行阑尾炎治疗术
- SJG 82-2020 政府投资学校建筑室内装修材料空气污染控制标准-高清现行
- 《脂蛋白(a)与心血管疾病风险关系及临床管理的专家科学建议》(2021)要点汇总
- 2004年武汉房地产市场情况分析报告(共23页)
- 肿瘤化学治疗
- RMG88.62C2控制器报警显示及可能的故障原因 - 副本
评论
0/150
提交评论