基于贪心算法的AGV路径规划可行性判断的研究

《基于贪心算法的AGV路径规划可行性判断的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛基于贪心算法的AGVS路径规划可行性判断的研究徐翠霞(潍坊学院计算机与通信工程学院山东潍坊261061)摘要：针对AGVS（自动导引小车系统）柔性问题的研究现状，为了解决AGVS柔性可行性的判断问题，提出了一种处理因生产任务临时调整而引起的AGVS路线调整的可行性判断方法，并给出了该方法可行的严格证明。仿真实验表明，该方法完全可以用于突发情况下AGVS路线调整的可行性判断。同时，该方法能安排尽可能多的突发任

2、务。本文还对该方法的未来研究方向做了展望。该方法具有简单易行、便于操作的特点。关键词：AGVS；柔性可行性；避撞中图分类号：TP301文献标识码：ATheresearchonflexiblefeabilityofAGVSXuCui-xia(DepartmentofComputerTechnology,WeifangUniversity,Shandong261061,China)Abstract:InordertosolvetheevaluationproblemofAGVfeasibility,anewfeasibil

3、ityevaluationapproachwasproposedaccordingtothepresentresearchsituation.ThismethoddealtwiththeproblemofAGVreschedulecausedbyprovisionalchangeofproductiontasks.Theeffectivenessofthismethodwasalsoprovedinthispaper.Simulationresultshowedthatthemethodcanevaluatethere

4、schedulefeasibilityunderprovisionalsituations.Andtheprospectofthismethodwasalsodiscussedinthispaper.Itisprovedthatthemethodisefficientandfeasible.Keywords:AGVS;flexibilityevaluate;conflict-free1引言AGV（自动导引小车）是CIMS（计算机集成制造系统）中物流系统的主要运输工具，以其高柔性、易于控制集成的特点愈来愈受到人们的青睐。

5、AGV一般由柔性的、在线的微机控制，通过自身携带的电池驱动，埋在地板槽内的感应导线构成AGV行驶路线的导引回路。小车能以任何编程速度向前或向后运动。提升AGVS（自动导引小车系统）的性能，可以缩短非加工时间，极大降低生产品成本，是提高CIMS效率的“瓶颈”。2国内外研究现状C.W.Kim等在1991年给出了一种避撞最小时间路径规划法(conflictfreeshortesttimeprocedure，[1])，能够从AGV的当前位置到目的地规划出一条不与其他正在工作AGV相碰撞并且运动时间最短的路径。这个方法的缺点是对

6、AGVS出现的突发情况处理程度不够。Samia等在2001年针对[1]方法提出改进[2]，通过使某辆AGV延迟到达时间，而其他车辆到达下一个指定结点的时候，把当前状态考虑进去重新对系统中每一辆AGV的路径进行避撞最小时间路径规划。但此方法仍有延时现象出现。于是Samia等在2002年提出了一种鲁棒性更强的算法[3]，该算法在[2]的基础上允许部分车辆提前，使系统的延时有所减少。上述文献都注意对突发情况的处理，但就目前文献检索情况看，尚未发现能够在处理突发情况的同时安排尽可能多的突发任务，从而使AGVS的柔性尽可能提高。

7、本文将针对此类问题作初步探讨。3时间窗的定义以及相关概念解释3.1时间窗的形式化定义时间窗的形式化定义最早在[3]中给出，内容如下：将AGV执行某个特定动作所持续的时间结合在一起，构成这个特定动作的时间集合称为时间窗(timewindow)。用于道路连接的部分称为缓冲区。停留在某个缓冲区的时间间隔称为保留时间窗(reservedtimewindow)。AGV从一个缓冲区出发，沿着指定的路径行进到另一个缓冲区，所持续的1http://www.elecfans.com电子发烧友http://bbs.elecfans.com

8、电子技术论坛时间集合称为自由时间窗(freetimewindow)。空间可行性是指在两个结点之间确实存在物理通路，时间可行性是指AGV在即将开始的下一个自由时间窗内，能够进入该时间窗并能按时离开。通过检查空间可行性和时间可行性可以发现潜在的碰撞。3.2通道与柔性可行性通道是指连接两个缓冲区之间的道路。柔性可行性是指在突发情况下AG