Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm
作者：
Highlights：
• Two approaches to partition a node-weighted graph into q balanced connected parts.
• The first GA for BCPq (q>=2) and it outperforms existing algorithm when q = 2.
• The GA can obtain good near-optimal results after a few individuals were evolved.
• The first mixed integer linear program (MILP), an exact algorithm, for BCPq (q>=2).
• The MILP solves 100 more nodes than existing work within same time limits when q = 2.
摘要
•Two approaches to partition a node-weighted graph into q balanced connected parts.•The first GA for BCPq (q>=2) and it outperforms existing algorithm when q = 2.•The GA can obtain good near-optimal results after a few individuals were evolved.•The first mixed integer linear program (MILP), an exact algorithm, for BCPq (q>=2).•The MILP solves 100 more nodes than existing work within same time limits when q = 2.
论文关键词：Genetic algorithm,Multi-robot system,Balanced connected partition,Mixed integer linear program,Tree partition,Tree evolution
论文评审过程：Received 16 January 2018, Revised 1 September 2018, Accepted 1 September 2018, Available online 3 September 2018, Version of Record 13 September 2018.
论文官网地址：https://doi.org/10.1016/j.eswa.2018.09.001
