物流工程的路径规划.pptx

7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划7.3路径规划A、起始节点S被代入OPEN[图7-21(a)]，子节点A和B被代人OPEN[图7-21(b)]。起始节点S扩展后移到CLOSED，B、由于节点A、B的评价值分别为10、8，所以选中扩展节点B。B的子节点D、E、F，评价值分别为9、8、10，全都代人OPEN，扩展后节点B被移到CLOSED[图7-21(c)]。C、节点E评价值最小，选中扩展节点E。E的子节点H同评价值10都代入OPEN，扩展后节点E被移到CLOSED。D、OPEN中当前评价值最小的子节点是D，所以选中节点D。D的子节点H被再次搜索，节点D被移到CLOSED。注意到节点H的值g，由于过去的费用6(经由节点E、B返回到节点S)比新的费用7(经由节点D、B返回到S)小，所以不更换指针[图7-21(d)]。指针仍在E。由于当前OPEN上存在评价值f都为10的三个节点A、H、F，此时须对这三个节点A、H、F都分别向下扩展。E、用中断连接节点A，扩展节点C同评价值8都代人OPEN，节点A被移到CLOSED。然后，C的两个扩展节点I、H中，选中值f最小的节点I（实际上，ACH路径在先已经被否定），节点I同评价值10都代人OPEN，节点C同评价值8都被移到CLOSED。节点I的扩展节点即为目标，OPEN保持F、节点H的扩展节点即为目标，OPEN保持G、节点F的扩展节点即为目标，OPEN保持H、当前OPEN上三个节点I、H、F的评价值都为10,其后的扩展节点都是目标G。计算分别经三个节点F、H、I到目标G的评价值,经节点F到目标G的评价值最小。所以用中断连接扩展节点F，节点G连同评价值9都代人OPEN，节点F移到CLOSED[图7-21(e)]。在图7-22的搜索图G上，所有节点的估计值h(在节点上用括号给出)常常比真值h*小或相等。7.3路径规划A、起始节点S被代入OPEN，子节点A、B连同评价值f6、8被代人OPEN，起始节点S扩展后移到CLOSED。B、由于节点A、B的评价值f分别为6、8，所以节点A扩展子节点C、D后移到CLOSED，节点B、C、D连同各自的评价值8、8、9都代入OPEN。C、用中断连接扩展节点B，节点B扩展子节点E、F。子节点E、F连同评价值8、9都代入OPEN，节点B扩展后代入CLOSED。再次搜索节点D。这时，如果注意到节点D的值g，由于新的费用值4(经由节点B返回到节点S)比过去的费用5(经由节点A返回到节点S)小，所以要更换指针，重新计算的评价值f变为9[图7-23(a)]。D、仍然用中断连接扩展节点C，节点C扩展子节点I、H。子节点I、H连同评价值10、9都代入OPEN，节点C移到CLOSED[图7-23(b)]，E、当前OPEN上五个节点I、H、D、E、F。所以选中评价值f最小的扩展节点E。然后，把节点E代入CLOSED，再次搜索节点H。F、这时，注意到节点H的值g，比起过去的费用7(经由节点C，A返回节点S)来新的费用6(经由节点E、B返回到节点S)要小，所以更换指针，重新计算H的评价值f为8[图7-23(c)]G、当前OPEN上扩展值f最小的节点H，其后的扩展节点是目标G，节点G以评价值8代人OPEN，节点H代入CLOSEDH、最后，节点G如果选择作为值f最小的节点，则把指针返回到节点H、E、B、S，最终得到费用8的最短路径。这里，由于节点H的估计值h与真值h*相比过小，所以这个最佳路径上的节点必须调整。4．AGV的路径规划实例Dijkstra最短路径确定法。图7-24中的节点1～5是AGV运行路线上的岔口，6～18是货物装卸点，6是系统的入口，9、15、16是系统的出口，19是AGV停车处。在图7-24(b)中，将AGV可能的运行方向用箭头进行了表示。7.3路径规划(1)因为节点1～5是找出6～18货物装卸点间最短距离的关键点，故先只考虑系统中的各岔口即节点l～5间的最短路径。为此，将相应箭头所表示的距离填人下面的距离矩阵。因节点1、3之间无直接连接的箭头，但两者之间可通过16、18连在一起，所以C1,3=C1,16+C16,18+Cl8,3=84。C3,4=∞表示所连两点间无直接联系，之间的联系要通过岔口节点。由此得到系统的距离矩阵(表7-2)。表7-2距离矩阵(2)搜索过程A、最短路径法首先要求找到搜索的起始点i，起始点i必须是通过一个单箭头就能和其余节点相连最多的节点。很显然，图7-24(b)中的节