洒水车线路优化问题2003

《洒水车线路优化问题2003》由会员分享，可在线阅读，更多相关《洒水车线路优化问题2003（9页珍藏版）》请在装配图网上搜索。

1、参赛学校：上师大附中成员：丁伟东、汤申嘉、毛钰润2011/7/31洒水车路线优化问题键入文档副标题课题摘要随着夏天天气逐渐炎热，洒水车对路面的降温越来越重要，如何合理运用不同型号的洒 水车进行路面降温工作正是本小组所研究的目标。为了方便计算与路线设计，我们建立模型：假设大车与小车的速度、耗油量等全部相等。为了达到最大限度的优化，我们考虑大车与小车对不同路段的洒水效率差异和边缘地带 只允许顺时针单侧完成任务的条件，将主干道全部分给大车完成并利用外侧绿线进行连接 将内部非主干道部分交给小车完成。并且我们利用几何画板对所有路段进行了分段与长度测 量，以极小的误差将大车和小车的路线长度分为了相等的两部

2、分，使大车和小车在最短的时 间内完成全部的路段工作量。以下展示大车小车分别的路线和任务路段。（左图为大车行车路线，右图为小车行车路线。）问题提出1、如何合理使用两种不同的洒水车对三种不同的路段进行洒水作业，使得洒水车在最短的时间内完成洒水作业，并且尽量使得两车作业时间相等，工作量最小？2、如何设计路线，使洒水车在完成任务后恰好回到停车场（即如何完成两个欧拉圈）？3、如何设计路线，使大小两车的路线既不重叠也不遗漏？模型假设A、洒水车在路上的运作与行驶问题1、洒水车在路上一切运作正常，无堵车与红绿灯问题。2、洒水车单程在同一条车道上行驶，不考虑切换车道导致的路线总长增加3、不考虑洒水车作业中水量减

3、少使车重变轻和速度变快的问题。4、不考虑任何因素对车的影响，假设洒水车完全地匀速前进。B、两辆洒水车的行驶比较1、假设大小两车的行驶速度相同。2、假设大小两车的油耗等成本相同。3、假设大小两车的洒水效果相同。C、洒水车的路线问题1、不考虑洒水车的水量补给问题。2、根据实际情况，保证洒水车在最终回到停车场内。3、利用路程估算洒水作业的工作量。4、忽略比例尺的误差和路面的高低路况。5、将路口视作一点进行计算。6、不考虑内外侧车道的长度差，全部取路段中间长的平均值。模型建立原题分析： 本题两车的路线往返，即考虑到现实中上下行不同车道问题。来回两次必须确保反向使得两边车道都能洒到水。由于外圈只需顺时针

4、方向洒水，也就可以理解成外圈只需在内测 路道洒水（即靠近城镇的一半车道），所以外圈以一个顺时针单圈进行考虑。原图：简化模型（弊端在于只注重线路简化，失去了比例。方便了线路连接和欧拉图的构造，但无 法利用这张图进行均衡分配和优化。）：OP= 2.3厘米厶匕5.6厘米EF = 2.1厘米PQ= 3.6厘 米 * 3.6厘 米不同路段分离图（便于测量计算各种路段的长度，为线路的优化铺垫基础）：（由于电脑显示屏尺寸不同问题，以下比例尺的标准与原图不同，但完全按照原图比例进行了放缩并且以下图片的比例相同，只影响到倍率，但不影响计算以及线路规划。）主干道（总长：89.14CM）：AB= 2.5厘 米 HI

5、= 2.5厘 米BC= 2.8厘米d 1.8厘米CD= 3.3厘米JK= 5.1厘米 QS= 2.0厘米迄 2.7厘米DE= 2.8厘米KL= 3.9厘米 ST= 1.8厘米孕=0.6厘米EF= 2.9厘米LM= 4.2厘米 TU= 3.2厘米勺锋=3.9厘米EG= 2.4厘米 MN= 3.5厘米 UV= 1.2厘米BC = 3.9厘米GH= 2.0厘米 NO= 6.6厘米 VW= 1.7厘米= 3.4厘米主要道路（82.82cm）：AB = 1.07 厘米BC = 1.27 厘米CD = 1.8 0 厘米EF = 2.93 厘米FG = 2.23 厘米H = 2.99厘米J 3.31厘米HK

