IEEE Robotics & Automation Magazine - December 2010 - 70
Heterogeneous, Multiple
Depot, Multiple UAV
Routing Problem
BY PAUL OBERLIN,
SIVAKUMAR RATHINAM,
AND SWAROOP DARBHA
© LUSHPIX
H
eterogeneous unmanned aerial vehicles (UAVs) are being developed for several civil
and military applications. These vehicles can differ either in their motion constraints or
sensing/attack capabilities. This article uses methods from operations research to
address a fundamental routing problem involving heterogeneous UAVs. The approach is to transform the routing problem into a relatively better understood single,
asymmetric, traveling salesman problem (ATSP) and use the algorithms available for the ATSP to
address the routing problem. To test the effectiveness of the transformation, the well-known
Lin-Kernighan-Helsgaun heuristic was applied to the transformed ATSP. Computational results
on the transformed ATSP show that solutions whose costs are within 16% of the optimum can
be obtained relatively fast [within 40 s of central processing unit (CPU)] for the routing problem
involving ten heterogeneous UAVs and 40 targets.
UAVs are being developed for several civil and military applications for surveillance purposes.
In these applications, multiple heterogeneous UAVs with different sensing capabilities can be
used to accomplish a given mission. Apart from their differing sensing capabilities, the UAVs can
also have different motion constraints. A commonly encountered mission that is required to be
carried out by a team of heterogeneous UAVs is an intelligence, surveillance, and reconnaissance
mission where a set of targets needs to be monitored. For example, in the Cooperative Operations in Urban Terrain project [1] at the Air Force Research Laboratory, a collection of UAVs is
required to gather information/video about a set of potential targets and transmit them to an
Digital Object Identifier 10.1109/MRA.2010.938844
70
IEEE Robotics & Automation Magazine
1070-9932/10/$26.00ª2010 IEEE
DECEMBER 2010
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2010
IEEE Robotics & Automation Magazine - December 2010 - Cover1
IEEE Robotics & Automation Magazine - December 2010 - Cover2
IEEE Robotics & Automation Magazine - December 2010 - 1
IEEE Robotics & Automation Magazine - December 2010 - 2
IEEE Robotics & Automation Magazine - December 2010 - 3
IEEE Robotics & Automation Magazine - December 2010 - 4
IEEE Robotics & Automation Magazine - December 2010 - 5
IEEE Robotics & Automation Magazine - December 2010 - 6
IEEE Robotics & Automation Magazine - December 2010 - 7
IEEE Robotics & Automation Magazine - December 2010 - 8
IEEE Robotics & Automation Magazine - December 2010 - 9
IEEE Robotics & Automation Magazine - December 2010 - 10
IEEE Robotics & Automation Magazine - December 2010 - 11
IEEE Robotics & Automation Magazine - December 2010 - 12
IEEE Robotics & Automation Magazine - December 2010 - 13
IEEE Robotics & Automation Magazine - December 2010 - 14
IEEE Robotics & Automation Magazine - December 2010 - 15
IEEE Robotics & Automation Magazine - December 2010 - 16
IEEE Robotics & Automation Magazine - December 2010 - 17
IEEE Robotics & Automation Magazine - December 2010 - 18
IEEE Robotics & Automation Magazine - December 2010 - 19
IEEE Robotics & Automation Magazine - December 2010 - 20
IEEE Robotics & Automation Magazine - December 2010 - 21
IEEE Robotics & Automation Magazine - December 2010 - 22
IEEE Robotics & Automation Magazine - December 2010 - 23
IEEE Robotics & Automation Magazine - December 2010 - 24
IEEE Robotics & Automation Magazine - December 2010 - 25
IEEE Robotics & Automation Magazine - December 2010 - 26
IEEE Robotics & Automation Magazine - December 2010 - 27
IEEE Robotics & Automation Magazine - December 2010 - 28
IEEE Robotics & Automation Magazine - December 2010 - 29
IEEE Robotics & Automation Magazine - December 2010 - 30
IEEE Robotics & Automation Magazine - December 2010 - 31
IEEE Robotics & Automation Magazine - December 2010 - 32
IEEE Robotics & Automation Magazine - December 2010 - 33
IEEE Robotics & Automation Magazine - December 2010 - 34
IEEE Robotics & Automation Magazine - December 2010 - 35
IEEE Robotics & Automation Magazine - December 2010 - 36
IEEE Robotics & Automation Magazine - December 2010 - 37
IEEE Robotics & Automation Magazine - December 2010 - 38
IEEE Robotics & Automation Magazine - December 2010 - 39
IEEE Robotics & Automation Magazine - December 2010 - 40
IEEE Robotics & Automation Magazine - December 2010 - 41
IEEE Robotics & Automation Magazine - December 2010 - 42
IEEE Robotics & Automation Magazine - December 2010 - 43
IEEE Robotics & Automation Magazine - December 2010 - 44
IEEE Robotics & Automation Magazine - December 2010 - 45
IEEE Robotics & Automation Magazine - December 2010 - 46
IEEE Robotics & Automation Magazine - December 2010 - 47
IEEE Robotics & Automation Magazine - December 2010 - 48
IEEE Robotics & Automation Magazine - December 2010 - 49
IEEE Robotics & Automation Magazine - December 2010 - 50
IEEE Robotics & Automation Magazine - December 2010 - 51
IEEE Robotics & Automation Magazine - December 2010 - 52
IEEE Robotics & Automation Magazine - December 2010 - 53
IEEE Robotics & Automation Magazine - December 2010 - 54
IEEE Robotics & Automation Magazine - December 2010 - 55
IEEE Robotics & Automation Magazine - December 2010 - 56
IEEE Robotics & Automation Magazine - December 2010 - 57
IEEE Robotics & Automation Magazine - December 2010 - 58
IEEE Robotics & Automation Magazine - December 2010 - 59
IEEE Robotics & Automation Magazine - December 2010 - 60
IEEE Robotics & Automation Magazine - December 2010 - 61
IEEE Robotics & Automation Magazine - December 2010 - 62
IEEE Robotics & Automation Magazine - December 2010 - 63
IEEE Robotics & Automation Magazine - December 2010 - 64
IEEE Robotics & Automation Magazine - December 2010 - 65
IEEE Robotics & Automation Magazine - December 2010 - 66
IEEE Robotics & Automation Magazine - December 2010 - 67
IEEE Robotics & Automation Magazine - December 2010 - 68
IEEE Robotics & Automation Magazine - December 2010 - 69
IEEE Robotics & Automation Magazine - December 2010 - 70
IEEE Robotics & Automation Magazine - December 2010 - 71
IEEE Robotics & Automation Magazine - December 2010 - 72
IEEE Robotics & Automation Magazine - December 2010 - 73
IEEE Robotics & Automation Magazine - December 2010 - 74
IEEE Robotics & Automation Magazine - December 2010 - 75
IEEE Robotics & Automation Magazine - December 2010 - 76
IEEE Robotics & Automation Magazine - December 2010 - 77
IEEE Robotics & Automation Magazine - December 2010 - 78
IEEE Robotics & Automation Magazine - December 2010 - 79
IEEE Robotics & Automation Magazine - December 2010 - 80
IEEE Robotics & Automation Magazine - December 2010 - 81
IEEE Robotics & Automation Magazine - December 2010 - 82
IEEE Robotics & Automation Magazine - December 2010 - 83
IEEE Robotics & Automation Magazine - December 2010 - 84
IEEE Robotics & Automation Magazine - December 2010 - 85
IEEE Robotics & Automation Magazine - December 2010 - 86
IEEE Robotics & Automation Magazine - December 2010 - 87
IEEE Robotics & Automation Magazine - December 2010 - 88
IEEE Robotics & Automation Magazine - December 2010 - 89
IEEE Robotics & Automation Magazine - December 2010 - 90
IEEE Robotics & Automation Magazine - December 2010 - 91
IEEE Robotics & Automation Magazine - December 2010 - 92
IEEE Robotics & Automation Magazine - December 2010 - 93
IEEE Robotics & Automation Magazine - December 2010 - 94
IEEE Robotics & Automation Magazine - December 2010 - 95
IEEE Robotics & Automation Magazine - December 2010 - 96
IEEE Robotics & Automation Magazine - December 2010 - 97
IEEE Robotics & Automation Magazine - December 2010 - 98
IEEE Robotics & Automation Magazine - December 2010 - 99
IEEE Robotics & Automation Magazine - December 2010 - 100
IEEE Robotics & Automation Magazine - December 2010 - 101
IEEE Robotics & Automation Magazine - December 2010 - 102
IEEE Robotics & Automation Magazine - December 2010 - 103
IEEE Robotics & Automation Magazine - December 2010 - 104
IEEE Robotics & Automation Magazine - December 2010 - 105
IEEE Robotics & Automation Magazine - December 2010 - 106
IEEE Robotics & Automation Magazine - December 2010 - 107
IEEE Robotics & Automation Magazine - December 2010 - 108
IEEE Robotics & Automation Magazine - December 2010 - 109
IEEE Robotics & Automation Magazine - December 2010 - 110
IEEE Robotics & Automation Magazine - December 2010 - 111
IEEE Robotics & Automation Magazine - December 2010 - 112
IEEE Robotics & Automation Magazine - December 2010 - 113
IEEE Robotics & Automation Magazine - December 2010 - 114
IEEE Robotics & Automation Magazine - December 2010 - 115
IEEE Robotics & Automation Magazine - December 2010 - 116
IEEE Robotics & Automation Magazine - December 2010 - 117
IEEE Robotics & Automation Magazine - December 2010 - 118
IEEE Robotics & Automation Magazine - December 2010 - 119
IEEE Robotics & Automation Magazine - December 2010 - 120
IEEE Robotics & Automation Magazine - December 2010 - Cover3
IEEE Robotics & Automation Magazine - December 2010 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2010
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2010
https://www.nxtbookmedia.com