  This paper formalizes path planning problem for a group of heterogeneous
Dubins vehicles performing tasks in a remote fashion and develops a memetic
algorithm-based method to effectively produce the paths. In the setting, the
vehicles are initially located at multiple depots in a two-dimensional space
and the objective of planning is to minimize a weighted sum of the total tour
cost of the group and the largest individual tour cost amongst the vehicles.
While the presented formulation takes the form of a mixed-integer linear
program (MILP) for which off-the-shelf solvers are available, the MILP solver
easily loses the tractability as the number of tasks and agents grow.
Therefore, a memetic algorithm tailored to the presented formulation is
proposed. The algorithm features a sophisticated encoding scheme to
efficiently. In addition, a path refinement technique that optimizes on the
detailed tours with the sequence of visits fixed is proposed to finally obtain
further optimized trajectories. Comparative numerical experiments show the
validity and efficiency of the proposed methods compared with the previous
methods in the literature.

Multiagent Systems