  In this article, a heuristic is proposed for a min-max heterogeneous
multi-vehicle multi-depot traveling salesman problem (TSP), wherein
heterogeneous vehicles start from given depot positions and need to cover a
given set of targets. The vehicles should cover given targets such that the
maximum tour time is minimized. In the considered problem, vehicles considered
can be functionally heterogeneous, wherein specific targets must be covered by
a particular vehicle, structurally heterogeneous, wherein the vehicles can
travel at different speeds, or both. The proposed heuristic generalizes the MD
heuristic for the min-max homogeneous multi-vehicle multi-depot TSP and has
three stages: an initialization stage to generate a feasible solution, a local
search stage in which the vehicle with the maximum tour time is improved, and a
perturbation stage to break from a local minimum. The proposed heuristic is
benchmarked with the optimal solution obtained by solving a mixed integer
linear program using branch and cut for instances considering three vehicles
covering thirty targets. Variations in the percentage of vehicle-target
assignments and the number of vehicles starting at the same depot are studied
to show the heuristic's effectiveness in producing high-quality solutions. It
was observed that the heuristic generated feasible solutions within 4% of the
optimum on average for the considered instances.
