图12: 从O→B的有向图的路线
由上述所提的Dijkstra算法对问题分析, 根据LINGO软件(程序见附件2)不考虑圆弧求得的最短路线为: O→d→e→f→g→j→B, 总路程为829.68个单位. 2、对上方案进行优化, 考虑圆弧的情况
图13: 最终确定O→B路线图
通过Matlab软件(程序见附件3)求得. 如表2所示.
表2：机器人从O→B经过的最短路线 经过圆心 前切点 后切点 圆弧长度 到前一点点 的切线长度 O (0, 0) d (60, 300) (50.14, (51.68, 305.55) 4.23 305.78 301.64) e (150, (141.68 , (147.96, 444.79) 7.78 162.25 435) 440.55) f (220, （222.04 , (230, 470) 13.66 75.66 470) 479.79） g (220, （230, 530） (225.50, 538.35) 9.89 60 530) j (150, (144.50, (140.69, 596.35) 6.15 96.95 600) 591.65) B (100, 111.36 700) 总路程: L=853.7个单位 总时间: t?179.08秒 5.2.3 对O→C路径的求解 10
图14: O→C的路线图
1、不考虑圆弧的情况
将图14路线看做为有向图O→C, 运用图论的方法来确定最短的路线. 如图15所示.
e f d y p q c k r O b C s m n z l 图15: 从O→C的所有可能的路线
运用Dijkstra算法根据LINGO软件(程序见附件4)不考虑圆弧求得的最短路线为: O→l→r→s→C, 总路程为1068.83个单位. 2、对上述方案进行优化
11
图16：最终确定O→C路线图
运用Matlab软件求得. 如表3所示.
表3：机器人从O→C经过的最短路线 经过圆心 前切点 后切点 圆弧长度 到前一点点 的切线长度 O (0, 0) l (410, 100) (412.14, (418.05, 7.19 422..02 90.23) 94.06) r (720, 520) (728.05, ( 730, 520) 6.36 522.02 514.06) s (720, 600) (730, 600) (727.72 , 6.89 80 593.64) C (700, 640) 44.59 总路程: L=1088.1个单位 总时间t?221.71秒 5.2.4 对O→A→B→C→O进行求解 对O→A→B→C→O分开进行考虑, 取每一段的最短路线, 即总路线也是最短的. 已知O→A与O→C的最短路线, 再对A→B跟B→C分别进行研究. 1.线段与线段折点的简单处理
在对该问题采用了分段求解的方法进行处理, 在段与段之间转折点如A、B、C,当作尖点处理. 如图17所示.
12
图17
2.对A→B进行求解
运用Dijkstra算法, 根据LINGO软件求得最短路线为: 总路程为464.67个单位.
图18: A→B的路线图 图19: 最终路线图 通过Matlab软件(程序见附件5)求得. 如表4所示.
表4: 机器人从A→B经过的最短路线； 经过圆心 前切点 后切点 圆弧长度 到前一点点 的切线长度 A (300, 300) g (220, 530) (229.57, (228.08, 3.34 243.31 532.89) 535.89) j (150, 600) (141.92, (141.92, 2.56 96.95 594.11) 596.35) B (300, 300) 111.36 总路程: L=457.54个单位 总时间: t?92.9秒 3.对B→C进行求解 13
图20: B→C的路线图
根据LINGO软件求得的最短路线为：总路程为674.71个单位. 4.对上述方案进行优化
图21: B→C的最终路线图
通过Matlab软件(程序见附件6)求得. 如表5所示.
表5：机器人从B→C经过的最短路线； 经过点 圆心 前切点 后切点 圆弧长度 到前一点的切线长度 B (100, 700) h (270, (272, 689.80) (270.58, 0.51 170.88 680) 689.99) u (370, (368, 670.20) (370, 670) 2.01 97.98 680) v (430, (430, 670) (434.33, 4.48 60 680) 670.99) p (670, (535.67, (540, 740) 4.48 119.16 600) 739.01) q (670, (670, 740) (689.77, 13.55 130 730) 732.14) C (700， 94.34
14