2014赛题解析

1、A 物资的配送（2人完成）某物流中心拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该物流中心用这样的车为若干个客户配送物资，物流中心与客户以及 客户与客户之间的公路里程（千米）为已知。每天，各客户所需物资的重量（吨）均已 知，并且每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物 流中心出发，最后回到物流中心。物流中心每天的配送方案应当包括：当天出动多少台 车？行驶路径如何？由此形成的当天总运行里程是多少？ 一个合格的配送方案要求送 货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一 定的惩罚；而一个好的配送方案还应该

2、给出使配送费用最小或总运行里程最短的车辆调 度方案。该物流中心希望:1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2. 具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。算例载重量为Q=8吨、平均速度为v=50千米/小时的送货车辆从物流中心（i=0） 出发，为编号是i=1,2,8的8个客户配送物资。某日，第i个客户所需物资的重量 为吨qi （qvQ），在第i个客户处卸货时间为si小时，第i个客户要求送货车辆到达 的时间范围ai,bi由表1给出。物流中心与各客户以及各客户间的公路里程（单位：千 米）由表2给出。问当日如何安排送货车辆（包括出动车辆

3、的台数以及每一台车辆的具 体行驶路径）才能使总运行里程最短。表1物资配送任务及其要求客户i12345678qi （吨）21.54.531.542.53Si （小时）121322.530.8ai,bi1,44, 61,24, 73, 5.52, 55, 81.5, 4表2点对之间的公路里程（千米）01234567800406075902001001608014006540100507511010026065075100100757575375407501005090901504901001001000100757510052005010050100070907561007575907570070

4、10071601107590759070010088010075150100751001000路程所用时间012345678000.81.21.51.8423.21.610.801.30.8211.52.2221.21.301.5221.51.51.531.50.81.50211.81.8341.8222021.51.5254121201.41.81.5621.51.51.81.51.401.4273.22.21.51.81.51.81.40281.621.5321.5220物资的配送问题物流是当今一门新兴的学科，配送又是现代物流的重要内容。合理安排物资配送 的路线，对于降低运输成本、提高运输

5、效率具有很高的现实意义。本文则主要研究物资 配送的最优路线，并且建立相关模型，根据实际问题给出一个合理的配送路线。对于问题（1 ），题中并没有给出相应的数据，所以在不考虑费用损失还有时间问题的情况下，即就是只考虑送货车辆每天的总运行里程，要求得出最短路径，因此我们 建立了物资配送分区模型，首先确定区位，然后再确定巡回路径。在建立的配送分区模 型中，我们采用的是四叉树算法的思想，对候选分区进行确定，优化得到结果分区；在 建立的运输路线模型中，我们采用的是经典的旅行商问题的算法，通过枚举法找出一条 路径最短的送货路线。对于问题（2），就实际问题求出一个合理的优化路线，考虑到配送方案要合理，即 就是

6、要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到 达将予以一定的惩罚，所以在保证方案合理的情况下，进行优化，从而确定出最佳的车辆派送方案。在问题（1）建立的模型的基础上，我们确定将客户分为 3个分区，利用穷举法列出了 26组分区并结合旅行商问题中的贪心算法，根据C+软件确定了符合路径最 短的一个分区，即最短路径为885千米，即1、2、3号客户为一个分区，4、6号客户为 一个分区，5、6、7号客户为另一个分区，但是没有考虑到时间问题，因此再根据时间 的要求进行巡回路线的确定，得出最优的送货路线，即0-3-1-2-00-8-5-7-00-6-4-0分区一分区分区最短路径为9

7、10千米。最后，我们对于建立的模型，进行了优缺点的分析和评价。关键词：物资配送分区模型四叉树算法旅行商问题的算法 C+软件1. 问题重述某物流中心拥有一支货运车队，为若干个客户配送物资，物流中心与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物资的重量 （吨）均已知，并且 每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物流中心出发，最后回到物流中心。一个合理的配送方案则要求送货车辆必须在一定的时间范围内 到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚，而一个较好的配送方 案应该使配送费用最小或总运行里程最短。于是物流中心希望：（1 ）建立送货车辆

