Efficient Heuristic Algorithms for Single-Vehicle Task Planning with Precedence Constraints

Xiaoshan Bai, Ming Cao, Weisheng Yan, Shuzhi Sam Ge, Xiaoyu Zhang

科研成果: 期刊稿件文章同行评审

13 引用 (Scopus)

摘要

This article investigates the task planning problem where one vehicle needs to visit a set of target locations while respecting the precedence constraints that specify the sequence orders to visit the targets. The objective is to minimize the vehicle's total travel distance to visit all the targets while satisfying all the precedence constraints. We show that the optimization problem is NP-hard, and consequently, to measure the proximity of a suboptimal solution from the optimal, a lower bound on the optimal solution is constructed based on the graph theory. Then, inspired by the existing topological sorting techniques, a new topological sorting strategy is proposed; in addition, facilitated by the sorting, we propose several heuristic algorithms to solve the task planning problem. The numerical experiments show that the designed algorithms can quickly lead to satisfying solutions and have better performance in comparison with popular genetic algorithms.

源语言英语
页(从-至)6274-6283
页数10
期刊IEEE Transactions on Cybernetics
51
12
DOI
出版状态已出版 - 1 12月 2021

指纹

探究 'Efficient Heuristic Algorithms for Single-Vehicle Task Planning with Precedence Constraints' 的科研主题。它们共同构成独一无二的指纹。

引用此