资源预览内容
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
第9页 / 共22页
第10页 / 共22页
亲,该文档总共22页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
承诺书我们仔细阅读了浙江中医药大学数学建模竞赛的规则。我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网 上咨询等)与本队以外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的 资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规 则的行为,我们愿意承担由此引起的一切后果。我们授权浙江中医药大学数学建模协会,可将我们的论文以任何形式进行公开展示 (包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。我们参赛选择的题号为(从A/B/C中选择一项填写): C我们的参赛队名为: 建模走天下参赛组别(研究生或本科或专科): 本科所属学院(请填写完整的全名)第二临床医学院药学院 信息技术学院参赛队员(打印并签名):1.马程程2. 林飞3. 王莉莉张朝政日期:2013 年 8 月 1 日获奖证书邮寄地址: 邮政编码编号专用页竞赛评阅编号(由竞赛评委会评阅前进行编号):裁剪线 裁剪线 裁剪线竞赛评阅编号(由竞赛评委会评阅前进行编号):参赛队伍的队名:(请各参赛队提前填写好):物资的配送问题物流是当今一门新兴的学科,配送又是现代物流的重要内容。合理安排物资配送 的路线,对于降低运输成本、提高运输效率具有很高的现实意义。本文则主要研究物资 配送的最优路线,并且建立相关模型,根据实际问题给出一个合理的配送路线。对于问题(1),题中并没有给出相应的数据,所以在不考虑费用损失还有时间问 题的情况下,即就是只考虑送货车辆每天的总运行里程,要求得出最短路径,因此我们 建立了物资配送分区模型,首先确定区位,然后再确定巡回路径。在建立的配送分区模 型中,我们采用的是四叉树算法的思想,对候选分区进行确定,优化得到结果分区;在 建立的运输路线模型中,我们采用的是经典的旅行商问题的算法,通过枚举法找出一条 路径最短的送货路线。对于问题(2),就实际问题求出一个合理的优化路线,考虑到配送方案要合理,即 就是要求送货车辆必须在一定的时间范围内到达客户处,早到达将产生等待损失,迟到 达将予以一定的惩罚,所以在保证方案合理的情况下,进行优化,从而确定出最佳的车 辆派送方案。在问题(1)建立的模型的基础上,我们确定将客户分为3个分区,利用穷 举法列出了 26组分区并结合旅行商问题中的贪心算法,根据C+软件确定了符合路径最 短的一个分区,即最短路径为885千米,即1、2、3号客户为一个分区,4、6号客户为 一个分区,5、6、7号客户为另一个分区,但是没有考虑到时间问题,因此再根据时间 的要求进行巡回路线的确定,得出最优的送货路线,即分区一:0-3-1-2-0分区二:0-8-5-7-0分区三:0-6-4-0最短路径为910千米。最后,我们对于建立的模型,进行了优缺点的分析和评价。关键词:物资配送分区模型 四叉树算法旅行商问题的算法C+软件1. 问题重述某物流中心拥有一支货运车队,为若十个客户配送物资,物流中心与客户以及客户 与客户之间的公路里程(千米)为已知。每天,各客户所需物资的重量(吨)均已知,并且 每个客户所需物资的重量都小于一台货运车辆的载重量,所有送货车辆都从物流中心出 发,最后回到物流中心。一个合理的配送方案则要求送货车辆必须在一定的时间范围内 到达客户处,早到达将产生等待损失,迟到达将予以一定的惩罚,而一个较好的配送方 案应该使配送费用最小或总运行里程最短。于是物流中心希望:(1)建立送货车辆每天总运行里程最短的一般数学模型,并给出求解方法。 对于载重量为Q=8吨,平均速度为50千米/小时的送货车辆从物流中心(i=0)出发, 为编号是i =1,2,的8个客户配送物资。某日,第i个客户所需物资的重量为q(q. Q ) 吨,在第i个客户处卸货时间为s.小时,第i个客户要求送货车辆到达的时间范围,b 由表1给出。物流中心与各客户以及各客户间的公路里程(单位:千米)由表2给出。问当 日如何安排送货车辆(包括出动车辆的台数以及每一台车辆的具体行驶路径)才能使总运 行里程最短。2. 模型假设1. 每个客户的站点仅允许一辆车经过一次并配送货物;2. 每个客户只能被一辆送货车服务且只被服务一次;3. 保证送货车辆的路况一直正常,无突发情况的发生;4. 每辆送货车送货时行驶的路程不超过它所能行驶的最远路程;5. 每辆送货车必须在原有道路上行驶。3. 符号说明ai第,分区中,足E离货物供给点最近需求点,其值为1,否则为0bij节点了属于i分区,其值为1,否则为0l ij节点了到本分区距离货物供给点最近需求点的运输路程w节点了的货物需求量d i第,分区中,足E离货物供给点最近需求点到货物供给点的运输路程z运输车辆的容量H支路消去约束,即消去构成不完整支路的解G送货线路4. 问题的分析及模型的建立、求解4.1问题(1)的分析求解过程4.1.1问题(1)的分析该问题要求我们建立相关的数学模型,使得送货车辆每天总运行里程最短,并给出 模型的求解方法。而本题并没有给出相应的数据,所以在不考虑费用损失还有时间问题 的情况下,即就是只考虑送货车辆每天的总运行里程,要求其达到里程最短,因此我们 建立了物资配送分区模型,首先确定区位,然后再确定巡回路径。在建立的配送分区模 型中,我们采用的是四叉树算法的思想,对候选分区进行确定,优化得到结果分区;在 建立的运输路线模型中,我们采用的是经典的旅行商问题的算法,通过枚举法找出一条 路径最短的送货路线。4.1.2问题(1)模型的建立对于问题(1),我们建立了物流分区配送模型,可分为以下两个步骤:一:确定区位,候选区位内各需求点的需求量总和等于或接近车辆的运送能力, 再对候选区进行优化,确定结果分区。二:确定巡回路径,在不同的分区,采用旅行商问题的解决算法在各分区内确定 巡回路线,对求得解进行适度的优化。物流分区配送数学模型包括两个相对独立的部分:配送分区模型和运输路线模型。 配送分区的数学模型如下所示:min dis tan* = ad. +S bli i jij可s.t b = 1ijien-1 b w zjen-1 可b 0,若:i, j不属于E,则d=8。令V= n,并假设n 1。G的 一条送货线路是包含V中每结点的一个有向环,送货线路的路径是此线路上所有边的总 和。该问题要从所有的送货线路中求取最短路径的线路,而从初始点出发的送货线路 一共有(n -1)条,即等于除初始结点外的(n -1)个结点的排列数,因此旅行商问题是一 个排列问题。排列问题比子集合的选择问题通常要难于求解得多,这是因为n个物体有 n!种排列,只有个子集合(n! O()。通过枚举(n-1)!条送货线路,从中找出一条具有 最短路径的送货线路,其计算时间显然为。(n!)。4.2问题(2)的分析求解过程4.2.1问题(2)的分析一个物流中心,同时对八个客户进行物资的配送,且已知每个客户的需求量都不超 过送货车的最大承载量,货运车队到每个客户点都有一定的卸载停留时间,同时,每个 客户都有各自的要求车辆到达时间的范围,每辆车的最大载重量为8吨,平均速率为50 千米/小时。本题要研究的是如何安排出动车辆的台数以及每台车辆的具体行驶路径,使配送的 总运行里程最短。根据题意,我们可以得出约束条件:考虑到配送方案合理,即就是要求送货车辆必须在一定的时间范围内到达客户处, 早到达将产生等待损失,迟到达将予以一定的惩罚,所以在保证方案合理的情况下,进 行优化,从而确定出最佳的车辆派送方案。4.2.2问题(2)的求解在问题(1)建立的物流配送分区模型的基础上,根据本题给出的实际问题,在考虑到 客户需求量、点对之间的路程、送货车辆的车速和载重量已知的情况下,对如何安排出 动车辆的台数和最优的送货路线进行分析运算。一:确定区位,候选区位内各需求点的需求量总和等于或接近车辆的运送能力,对 候选区进行优化,确定结果分区。因此,分析到八个客户所需要的货物量为22吨,而每辆
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号