6、 = 3.22 厘米KL = 1.84厘米LM = 2.6 4 厘米NO = 3.37 厘米OP = 1.9 4 厘米PQ = 2.92 厘米QR = 4.34 厘米RS = 3.77 厘米ST = 1.8 4 厘米TU = 3.32 厘米UV = 4.08厘米VW = 2.2 4 厘米 WX = 2.2 0 厘米 刖=3.48厘米 YZ = 2.17 厘米 ZA1 = 1.89 厘米 VB1 = 3.51 厘米 BC = 1.70 厘米 DE = 3.95 厘米 E1F1 = 3.33厘米FG = 3.35 厘米GH = 2.45 厘米J= 2.12厘米J1K1 = 1.55厘米般道路（81

7、.03cm）：AB = 2.04 厘米CD = 2.17 厘米EF = 2.82厘米 _QR = 2.84厘米FG = 1.99厘米 rj= 3.25厘米 GH = 2.20厘米 SM = 2.79厘米 J 1.88厘米MT = 1.36厘米JK = 2.17厘米厂，UV = 2.88 厘米LM = 2.55 厘米MN = 1.99厘米 WX = 3.54厘米OF = 2.33厘米YZ = 3.72厘米= 1.94厘米FP = 2.56厘米 各=1.92厘米 NO=2-54厘米BC = 2.77厘米 TP1 = 2.20厘米C1D1 = 1.67厘米 P1Q1 = 1.04厘米1 -1L ,

8、R/ = 1.84厘米E1F1 = 3.87厘米1厂，IS = 1-57厘米G1H1 = 2.58 厘米 +H占=1.82厘米S1Ti = 1.74厘米 J = 2.54厘米 S1U-= 2.62厘米 K1L1 = 1.70厘米 V1W1 = 1.59厘米以上为基础模型）矩形图模型：矩形图更加简洁明朗，对题意的初步理解和初步规划有很大的帮助。利用 简洁的矩形图，直接对图进行分析。因为方正的矩形让你第一步就决定让外圈连接成一个完 整的圈，并连接内部分支，组成最终的欧拉圈。然而，便于观察的矩形图，比例不正确，无 法进一步计算。分离图：将原图分离开，更加便于分配，不同路段应由不同车辆完成。并且对每一

9、个路 段进行了同比例测量，有了准确的数据，可以把矩形图的大概思想进一步转化为精确的定量 关系可以进一步优化。可以在原先的基础上考虑一些内部小分支的分配，利用数据达到平衡。小结：矩形图和分离图的两步法，先从浅层的基本分配快速入手，再通过数据，精准地 完全分配完毕。两步法可以在短时间内完成相对优化的方案制定。可见，此模型是相对成功 的。模型求解大车路线：大车路线：D2-E2-D2-L1-F-G-H-K1-J1-N1-O1-N1-J1-I1-C1-O1-B1-T1-S1-Q1-R1-Q1-P1-F-P1-Q1-Z-Q1-S1-T1-A1-Z-Y-X-D-E-F-E-D-L-D-C-K2-J2-K2-

10、C-B-A-B-C-D-X-Y-Z-A1-T1-B1-O1-C1-H1-G1-W-V-U-T-S-Q-D1-I2-E1-F1-E1-I2-D1-P-O-A-N-M-J2-L-K-J-I-E2-H-G-F-L1-D2AB = 2.52 厘米BC = 2.81 厘米CD = 3.33 厘米DE = 2.8 0 厘米EF = 2.98 厘米FG = 2.47 厘米GH = 2.08厘米H = 2.59厘米IJ= 1.83 厘米JK = 5.19 厘米KL= 3.97 厘米LM = 4.2 4 厘米MN = 3.5 4厘米NO = 6.61厘米OP = 2.32厘米LX = 5.60厘米EF = 2.

