Page 178 - Innovations in Intelligent Machines

170 S. Rathinam and R. Sengupta
problems. Even though algorithms with approximation factors are helpful,
there might be simple heuristics that could perform well in practice. The
main difficulty of these routing problems involving UAVs is that there are
no existing methods to calculate the optimal cost. However lower bounds
based on Euclidean distances can be easily derived using the algorithms
presented in this paper. A study comparing the performance of different
heuristics for a given number of depots and destinations would be very
useful.

• Heterogeneous vehicles:
All the problems considered in this chapter assumed a homogeneous collec-
tion of vehicles. Many applications involving UAVs might require vehicles
with different capabilities to act in a cooperative manner. A simple case
would be when the vehicles have a different minimum turning radius. It
is unclear even whether algorithms with approximation factors of 2 are
possible for these problems.

• Adding and deleting destination points:
In military applications, it would be common to have tasks removed or
added as the mission progresses. A simple scenario would be when certain
destination points are deleted or added frequently. A naive approach to
deal with such scenarios would be to recompute solutions whenever the
destinations change. But this might require a large computation time. A
very useful research direction would be to derive algorithms that can adapt
itself to changing scenarios. In particular, the following question is the one
to ask: Can one devise a routing algorithm for all the vehicles that does not
recompute the entire solution from scratch but rather uses old information
in building new solutions?

References
1. Vazirani, V.V., 2001. Approximation algorithms, Springer
2. Papadimitriou, C.H., Steiglitz, K., 1998. Combinatorial optimization: algo-
rithms and complexity, Dover publications
3. Christofides, N., 1976. Worst-case analysis of a new heuristic for the travelling
salesman problem. In: J.F. Traub (Editor), Algorithms and Complexity: New
Directions and Recent Results, Academic Press, pp. 441
4. Arora, S., 1996. Polynomial-time approximation schemes for Euclidean TSP
and other geometric problems. Proceedings of the 37 th Annual Symposium on
the Foundations of Computer Science, pp. 2–11
5. Held, M., Karp, R.M., 1970. The traveling salesman problem and minimum
spanning trees. Operations Research 18, pp. 1138–1162
6. Held, M., Karp, R.M., 1971. The travelling salesman problem and minimum
spanning trees: Part II. Mathematical Programming 18, pp. 6–25
7. Gutin, G., Punnen, A.P. (Editors), 2002. The travelling salesman problem and
its variations. Kluwer Academic Publishers