Unmanned aerial vehicles are being used in several monitoring applications to collect data from a set of targets. These vehicles are heterogeneous in the sense that they can differ either in their motion constraints or sensing capabilities. Furthermore, not all vehicles may be able to visit a given target because vehicles may occasionally be equipped with disparate sensors due to the respective payload restrictions. This article addresses a problem where a group of heterogeneous vehicles located at distinct depots visit a set of targets. The targets are partitioned into disjoint subsets: targets to be visited by specific vehicles and targets that any of the vehicles can visit. The objective is to find an optimal tour for each vehicle starting at its respective depot such that each target is visited at least once by some vehicle, the vehicle-target constraints are satisfied and the sum of the costs of the tours for all the vehicles is minimized. We formulate the problem as a mixed-integer linear program and develop a branch-and-cut algorithm to compute an optimal solution to the problem. Computational results show that optimal solutions for problems involving 100 targets and 5 vehicles can be obtained within 300 seconds on average, further corroborating the effectiveness of the proposed approach.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem


    Beteiligte:


    Erscheinungsdatum :

    2015-06-01


    Format / Umfang :

    272626 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Heuristic for Min-Max Heterogeneous Multi-Vehicle Multi-Depot Traveling Salesman Problem

    Kumar, Deepak Prakash / Rathinam, Sivakumar / Darbha, Swaroop et al. | AIAA | 2024




    Exact methods for the traveling salesman problem with multiple drones

    Cavani, Sara / Iori, Manuel / Roberti, Roberto | Elsevier | 2021


    2012-2563 A Binary Programming Solution to the Multiple-Depot, Multiple Traveling Salesman Problem with Constant Profits

    Kivelevitch, E. / Cohen, K. / Kumar, M. et al. | British Library Conference Proceedings | 2012