洒水车线路优化问题(终极版)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 E1F1 2 10厘 厘 D1E1 3 43厘 厘 B1C1 3 92厘 厘 A1B1 3 96厘 厘 ZA1 0 66厘 厘 YZ 2 76厘 厘 XY 3 67厘 厘 LX 5 60厘 厘 VW 1 72厘 厘 UV 1 22厘 厘 TU 3 27厘 厘 ST 1 84厘 厘 QS 2 04厘 厘 PQ 3 67厘 厘 OP 2 32厘 厘 NO 6 61厘 厘 MN 3 54厘 厘 LM 4 24厘 厘 KL 3 97厘 厘 JK 5 19厘 厘 IJ 1 83厘 厘 HI 2 59厘 厘 GH 2 08厘 厘 FG 2 47厘 厘 EF 2 98厘 厘 DE 2 80厘 厘 CD 3 33厘 厘 BC 2 81厘 厘 AB 2 52厘 厘 主要道路 82 82cm J1K1 1 55厘 厘 I1J1 2 12厘 厘 G1H1 2 45厘 厘 F1G1 3 35厘 厘 E1F1 3 33厘 厘 D1E1 3 95厘 厘 B1C1 1 70厘 厘 VB1 3 51厘 厘 ZA1 1 89厘 厘 YZ 2 17厘 厘 WY 3 48厘 厘 WX 2 20厘 厘 VW 2 24厘 厘 UV 4 08厘 厘 TU 3 32厘 厘 ST 1 84厘 厘 RS 3 77厘 厘 QR 4 34厘 厘 PQ 2 92厘 厘 OP 1 94厘 厘 NO 3 37厘 厘 LM 2 64厘 厘 KL 1 84厘 厘 HK 3 22厘 厘 IJ 3 31厘 厘 HI 2 99厘 厘 FG 2 23厘 厘 EF 2 93厘 厘 CD 1 80厘 厘 BC 1 27厘 厘 AB 1 07厘 厘 一般道路 81 03cm V1W1 1 59厘 厘 S1U1 2 62厘 厘 S1T1 1 74厘 厘 I1S1 1 57厘 厘 R1I1 1 84厘 厘 P1Q1 1 04厘 厘 O1P1 2 20厘 厘 N1O1 2 54厘 厘 L1M1 1 94厘 厘 K1L1 1 70厘 厘 I1J1 2 54厘 厘 H1I1 1 82厘 厘 G1H1 2 58厘 厘 E1F1 3 87厘 厘 C1D1 1 67厘 厘 B1C1 2 77厘 厘 ZA1 1 92厘 厘 YZ 3 72厘 厘 WX 3 54厘 厘 UV 2 88厘 厘 MT 1 36厘 厘 SM 2 79厘 厘 RJ 3 25厘 厘 QR 2 84厘 厘 FP 2 56厘 厘 OF 2 33厘 厘 MN 1 99厘 厘 LM 2 55厘 厘 JK 2 17厘 厘 IJ 1 88厘 厘 GH 2 20厘 厘 FG 1 99厘 厘 EF 2 82厘 厘 CD 2 17厘 厘 AB 2 04厘 厘 以上为基础模型 矩形图模型 矩形图更加简洁明朗 对题意的初步理解和初步规划有很大的帮助 利 用简洁的矩形图 直接对图进行分析 因为方正的矩形让你第一步就决定让外圈连接成一 个完整的圈 并连接内部分支 组成最终的欧拉圈 然而 便于观察的矩形图 比例不正 确 无法进一步计算 分离图 将原图分离开 更加便于分配 不同路段应由不同车辆完成 并且对每一个 路段进行了同比例测量 有了准确的数据 可以把矩形图的大概思想进一步转化为精确的 定量关系可以进一步优化 可以在原先的基础上考虑一些内部小分支的分配 利用数据达 到平衡 小结 矩形图和分离图的两步法 先从浅层的基本分配快速入手 再通过数据 精准 地完全分配完毕 两步法可以在短时间内完成相对优化的方案制定 可见 此模型是相对 成功的 模型求解模型求解 大车路线 大 大 大 大 大 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 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 D2 K2C 2 07厘 厘 J2K2 1 96厘 厘 HI 2 59厘 厘 D2E2 1 95厘 厘 L1D2 2 24厘 厘 S1T1 1 64厘 厘 Q1S1 2 21厘 厘 Q1Z 3 12厘 厘 Q1R1 2 48厘 厘 P1Q1 1 89厘 厘 FP1 2 22厘 厘 N1O1 2 08厘 厘 J1N1 3 42厘 厘 FL1 1 43厘 厘 K1H 2 42厘 厘 J1K1 2 15厘 厘 I1J1 4 20厘 厘 C1I1 4 08厘 厘 H1C1 4 90厘 厘 G1H1 4 42厘 厘 WG1 3 06厘 厘 E1F1 2 10厘 厘 D1E1 3 43厘 厘 B1C1 3 92厘 厘 A1B1 3 96厘 厘 ZA1 0 66厘 厘 YZ 2 76厘 厘 XY 3 67厘 厘 LX 5 60厘 厘 VW 1 72厘 厘 UV 1 22厘 厘 TU 3 27厘 厘 ST 1 84厘 厘 QS 2 04厘 厘 PQ 3 67厘 厘 OP 2 32厘 厘 NO 6 61厘 厘 MN 3 54厘 厘 LM 4 24厘 厘 KL 3 97厘 厘 JK 5 19厘 厘 IJ 1 83厘 厘 GH 2 08厘 厘 FG 2 47厘 厘 EF 2 98厘 厘 DE 2 80厘 厘 CD 3 33厘 厘 BC 2 81厘 厘 AB 2 52厘 厘 由于大车在主干道上只需要来回工作一次 而小车需要来回四次 其工作效率显而易 见 所以决定利用大车对主干道进行洒水作业 然后结合题目中要求的边缘部分只允许顺 时针方向进行洒水和红线的来回原则 所以只有外圈边缘部分需要调整使边缘成为欧拉圈 而圈内部分每条边全部是来回一次即每个点都是偶点 成为了欧拉圈的充要条件 外圈需 要成为单向的欧拉圈 根据欧拉环游的条件 必须组成一个完整的圈 所以最终决定利用 边缘的绿线将红线连成一个完整的圈 最后大车环绕边缘走一圈 并且在绕圈的同时进入 内部部分红线绿线进行洒水 总计行车 216 26cm 小车路线 W1Y1 2 61厘 厘 W1X1 1 74厘 厘 W1N1 1 76厘 厘 S1W1 1 70厘 厘 U1V1 1 77厘 厘 S1T1 2 62厘 厘 P1S1 1 57厘 厘 Q1R1 1 02厘 厘 P1Q1 1 04厘 厘 N1P1 1 69厘 厘 N1O1 1 96厘 厘 G1N1 3 08厘 厘 G1M1 1 47厘 厘 F1G1 1 77厘 厘 F1L1 1 64厘 厘 I1K1 2 98厘 厘 D1I1 3 18厘 厘 I1J1 1 57厘 厘 D1O 2 81厘 厘 H1I1 2 52厘 厘 C1G1 4 34厘 厘 E1F1 2 71厘 厘 C1E1 1 79厘 厘 C1D1 3 05厘 厘 YC1 2 26厘 厘 YB1 2 42厘 厘 ZA1 0 91厘 厘 YZ 1 79厘 厘 XY 3 01厘 厘 QX 2 55厘 厘 TV 1 46厘 厘 TU 2 15厘 厘 ST 2 21厘 厘 QS 3 00厘 厘 QR 2 51厘 厘 OQ 3 06厘 厘 OP 2 22厘 厘 NO 1 17厘 厘 MN 2 88厘 厘 JM 2 46厘 厘 KL 3 16厘 厘 JK 2 87厘 厘 IJ 1 40厘 厘 BI 3 66厘 厘 BH 1 98厘 厘 DG 3 60厘 厘 EF 2 19厘 厘 CD 2 70厘 厘 BC 2 27厘 厘 AB 3 05厘 厘 为了便于达到欧拉环游的目的 所以让小车往返走各条非主干型道路 因为小车的线 路全部为偶点 所以小车能够不重复不遗漏地走完大车不会走过的道路 具体线路正好覆 盖整个路线 但方法较多 不作单一走法 且以欧拉环游的方式回到停车场 经过几何 画板的测量与计算 小车行进路线长 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 中的主要道路 为符合上述要求的部分 这些主要道路必须由小型车完成 通过几何画板