8、每天总运行里程最短的一般数学模型，并给出求解方法。（2）对于载重量为Q=8吨，平均速度为50千米/小时的送货车辆从物流中心（i=0）出发， 为编号是i=1,2,8的 8个客户配送物资。某日，第i个客户所需物资的重量为qi（qi<Q）吨，在第i个客户处卸货时间为s小时，第i个客户要求送货车辆到达的时间范围bi'bi由表1给出。物流中心与各客户以及各客户间的公路里程 仲位:千米)由表2给出。问当 日如何安排送货车辆(包括出动车辆的台数以及每一台车辆的具体行驶路径 )才能使总运 行里程最短。2. 模型假设1. 每个客户的站点仅允许一辆车经过一次并配送货物；2. 每个客户只能被一辆送货车

9、服务且只被服务一次；3. 保证送货车辆的路况一直正常，无突发情况的发生；4. 每辆送货车送货时行驶的路程不超过它所能行驶的最远路程;5. 每辆送货车必须在原有道路上行驶。3. 符号说明ai第i分区中，距离货物供给点最近需求点，其值为1,否则为0bij节点j属于i分区，其值为1,否则为0lij节点j到本分区距离货物供给点最近需求点的运输路程wj节点j的货物需求量di第i分区中，距离货物供给点最近需求点到货物供给点的运输路程z运输车辆的容量H支路消去约束，即消去构成不完整支路的解G送货线路4. 问题的分析及模型的建立、求解4.1问题(1)的分析求解过程4.1.1问题(1)的分析该问题要求我们建立相

10、关的数学模型，使得送货车辆每天总运行里程最短，并给出 模型的求解方法。而本题并没有给出相应的数据，所以在不考虑费用损失还有时间问题 的情况下，即就是只考虑送货车辆每天的总运行里程，要求其达到里程最短，因此我们 建立了物资配送分区模型，首先确定区位，然后再确定巡回路径。在建立的配送分区模 型中，我们采用的是四叉树算法的思想，对候选分区进行确定，优化得到结果分区；在 建立的运输路线模型中，我们采用的是经典的旅行商问题的算法，通过枚举法找出一条 路径最短的送货路线。4.1.2问题模型的建立对于问题(1),我们建立了物流分区配送模型，可分为以下两个步骤：一：确定区位，候选区位内各需求点的需求量总和等于

11、或接近车辆的运送能力， 再对候选区进行优化，确定结果分区。二：确定巡回路径，在不同的分区，采用旅行商问题的解决算法在各分区内确定 巡回路线，对求得解进行适度的优化。配送分区模型和运输路线模型。物流分区配送数学模型包括两个相对独立的部分： 配送分区的数学模型如下所示：mindistance=2 ad+£ 送 bjhjii js.tZ bjWj <zjCT Jbij <aiai =0,1bij =0,1式中，(1)为目标函数，使得运输路程最小化；(2)表示每一需求点都被选中；(3)表示每一分区的总货物需求量限制，均小于等于运输容量；(4)表示分区i与节点j关系；(6)限制a、