11、10厘米KH = 2.42厘米丄N = 3.42厘米PQ = 3.67厘米XY = 3.67厘米WG1 = 3.06厘米F匚=1.43厘米NO = 2.08厘米QS = 2.04厘米YZ = 2.76厘米匕=4.42厘米LD = 2.24厘米FP+.= 2.22厘米ST = 1.84厘米ZA = 0.66厘米HC = 4.90厘米_S1f1 = 1.64厘米PQ = 1.89厘米TU = 327厘米 A1B1 = 3.96厘米 = 4.08厘米 DE = 1.95厘米 QR = 2.48厘米 UV = 1.22厘米 BC = 3.92厘米 J= 4.20厘米 JK 1.96厘米 Q1Z = 3

12、.12厘米 VW = 1.72厘米 D1E1 = 3.43厘米 J1K1 = 2.15厘米 k2c = 2.07厘米 Qs； = 2.21 厘米由于大车在主干道上只需要来回工作一次，而小车需要来回四次，其工作效率显而易见， 所以决定利用大车对主干道进行洒水作业。然后结合题目中要求的边缘部分只允许顺时针方 向进行洒水和红线的来回原则，所以只有外圈边缘部分需要调整使边缘成为欧拉圈，而圈内 部分每条边全部是来回一次即每个点都是偶点，成为了欧拉圈的充要条件。外圈需要成为单 向的欧拉圈，根据欧拉环游的条件，必须组成一个完整的圈。所以最终决定利用边缘的绿线 将红线连成一个完整的圈。最后大车环绕边缘走一圈，

13、并且在绕圈的同时进入内部部分红线 绿线进行洒水，总计行车 216.26cm。小车路线:UAB = 3.05 厘米BC = 2.27 厘米CD= 2.7 0 厘米CE = 1.79 厘米 11首E = 2.71厘米CG = 4.34 厘米 - 1H丄=2.52厘米DO = 2.81 厘米 G；N = 3.08厘米 U1V1 = 1.77厘米 BH = 1.98厘米 IJ = 1.57厘米=1.96厘米 SW1 = 1.70厘米 B = 3.66厘米DL = 3.18厘米 Np = 1.69厘米 WN = 1.76厘米 IJ= 1.40厘米 K = 2.98厘米 P1Q1 = 1.04厘米 WX1

14、 = 1.74厘米 竺=2.87厘米 F1L1 = 1.64厘米 QR = 1.02厘米 WY = 2.61 厘米 KL = 3.16厘米 FG = 1.77厘米 P；S； = 1.57厘米 EF = 2.19厘米 JM = 2.46厘米 GM = 1.47厘米 S1T1 = 2.62厘米 DG = 3.60厘米 MN = 2.88厘米NO = 1.17 厘米OP = 2.22 厘米OQ = 3.06 厘米QR = 2.51 厘米QS = 3.0 0 厘米ST = 2.21 厘米TU = 2.15 厘米TV = 1.46 厘米 QX = 2.55 厘米 XY = 3.01 厘米YZ = 1.7

15、9 厘米ZA = 0.91 厘米1YB1 = 2.42 厘米YC = 2.26 厘米C1D1 = 3.05 厘米为了便于达到欧拉环游的目的，所以让小车往返走各条非主干型道路，因为小车的线路 全部为偶点，所以小车能够不重复不遗漏地走完大车不会走过的道路（具体线路正好覆盖整 个路线，但方法较多，不作单一走法。）且以欧拉环游的方式回到停车场。经过几何画板的 测量与计算，小车行进路线长218. 84cm。大车小车的路线正好覆盖了整个区域，并且以欧拉圈的形式回到了停车场，没有遗漏也 没有重复，达到了优化的目标。另外两辆车的工作量几乎相等，可以在最短的时间内同时完 成任务，避免出现一辆车空着另一辆还有一大

