物资的配送

2015 高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上 咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其 他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用 处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违 反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示 （包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号（从 A/B/C/D 中选择一项填写）： 我们的报名参赛队号（12 位数字全国统一编号）： 参赛学校（完整的学校全称，不含院系名）： 参赛队员（打印并签名） ：1.2.3.指导教师或指导教师组负责人 （打印并签名）：日期：年月日（此承诺书打印签名后作为纸质论文的封面，注意电子版论文中不得出现此页。以上内容 请仔细核对，特别是参赛队号，如填写错误，论文可能被取消评奖资格。）2015 高教社杯全国大学生数学建模竞赛编号专用页赛区评阅记录（可供赛区评阅时使用）：1平 阅彳备送全国评奖统一编号（由赛区组委会填写）：全国评阅统一编号（由全国组委会填写）：此编号专用页仅供赛区和全国评阅使用，参赛队打印后装订到纸质论文的第二页上。注意电子版论文中不得出现此页，即电子版论文的第一页为标题和摘要页。物资的配送的数学模型摘要物资配送问题是在我们生活中常见的问题，这里问题的求解，不仅有利于我们节省大量时间，同时也能够使我们的物资配送更加有效率的到达每一个客户手中，实现利益的最 大化。在本题中针对在物流中心的配货问题，我们可以利用图论的观点，将送货点和物流 中心抽象成几个孤立的点。而车辆的行使路径抽象成线，这样可以简单有效的用数学的思 想来解决生活中的实际问题，利用两点之间的距离和配送关系确定出最优的配送方式。针对问题一：建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。 在求解的过程中我们首先想到的就是 VRPTW 模型，利用遗传算法1求解路径。针对问题二：首先是对具体生活中的问题进行分析，主要有一下几个条件的限制:（1）时间限制；（2）载重量的限制；（3）等待时间与早到时间的损失。利用亚启发式算法中的遗传算法，在最初求解过程中，我们得到的初步数据是 910km， 最后利用优化工具箱对相邻两点之间路径最短进行了进一步优化后，得到了 885km 的答案。关键词：两点之间最短路 遗传算法 VRPTW 问题 亚启发式算法 最优设计物资的配送一）问题重述某物流中心拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/ 小时）相同，该物流中心用这样的车为若干个客户配送物资，物流中心与客户以及客户与 客户之间的公路里程（千米）为已知。每天，各客户所需物资的重量（吨）均已知，并且 每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物流中心出发 最后回到物流中心。求解当天出动多少台车，行驶路径如何时，总运行里程最短？要求送 货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定 的惩罚。该物流中心希望：1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。根据生活实 际建立合适的数学模型。2. 具体求解以下算例，并给出我们实际使用的软件名称、命令和编写的全部计算机源 程序。例载重量为Q二8吨、平均速度为v = 50千米/小时的送货车辆从物流中心（i = 0）出发，为编号是i二1,2,3 啲8位客户配送物资。某日，第i位客户所需物资的重量为q （q< Q）吨，在第i位客户处卸货时间为s小时，第i位客户要求送货车辆到达的时间范围 iia ,b 由表1给出。物流中心与各客户以及各客户间的公路里程（单位：千米）由表2给i i出。问当日如何安排送货车辆（包括出动车辆的台数以及每一台车辆的具体行驶路径）才 能使总运行里程最短。二）问题的分析 对问题一的分析：主要通过读题干，从其中抽象出合理的数学模型，能够确定自己合理的数学模型，并 且能够通过什么方法来求解生活中的实际问题。首先我们要将送货点和物流中心抽象成几 个孤立的点，将车辆抽象成可以移动的点，可以通过移动将所有的点能够联系起来。这样 自然就可以想到图论。在求解的过程中我们首先想到的就是 VRPTW 模型，利用亚启发式算 法中的遗传算法。进行模型的建立以及算法的实现。对问题二的分析：对于问题二，其实就是对问题一所建立的模型进行检验，能不能非常好的与生活中的 物资配送问题联系在一起，非常合理的解决它。我们在求解的过程中时间的弊端可以用路 程弥补，反之亦然。首先要确定所需要的车辆数量，最后利用优化工具箱对相邻两点之间 路径最短进行了进一步优化后。（三）模型假设1.物流中心出发到送货点，最后回到物流中心。2.不考虑路面的情况。3. 每辆车的载重量均相同。4. 每辆车的载重量的运输过程中不会发生偏差。5. 不考虑车辆的行使路程限制。6. 物流中心和送货点都抽象成几个孤立点。7. 没有其他意外情况会造成时间的消耗和费用的减少8. 每个客户点不会要求退货。9. 每位客户所需的货物可以混装。四）符号及变量说明符号含义K物流中心配送货物的车辆数N总的客户点数Q车辆的载重量mi客户i需要的货物重量ti到达客户i所用时间fi在客户i处的服务时间ei客户i处的早到时间li客户i处的迟到时间dij客户i到客户j的距离Xijk车辆k从客户i到客户j为1,否则为0Yik车辆k服务客户i为1,否则为0m物流中心用于配送的车辆ai客户i允许最早到达时间bi客户i允许最晚到达时间p (t)k i时间惩罚函数五）模型的建立与求解问题一模型的建立由题中给予我们的条件我们可以非常明显的构建条件约束下的运输模型，在运输的过 程中我们需要考虑每辆车的载重量，也要考虑我们在运输过程中，时间的要求对我们运输 过程中所产生的影响，这是我们不可以避免的，同时我们可以利用这些条件建立合适的模 型，最终形成最佳的运输方案。1) 目标函数min另另另i=1 j=1 k=1C Xij ijk+另另P (t)k ii=1 k=12) 约束条件mY < Q(k e1,2 K)i iki=1Y =0,1(电0)(k g1,2 K)ikY = m (i = 0)(k g1,2 K)ik迓X = Y (j wl,2,N)ijkjki=1迓X = Y (i wl,2,N)ijk iki=1(k g1,2 K )(k g1,2 K )X =o,l(k g1,2 K )ijk P (t )k ir c + p Q (a -1 )1 1 k i i0.c + pm (t - b )2 2 i i it < aa < t < b(k g 1,2 K)i i it > bii5.1 模型的建立在分析问题中，考虑到用遗传算法，故先对客户进行编码，我们采用自然数编码的原 则，将开始与结尾均赋值为 0，表示物流中心，例如：01245n05.1.1 种群初始化以载重量为评估标准，插入物流中心0,当艺m < Q，且工m > Q，在t处插入物流中ii心 0 ，将客户分为若干组，即0123045n05.1.2 适应度评估在这个问题的求解过程中，我们引入了惩罚函数，对于载重量超过q吨的个体，以及 没有在要求范围内到达的进行惩罚，每个个体的适应度为/ (厂)。i5.1.3 选择算子f (J针对这个问题，我们采用轮盘赌法，每个个体被选中的概率为亠 ，通过计算其累£ f (r)ir=1计概率与随机生成数的比较，决定是否淘汰。5.1.4 交叉算子对于某些特殊情况，可能会使一些超级基因一直遗传，从而陷入局部最优，我们对其 进行概率交叉。5.1.5 变异算子加入变异能增大种群的多样性，在全局找最优解。问题二的建立与求解根据问题一的分析，首先要确定所需要的车辆数量4 m = 亠i，(a = 0.95)，解得 aQm = 3，生成初始解在8位客户间插入两个物流中心012304560780即把客户分为三组，适应度评估在每个个体中，对于超过时间限制或者超过车辆的最大载重量的个体惩罚。VP 4选择算子个体12345678910适应度12345678910选择概率0.0180.0360.0550.0730.0910.1090.1270.1450.1640.182累计概率0.0180.0540.1090.1820.2730.3820.5090.6540.8181.000因为有10 个个体，需对其进行10 次选择，所以产生10 个（0，1）之间的随机数，假 设产生的随机数为 0.341，0.425，0.916，0.937，0.238，0.121，0.158，0.551，0.653，0.721 将该随机数与个体的累计概率比较，累计概率大于随机数则被选中，则一次序号为 6，7， 10，10，5，4，4，8，8，9 个体被选中，在这一次的选择中，序号为1，2，3 的个体被淘 汰，代之适应度更高的 4，8，10。交叉算子我们保存可能是最优路径的路径，故选择物流中心作为交叉点，将选中的基因先移到 首项，如图选择交叉点双亲1012034506780双亲2036504710280双亲ltemp034501206780双亲1后代034506701280变异算子为了使得已经选择好的个体不被，故在选择变异点时，不选择物流中心选择变异点父代012304560780子代012604530780在这里，我们选择进化 50 代，种群大小为 100，交叉概率为 0.9，变异概率为 0.1 基于会有不确定因素干扰，在写程序的时候进行多次循环，取最小值，通过MATLAB计算, 得出初步解为路线载重量行驶路程迟到时间等待时间总路程0 T 6 T 4 T 0726500