12、b的取值。运输巡回线路的数学模型采用经典的旅行商问题 (TS P)数学模型，如下所示:m i ndis t ace Z dijx i ji js.tn送 Xij =1,j =0,1 ni =0 nZ Xjj =1,i =0,1 nj=0X =(Xj F HXj =0,1其中，Xij =0若弧fj在在线路上dij =J（Xj -为）+（yj -yi）4.1.3问题模型的求解配送分区模型的求解：四叉树思想，可以很好地在图像处理、空间数据结构的描述等方面得到了广泛的 运用，较好地描述地理目标的空间位置和空间关系，具有良好的数据结构和地理目标快 速检索等特点。而且物流配送作为空间点线关系的处理，采用四

13、叉树方法进行处理有简 洁快速的技术优势。对于四叉树网格关系的描述，本文引用了方向度的概念。通常四叉树与相邻 网格连接，即有8个方向度，如果邻近网格没有需求点，则该四叉树周围无四叉树网格 连接，即该网格的方向度为0,形成了孤岛。通过建立四叉树方向度的概念，陪面了配 送分区孤岛现象的发生。根据上述思想，本文提出的物流配送分区模型采用四叉树思想的算法进行实现， 实现方法如下所示：四叉树的生成。以四叉树中网格包含的需求点货物总需求量小于等于车辆载重量 为基准进行四叉树的生成，当四叉树网格包含的需求点货物总需求量小于等于车辆载重 量时，停止该四叉树网格的划分，则该四叉树网格为一个候选配送分区，剔除不包含

14、需 求点的四叉树网格。确定候选区间。选择距离供给点最远端的四叉树网格，延逆时针方向进行网格中 需求点的扩充。如果与之临近网格中有方向度小于 3的网格，则以临近网格中最小方向 度的网格为中心进行补充，原网格作为次选网格。扩充的条件是：如果本网格的货物总 需求量等于车辆载重量，则不进行扩充；如果本网格的货物总需求量小于车辆载重量， 则延逆时针方向以最近原则选择相邻一定等级的网格内的需求点（实际上，应当根据物 流中心的实际用户分布的聚类特征决定，为了节省计算和存储资源，考虑到物资配送需 求点基本呈均匀分布的特点，可以认为客户呈均匀离散分布。）使得配送区位的总需求量等于或者接近车辆载重量。所选择的需求

15、点从原从属网格中剔除；将无需求点的网格 剔除，形成非四叉树形式的配送区位。重复上述操作，使每个需求点仅一次被选择入一个配送区位。将以上操作确定的配送区位仍然作为候选区位，通过改进算法的方式，代入物流 分区配送数学模型中，进行目标函数求解，如果求解值小于原目标函数求解值，则该配 送区位设定为新的候选区位，循环上述操作，经过限定次计算，进行配送区位的优化。运输线路模型的求解：此问题可描述如下：设G = （V, E ）是一个具有边路程dij的有向图，dij的定义如下,对于所有的i和j，dij >0,若（ij不属于E，则dijZ。令IV = n,并假设n >1 o G的一条送货线路是包含V

16、中每结点的一个有向环，送货线路的路径是此线路上所有边的总 和。该问题要从所有的送货线路中求取最短路径的线路，而从初始点出发的送货线路 一共有（nT ）条，即等于除初始结点外的（n-1）个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有个子集合(n!>0()。通过枚举(n 1 )!条送货线路，从中找出一条具有最短路径的送货线路，其计算时间显然为0(n!)。4.2问题(2)的分析求解过程 4.2.1问题(2)的分析一个物流中心，同时对八个客户进行物资的配送，且已知每个客户的需求量都不超 过送货车的最大承载量，货运车队

17、到每个客户点都有一定的卸载停留时间，同时，每个 客户都有各自的要求车辆到达时间的范围， 每辆车的最大载重量为8吨，平均速率为50 千米/小时。本题要研究的是如何安排出动车辆的台数以及每台车辆的具体行驶路径，使配送的总运行里程最短。根据题意，我们可以得出约束条件：考虑到配送方案合理，即就是要求送货车辆必须在一定的时间范围内到达客户处， 早到达将产生等待损失，迟到达将予以一定的惩罚，所以在保证方案合理的情况下，进 行优化，从而确定出最佳的车辆派送方案。4.2.2问题(2)的求解在问题(1)建立的物流配送分区模型的基础上， 根据本题给出的实际问题，在考虑到 客户需求量、点对之间的路程、送货车辆的车速

18、和载重量已知的情况下，对如何安排出 动车辆的台数和最优的送货路线进行分析运算。一：确定区位，候选区位内各需求点的需求量总和等于或接近车辆的运送能力，对 候选区进行优化，确定结果分区。口号。因此，分析到八个客户所需要的货物量为 22吨，而每辆送货车的最大载货量为 8 吨，考虑到在各个区位内各需要量总和等于或接近车辆的运送能力，并结合上一题建立 的模型可以确定为3辆车，对应3个分区，每一辆车负责每一个分区。下表 1即为列出 来的每个分区所对应的客户序号。若分为 2个分区，则不满足货车的最大载重量要求； 若分为4个分区，则每辆车的载货量严重浪费，不符合实际情况。因此确定3辆车，对应3个分区是最为合理

19、的划分。以下表1即为穷举法所列出的每个分区所对应的客户序 号。分区一123123123123135135156分区二567457458578267247278分区三48686746486834分区一267567145124148148126分区二458248267567267567457分区三13133838352338分区一178135135148178126156分区二256248278256235578247分区三34674637463438分区一235235147126156分区二178147256458248分区三4668383737表1:每个分区所对应的客户序号二：确定巡回路径，在

20、不同的分区，采用旅行商问题的解决算法在各分区内确定巡 回路线，对求得解进行适度优化。因此我们根据C+软件，采用旅行商问题中的贪心算法，获得最优路径的贪心法应一条 边一条边地构造这棵树。根据距离这种量度来选择将要计入的下一条边。最简单的量度 标准是选择使得迄今为止计入的那些边的距离的和有最小增量的那条边。得出了路径最短的一组分区（代码见附录二），如下图1所示（1、2、3号客户为一个分区，4、6号客户 为一个分区，5、& 7号客户为另一个分区），配送中心图1:路径最短的分区根据上图我们可以得出，最短路径为885千米，但此答案是不考虑到时间问题（包 括送货时间、卸货时间、客户要求的送达时间范

21、围），不视为一个合理的配送的方案。 对此，要得出一个较好的配送方案，我们必须要对这组的分区进行时间的考虑，下表2即为点对之间的需要的行驶时间：012345678000.81.21.51.8423.21.610.801.30.8211.52.2221.21.301.5221.51.51.531.50.81.50211.81.8341.8222021.51.5254121201.41.81.5621.51.51.81.51.401.4273.22.21.51.81.51.81.40281.621.5321.5220表2:点对之间的时间（小时）从表2可以看到，首先遇到送货时间底线的是3号客户，其实是

22、1号客户，8号客 ，然后户，6号客户，5号客户，2号客户，4号客户，7号客户，即3-1-8-6-5-2-4-7再对我们得到的那组分区（1、2、3号客户为一个分区，4、6号客户为一个分区，5、&1F4Qkjn /./3匸:：75kTi'二/甕送屮心 65 km/ eOkm75km”80 km8 160km90 km75krr7号客户为另一个分区）进行验证，由此可得到最优的送货路线，如下图 2所示： 5图2:各分区的巡回路线即就是分区一：0-3-1-2-0分区二：0-8-5-7-0分区三：0-6-4-0最短路径为910千米。5. 模型的评价5.1模型的优点1. 采用四叉树方法进行处

23、理物流配送空间点线关系，具有简洁快速的技术优势。2. 采用旅行商问题的解法，解决最短路径问题很方便且快捷。3. 物流配送分区模型的思路清晰，考虑全面。5.2模型的缺点 1.实际确定分区的过程中，采用了穷举法，对于大样本容量的数据就不适合，显得繁琐、 复杂。6. 参考文献1李化，配送路线优化模型研究，全国贸易经济类核心期刊，2009年2月物流技术,2003年032霍亮，安敏，李欣，一种城市物流分区配送方法的研究，期3陈文兰，戴树贵，旅行商问题算法研究综述，滁州学院学报，2006 年 03 期国防科学技术大学,2003年4陈继业，旅行商问题的近似算法研究，注意：不仅提交纸质版，也提交电子版。电子版

24、发送 zbjianmo文件名：“题号学院姓名”，例如“ B题张三李四”各参赛者从若干给定题中任选一题。注意有的 为 1人独立完成，有的为合作。论文用白色 A4 纸单面打印；上下左右各留出至少 2.5厘米的页边距；从左侧装订。论文不能有 页眉，论文中不能有任何可能 显示答题人身份的标志。论文题目用三号黑体字、一 级标题用四号黑体字，并居中；二 级、三级标题用小四号黑体字，左端 对齐（不居中） 。论文中其他汉字一律采用小四 号宋体字，行距用单倍行距，打印 时应尽 量避免彩色打印。提请大家注意：摘要 应该是一份简明扼要的详细摘要（包括 关键词），在整篇论文评阅中占有重要 权重，请认真书写 （注意篇幅

25、不能超 过一页，且无需 译成英文）。引用 别人的成果或其他公 开的资料（包括 网上查到的资料） 必须按照 规定的 参考文献的表述方式在正文引用 处和参考文献中均明确列出。正文引用 处用方括 号标示参考文献的编号，如13等；引用 书籍还必须指出页码。参考文献按正文中的引用次序列出，其中 书籍的表述方式 为： 编号 作者，书名，出版地：出版社，出版年。参考文献中期刊杂志论文的表述方式 为： 编号 作者，论文名，杂志名，卷期号：起止页码，出版年。参 考文献中网上资源的表述方式 为： 编号 作者，资源标题，网址，访问时间（年月日）。报名全国竞赛队员个人信息（不计划报的不填，订在最前面！）姓名：学院：班

26、级：电话：阅读过的建模书籍参加培训次数及内 容计算机水平（编程、数学软件、OFFICE）学过的数学课程和 成绩写作方面的情况个人学习情况，班级 排名，优势科目参加建模竞赛的个 人优势自己觉得哪些方面 还有欠缺对数学建模的看法其它情况多人合作的还需要填写本表格队员姓名 工作内容队员1队员2队员3在整个建模中 所做的工作（尽 量细一些）程序完成人数据处理论文书写文献查阅报告书写创新点第一问第二问特殊工作其它工作（本页为题目、摘要、关键词，所有彩色字体要删除）城摘要摘要写作要求：摘要是整个论文核心思想的浓缩，读者通过阅读摘要了解论文的基本情况，决定是 否阅读正文。摘要一般包括：模型的数学归类（在数学

27、上属于什么类型） ； 建模的思想（思路）；算法思想 （求解思路）； 建模特点 （模型优点，建模思想或方法，算法特点，灵敏度分析，模型检验； 主要结果 （数值结果，结论） （要求逐一回答题目所提的全部“问题”） 摘要要求语言精炼、准确，常用术语为：针对什么问题、作了哪些重要假设、采 用了什么方法、建立了什么模型，获得了什么结论，主要创新是什么。摘要要反映所作 工作的闪光点。摘要用字准确，尽量达到少一字不行，多一字浪费的程度。不用修饰词、感叹句不能用表格、图表、公式代摘要；摘要主要是文字，可以有个别重要结果，一般 不使用表格公式图表。关键词：关键词一般 5 个左右，涉及论文的关键概念，给人们提供思

28、考的线索 ）（本页开始为正文，通常结构和要求见下面蓝色字体，注意引用或借鉴别人成果要有标注1）（一）.问题重述（或称问题的提出）根据本人对题目的理解，明确题目需要解决的问题。问题的重述尽管来自题目, 但不是抄写题目，特别是背景说明要简洁，不同的人对题目的理解可以不同。常用的套路是:XXXXXX是XX,研究XX具有一定现实意义。根据题目要求，需要解决以下 几个问题：（1）,（ 2）,.（二）.问题的分析对问题进行必要的分析，提供本人解决问题的主要思路及大致方法。特别是为研究问题本人提出的创新性概念、思想、解决方法等。简单说明解决每个问题的框架（三）.模型假设模型假设建模论文的重要组成部分。 实际生活中的问题往往非常复杂，不利于模 型的建立和求解。因此需要对许多情况进行简化处理，得到理想化的假设。在解决问题 的过程中，要求准确理解题目及其每个概念的意思，对使用的理论、给出的说法要有依 据。但是有些关键信息题目没有提供或事实上因涉密或其它原因难以