In this work, we aim to develop task allocation algorithms for routing a collection of heterogeneous UAVs that may travel at different speeds, and carry different sensors. Recently, we have developed a 2-approximation algorithm for a multiple heterogeneous vehicle routing problem based on the primal-dual method. The primal-dual method we adopt is based on the work by Goemans and Williamson for the constrained forest problems.
The following paper discusses our result for a two vehicle problem (the paper for multiple vehicles will be uploaded soon):
Journal Publications
Jungyun Bae and Sivakumar Rathinam, A Primal Dual Algorithm for the Heterogeneous Traveling Salesman Problem, Under review in Optimization Letters. A preliminary version to be presented at the ASME-DSC Conference, 2011. You can download a preliminary version of the paper from arXiv.org (http://arxiv.org/abs/1111.0567). A nice feature of this algorithm is that it scales reasonably well with the number of vehicles. An overview of the algorithm for two vehicles can also be seen here in this presentation. A slightly more technical version of this presentation with equations can be downloaded here.
For a more general heterogeneous vehicle routing problem where the travel costs for the vehicles are unrelated, we have developed some approximation algorithms in the following article. However, the approximation factor depends on the number of vehicles.
Riddhi Doshi, Sai Yadlapalli, Sivakumar Rathinam and Swaroop Darbha, Approximation algorithms and heuristics for a 2-depot, heterogeneous hamiltonian path problem, International Journal of Robust and Nonlinear Control, December 2010. (pdf)
S. Yadlapalli.., S. Rathinam and S. Darbha, 3-Approximation algorithm for a two depot, heterogeneous traveling salesman problem, Optimization Letters, vol. 6, no. 1, pages 141-152, January 2012. (pdf)
K. Sundar and S. Rathinam, A Primal-Dual Heuristic for a Heterogeneous Unmanned Vehicle Path Planning Problem. International Journal of Advanced Robotic Systems, 2013, 10:349. doi: 10.5772/56486 (pdf)
P. Oberlin.., S. Rathinam and S. Darbha, A Transformation for a Heterogenous, Multiple Vehicle, Multiple Travelling Salesman Problem, IEEE Robotics and Automation Magazine, vol. 17, issue 4, pages 70 – 77, 2010. (pdf)
Conference Publications
J. Bae and S. Rathinam, An Approximation Algorithm for a Heterogeneous Traveling Salesman Problem, ASME-Decision, Systems and Controls Conference, 2011.
S. Yadlappalli.., J. Bae, S. Rathinam and S. Darbha, Approximation algorithms for a heterogeneous Multiple Depot Hamiltonian Path Problem, American Control Conference, 2011.
S. Yadlapalli.., S. Rathinam and S. Darbha. An approximation algorithm for a Heterogenous, Multiple Vehicle, Multiple Travelling Salesman Problem. American Control Conference, 2009.
P. Oberlin.., S. Rathinam and S. Darbha. A Transformation for a Heterogenous, Multiple Vehicle, Multiple Travelling Salesman Problem. American Control Conference, 2009.