论文部分内容阅读
本文依托北京某地下无人泊车停车场,主要研究了AGV泊车的路径规划和动态调度问题。本文的室内智能无人泊车系统,其设计目标在于改造现有停车场,而不是构建新的停车场,满足提高停车场的利用率(较大增容率)和用户体验(较少存取车时间)这两个指标。因此,对实时路径规划和动态任务调度提出了较高的要求。目前,国内一些企业也开始积极开发AGV智能泊车业务。其停车场路线多为环形回路,尽管路径规划与任务调度算法简单,容易操作,但是AGV只能单向环路行驶,既不利于提高增容率,满足运营商的利益要求,也不能减少用户的存取车时间。因此,在满足最大增容率的情况下(即没有环形路线且AGV可双向行驶),本文提出了新的路径规划时间模型,同时采用静态与动态相结合的路径规划算法进行实时路径规划,解决多AGV相遇死锁的难题。针对本课题,基于分布式约束优化问题模型(DCOP),建立了新的任务分配模型,使用基于FRODO框架的DPOP算法进行优化求解。本文的主要研究内容如下:(1)对AGV无人泊车系统的关键问题进行了详细分析,并构建了AGV系统中路径规划和任务分配两个问题的数学模型,其优化目标分别为最少AGV行驶时间和最小滞后惩罚成本,同时建立了停车场的拓扑电子地图模型,为后续的计算提供了计算基础;(2)提出了一种改进的Dijkstra路径规划算法,用于求解静态AGV最短路径,即原始最优路径。本文中的停车场路线规整,但节点数较多,因此采用关键节点法禁忌表减少实际计算节点。该方法与数据库相连接,得出完整的最优路径。通过与A*算法和Dijkstra算法的比较,增加的禁忌表可以将原来的无关节点屏蔽,并不会减少路径搜索的有效域。虽然路径的搜索结果相同,但改进算法的效率更高;(3)分别用两种方法对AGV的任务分配进行建模求解。第一种是集中的任务调度模型,用带ATC rule的过滤搜索法与模拟退火相结合的改进算法求解。第二种是运用约束优化问题建模,并使用基于FRODO框架的DPOP算法求解。通过实例进行比较,实验表明本文提出的改进算法ATCSA在初始解和最优解质量比约束优化更优;(4)本文结合理论研究算法,对AGV调度系统进行了仿真系统的设计。基于前面的理论研究,本文使用C++builder XE实现了AGV管控仿真系统,重点介绍了系统的功能模块和数据库设计。