Department of Mechanical Engineering-Engineering Mechanics, Michigan Technological University, Houghton, MI 49931, USA.
Department of Applied Computing, Michigan Technological University, Houghton, MI 49931, USA.
Sensors (Basel). 2022 Jul 28;22(15):5637. doi: 10.3390/s22155637.
This paper proposes an algorithm that provides operational strategies for multiple heterogeneous mobile robot systems utilized in many real-world applications, such as deliveries, surveillance, search and rescue, monitoring, and transportation. Specifically, the authors focus on developing an algorithm that solves a min-max multiple depot heterogeneous asymmetric traveling salesperson problem (MDHATSP). The algorithm is designed based on a primal-dual technique to operate given multiple heterogeneous robots located at distinctive depots by finding a tour for each robot such that all the given targets are visited by at least one robot while minimizing the last task completion time. Building on existing work, the newly developed algorithm can solve more generalized problems, including asymmetric cost problems with a min-max objective. Though producing optimal solutions requires high computational loads, the authors aim to find reasonable sub-optimal solutions within a short computation time. The algorithm was repeatedly tested in a simulation with varying problem sizes to verify its effectiveness. The computational results show that the algorithm can produce reliable solutions to apply in real-time operations within a reasonable time.
本文提出了一种算法，为在许多实际应用中使用的多个异构移动机器人系统提供操作策略，例如交付、监控、搜索和救援、监测和运输。具体来说，作者专注于开发一种算法来解决最小最大多库异构不对称旅行商问题 (MDHATSP)。该算法基于主对偶技术设计，通过为位于不同仓库的给定多个异构机器人找到一条巡回路线来操作这些机器人，使得至少有一个机器人访问所有给定的目标，同时最小化最后一个任务的完成时间。在现有工作的基础上，新开发的算法可以解决更一般的问题，包括具有最小最大目标的不对称成本问题。虽然生成最优解需要很高的计算负载，但作者旨在在短时间内找到合理的次优解。该算法在具有不同问题规模的模拟中反复进行测试，以验证其有效性。计算结果表明，该算法可以在合理的时间内生成可靠的解决方案，以便在实时操作中应用。
