洒水车线路优化问题(终极版)2003

洒水车路线优化问题 [键入文档副标题]   参赛学校：上师大附中   成员：丁伟东、汤申嘉、毛钰润 2011/7/31     课题摘要 随着夏天天气逐渐炎热，洒水车对路面的降温越来越重要，如何合理运用不同型号的洒水车进行路面降温工作正是本小组所研究的目标。 为了方便计算与路线设计，我们建立模型：假设大车与小车的速度、耗油量等全部相等。 为了达到最大限度的优化，我们考虑大车与小车对不同路段的洒水效率差异和边缘地带只允许顺时针单侧完成任务的条件，将主干道全部分给大车完成并利用外侧绿线进行连接，将内部非主干道部分交给小车完成。并且我们利用几何画板对所有路段进行了分段与长度测量，以极小的误差将大车和小车的路线长度分为了相等的两部分，使大车和小车在最短的时间内完成全部的路段工作量。以下展示大车小车分别的路线和任务路段。 (左图为大车行车路线，右图为小车行车路线。) 问题提出 1、如何合理使用两种不同的洒水车对三种不同的路段进行洒水作业，使得洒水车在最短的时间内完成洒水作业，并且尽量使得两车作业时间相等，工作量最小？ 2、如何设计路线，使洒水车在完成任务后恰好回到停车场（即如何完成两个欧拉圈）？ 3、如何设计路线，使大小两车的路线既不重叠也不遗漏？ 模型假设 A、 洒水车在路上的运作与行驶问题 1、 洒水车在路上一切运作正常，无堵车与红绿灯问题。 2、 洒水车单程在同一条车道上行驶，不考虑切换车道导致的路线总长增加。 3、 不考虑洒水车作业中水量减少使车重变轻和速度变快的问题。 4、 不考虑任何因素对车的影响，假设洒水车完全地匀速前进。 B、 两辆洒水车的行驶比较 1、 假设大小两车的行驶速度相同。 2、 假设大小两车的油耗等成本相同。 3、 假设大小两车的洒水效果相同。 C、 洒水车的路线问题 1、 不考虑洒水车的水量补给问题。 2、 根据实际情况，保证洒水车在最终回到停车场内。 3、 利用路程估算洒水作业的工作量。 4、 忽略比例尺的误差和路面的高低路况。 5、 将路口视作一点进行计算。 6、 不考虑内外侧车道的长度差，全部取路段中间长的平均值。 模型建立 原题分析： 本题两车的路线往返，即考虑到现实中上下行不同车道问题。来回两次必须确保反向，使得两边车道都能洒到水。由于外圈只需顺时针方向洒水，也就可以理解成外圈只需在内测路道洒水（即靠近城镇的一半车道），所以外圈以一个顺时针单圈进行考虑。 原图： 简化模型（弊端在于只注重线路简化，失去了比例。方便了线路连接和欧拉图的构造，但无法利用这张图进行均衡分配和优化。）： 不同路段分离图（便于测量计算各种路段的长度，为线路的优化铺垫基础）： （由于电脑显示屏尺寸不同问题，以下比例尺的标准与原图不同，但完全按照原图比例进行了放缩并且以下图片的比例相同，只影响到倍率，但不影响计算以及线路规划。） 主干道（总长：89.14CM）： 主要道路（82.82cm）： 一般道路（81.03cm）： （以上为基础模型） 矩形图模型：矩形图更加简洁明朗，对题意的初步理解和初步规划有很大的帮助。利用简洁的矩形图，直接对图进行分析。因为方正的矩形让你第一步就决定让外圈连接成一个完整的圈，并连接内部分支，组成最终的欧拉圈。然而，便于观察的矩形图，比例不正确，无法进一步计算。 分离图：将原图分离开，更加便于分配，不同路段应由不同车辆完成。并且对每一个路段进行了同比例测量，有了准确的数据，可以把矩形图的大概思想进一步转化为精确的定量关系可以进一步优化。可以在原先的基础上考虑一些内部小分支的分配，利用数据达到平衡。 小结：矩形图和分离图的两步法，先从浅层的基本分配快速入手，再通过数据，精准地完全分配完毕。两步法可以在短时间内完成相对优化的制定。可见，此模型是相对成功的。 模型求解 大车路线： 由于大车在主干道上只需要来回工作一次，而小车需要来回四次，其工作效率显而易见，所以决定利用大车对主干道进行洒水作业。然后结合题目中要求的边缘部分只允许顺时针方向进行洒水和红线的来回原则，所以只有外圈边缘部分需要调整使边缘成为欧拉圈，而圈内部分每条边全部是来回一次即每个点都是偶点，成为了欧拉圈的充要条件。外圈需要成为单向的欧拉圈，根据欧拉环游的条件，必须组成一个完整的圈。所以最终决定利用边缘的绿线将红线连成一个完整的圈。最后大车环绕边缘走一圈，并且在绕圈的同时进入内部部分红线绿线进行洒水，总计行车216.26cm。 小车路线： 为了便于达到欧拉环游的目的，所以让小车往返走各条非主干型道路，因为小车的线路全部为偶点，所以小车能够不重复不遗漏地走完大车不会走过的道路（具体线路正好覆盖整个路线，但方法较多，不作单一走法。）且以欧拉环游的方式回到停车场。经过几何画板的测量与计算，小车行进路线长218.84cm。 大车小车的路线正好覆盖了整个区域，并且以欧拉圈的形式回到了停车场，没有遗漏也没有重复，达到了优化的目标。另外两辆车的工作量几乎相等，可以在最短的时间内同时完成任务，避免出现一辆车空着另一辆还有一大段任务的情况，在相对性上进一步优化。 求解小结：大车开216.26cm，小车218.84cm。两辆车在最短时间内同时完成洒水任务。 模型验证 根据已建立的模型，我们将各个路口之间的距离量化。 经过计算得出整个街道总长为252.99cm，由于题设中假设大、小型洒水车的速度完全相同，两车行车路线的最优化安排的关键便在于如何安排量车型车总距离相同且尽可能不重复；又由于两车最终需回到停车场（即起点），问题的关键又转化到建立两个尽可能不重复的欧拉圆。 由于两种型号的车辆工作效率不同暂时假设由大型车完成所有的主干道洒水工作。由此建立模型A，经过计算得到主干道部分总长为89.14cm，即大型车至少需完成89.14cm路段（不考虑往返）的工作量，但显然在这种情况下无法完成一个欧拉圆，且大、小两车的行车路程相差极大。因此需要分配部分非主要道路给大型车完成。由于单行的话会出现奇点，无法完成欧拉环游，所以大型车不能走一般道路，所有的一般道路都必须由小型车完成。因此小型车至少需完成81.03cm（不考虑往返）的工作量。此时大、小两车的工作量相差为82.82cm（不考虑往返）。 又由于以上方案全部为往返车程（除边缘部分），内部全部为欧拉圈，总洒水长度为435.1cm，所以要想合理分配主要道路，使得两车行驶的总长度几乎相等（两车分别接近217cm）。 往返洒水已经确保小车行驶部分必然是欧拉圈。所以要保证大车行进的是欧拉圈，必然要保证边缘部分成为一个完整的圈，即一辆车去洒水，所以整个边缘有大车负责，组成欧拉圈。之后进一步对剩余路段进行再次分配并达到平衡。 在基本确定路线后，删去所有的一般道路、必经的主要道路以及所有的主干道，得到模型2，这一部分即为大型车和小型车共同分担的部分。结合基本模型与模型2，不难发现任何一部分一般道路只与模型2中的主要道路相通，得到模型3，即模型3中的主要道路为符合上述要求的部分，这些主要道路必须由小型车完成。通过几何画板的测量，得到小型车必须完成的部分，发现刚好与总路程的一半相接近（误差仅为2cm），且满足完成两个欧拉圆的要求。由此得出结论，所设的路线即为最优化方案。 模型2： 模型3： 模型优缺点： 优点： 1、 运用工具简单，便于操作。 2、 计算简单，能够快速按一定步骤制定优化的计划。 3、 分为路线制定（矩形图）和路线计算（原图分离版），两步能够更加精确地计算出最优路线。 缺点： 1、 将路线分成多段直线，虽然很接近，必然有误差。 2、 忽略了车速的各种影响，与现实有一定差距。 3、 大小两种车型油耗必然不同，由于方便计算与应用，忽略了成本的差异。 4、 没有考虑到水的补给问题，应该在路线上设定供给点。 5、 此模型是优化的一种，不一定为最优情况。 6、 只考虑一条道路全部分给同一辆车完成，不考虑两车同时完成的情况。 小结：由于此模型与现实的差距存在，并且忽略了部分影响因素，导致会有一定误差的存在；并且，此模型的优化只是本小组的假设情况下的最优化，可能还有更好地优化方案。 但是，此模型制定简单迅速，简单易懂，而且有两步法减小差距，在短时间内制定此优化方案，并且立即执行，必然有很大的好处；相对于其他情况，此模型是一个短时间制定的好方案。 参考文献 1、 高中应用数学选讲 2、 中学数学建模与赛题集锦 3、 数学模型引论---E.A.BENDER 4、 数学模型基础---王树禾