16、段任务的情况，在相对性上进一步优化。求解小结：大车开216.26cm，小车218. 84cm。两辆车在最短时间内同时完成洒水任务。模型验证根据已建立的模型，我们将各个路口之间的距离量化。经过计算得出整个街道总长为252.99cm,由于题设中假设大、小型洒水车的速度完全 相同，两车行车路线的最优化安排的关键便在于如何安排量车型车总距离相同且尽可能不重 复；又由于两车最终需回到停车场（即起点），问题的关键又转化到建立两个尽可能不重复 的欧拉圆。由于两种型号的车辆工作效率不同暂时假设由大型车完成所有的主干道洒水工作。由 此建立模型A,经过计算得到主干道部分总长为89.14cm，即大型车至少需完成89

17、.14cm路 段（不考虑往返）的工作量，但显然在这种情况下无法完成一个欧拉圆，且大、小两车的行 车路程相差极大。因此需要分配部分非主要道路给大型车完成。由于单行的话会出现奇点， 无法完成欧拉环游，所以大型车不能走一般道路，所有的一般道路都必须由小型车完成。因 此小型车至少需完成81.03cm （不考虑往返）的工作量。此时大、小两车的工作量相差为 82.82cm （不考虑往返）。又由于以上方案全部为往返车程（除边缘部分），内部全部为欧拉圈，总洒水长度为 435.1cm，所以要想办法合理分配主要道路，使得两车行驶的总长度几乎相等（两车分别接近 217cm）。往返洒水已经确保小车行驶部分必然是欧拉圈

18、。所以要保证大车行进的是欧拉圈，必 然要保证边缘部分成为一个完整的圈，即一辆车去洒水，所以整个边缘有大车负责，组成欧 拉圈。之后进一步对剩余路段进行再次分配并达到平衡。在基本确定路线后，删去所有的一般道路、必经的主要道路以及所有的主干道，得到 模型 2，这一部分即为大型车和小型车共同分担的部分。结合基本模型与模型2，不难发现 任何一部分一般道路只与模型2 中的主要道路相通，得到模型3，即模型3中的主要道路为 符合上述要求的部分，这些主要道路必须由小型车完成。通过几何画板的测量，得到小型车 必须完成的部分，发现刚好与总路程的一半相接近（误差仅为2cm）,且满足完成两个欧拉 圆的要求。由此得出结论

19、，所设的路线即为最优化方案。模型2：模型 3：厶模型优缺点：优点：1、运用工具简单，便于操作。2、计算简单，能够快速按一定步骤制定优化的计划。3、分为路线制定（矩形图）和路线计算（原图分离版），两步能够更加精确地计算出最优 路线。缺点：1、将路线分成多段直线，虽然很接近，必然有误差。2、忽略了车速的各种影响，与现实有一定差距。3、大小两种车型油耗必然不同，由于方便计算与应用，忽略了成本的差异4、没有考虑到水的补给问题，应该在路线上设定供给点。5、此模型是优化的一种，不一定为最优情况。6、只考虑一条道路全部分给同一辆车完成，不考虑两车同时完成的情况。 小结：由于此模型与现实的差距存在，并且忽略了部分影响因素，导致会有一定误差的存在； 并且，此模型的优化只是本小组的假设情况下的最优化，可能还有更好地优化方案。但是，此模型制定简单迅速，简单易懂，而且有两步法减小差距，在短时间内制定此优化 方案，并且立即执行，必然有很大的好处；相对于其他情况，此模型是一个短时间制定的好参考文献1、高中应用数学选讲 2、中学数学建模与赛题集锦 3、数学模型引论 -E.A.BENDER4、数学模型基础 -王树禾