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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Multi-robot routing problem with min-max objective


    Beteiligte:

    Erscheinungsdatum :

    2021-01-01


    Anmerkungen:

    Scopus 2-s2.0-85119036702



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    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

    Freier Zugriff


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

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