In this paper, we study the “Multi-Robot Routing problem” with min–max objective (MRR-MM) in detail. It involves the assignment of sequentially ordered tasks to robots such that the maximum cost of the slowest robot is minimized. The problem description, the different types of formulations, and the methods used across various research communities are discussed in this paper. We propose a new problem formulation by treating this problem as a bipartite graph with a permutation matrix to solve it. A comparative study is done between three methods: Stochastic simulated annealing, deterministic mean-field annealing, and a heuristic-based graph search method. Each method is investigated in detail with several data sets (simulation and real-world), and the results are analysed and compared with respect to scalability, computational complexity, optimality, and its application to real-world scenarios. The paper shows that the heuristic method produces results very quickly with good scalability. However, the solution quality is sub-optimal. On the other hand, when optimal or near-optimal results are required with considerable computational resources, the simulated annealing method proves to be more efficient. However, the results show that the optimal choice of algorithm depends on the dataset size and the available computational budget. The contribution of the paper is three-fold: We study the MRR-MM problem in detail across various research communities. This study also shows the lack of inter-research terminology that has led to different names for the same problem. Secondly, formulating the task allocation problem as a permutation matrix formulation (bipartite graph) has opened up new approaches to solve this problem. Thirdly, we applied our problem formulation to three different methods and conducted a detailed comparative study using real-world and simulation data. © 2021 by the authors.


    Access

    Download


    Export, share and cite



    Title :

    Multi-robot routing problem with min-max objective


    Contributors:

    Publication date :

    2021-01-01


    Remarks:

    Scopus 2-s2.0-85119036702



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    511 / 629



    Multi-Objective UAV routing

    Hernandez-Hernandez, Lucia / Tsourdos, Antonios / Shin, Hyo-Sang et al. | IEEE | 2014


    Multi-objective green mixed vehicle routing problem under rough environment

    Joydeep Dutta / Partha Sarathi Barma / Anupam Mukherjee et al. | DOAJ | 2021

    Free access


    Optimization of Vehicle Routing Problem Based on Multi-Objective Genetic Algorithm

    Zhong, R. / Wu, J.P. / Du, Y.M. | British Library Conference Proceedings | 2013