机器人室内自主载人自适应性匈牙利派单算法
2023,31(10):200-207
摘要：以航站楼等大型公共室内环境中机器人运送旅客为背景，研究多自主载人机器人的派单优化问题。借鉴了网约车的派单思想，针对航站楼隔离区环境内的搭乘需求，研究了自适应性匈牙利派单算法。首先，基于航站楼二分图派单匹配模型，计算载人机器人的派单调度矩阵。其次，该派单调度矩阵考虑了旅客密度时空分布、旅客等待时间和机器人能耗为参考，将路径-时间-能量作为目标变量，以计算各接载任务起讫（OD）矩阵元素值，同时为挖掘全域派单的可能性，结合供需预测关系将快到达目标点的载人机器人加入可派单队列。最后，构建航站楼实际动态业务的三维仿真模型，进行了全天时派单模拟实验。结果表明，所研究的派单算法对多目标约束派单求解有较好的优越性和适应性，以达到全域最优派单分配的目的，为高效完成接载任务提供其决策支持。
关键词：网约车；二分图派单匹配；接载任务OD矩阵；供需预测关系；连环派单；自适应性匈牙利算法
Robot indoor autonomous manned adaptive Hungarian dispatch algorithm
Abstract：Based on the background of robot transporting passengers in large public indoor environments such as terminal buildings, the problem of dispatching order optimization of multi-autonomous manned robots is studied. Based on the idea of dispatching the network car, the adaptive Hungarian dispatching algorithm is studied for the ride demand in the terminal isolation area. Firstly, the dispatch scheduling matrix of manned robot is calculated based on the dispatch matching model of terminal bipartite graph. Secondly, the dispatch matrix considers the spatial and temporal distribution of passenger density, passenger waiting time and robot energy consumption as reference, and takes the path-time-energy as the target variable to calculate the OD matrix element value of each receiving task. At the same time, in order to explore the possibility of global dispatch, combined with the supply and demand prediction relationship, the manned robot that quickly reaches the target point is added to the dispatchable single queue. Finally, the three-dimensional simulation model of the actual dynamic business of the terminal is constructed, and the all-day dispatch simulation experiment is carried out. The results show that the proposed dispatch algorithm has better superiority and adaptability to multi-objective constrained dispatch, so as to achieve the purpose of global optimal dispatch allocation and provide decision support for efficient completion of the receiving task.
Key words：Network car; bipartite graph assignment matching; loading task OD matrix; supply and demand forecasting relationship; serial dispatch; adaptive Hungarian algorithm
收稿日期：2023-01-15
基金项目：国家自然科学基金(U1533203)
