Luo Zhihao, Liu Zhong, Shi Jianmai
Science and Technology on Information System Engineering Laboratory, National University of Defense Technology, Changsha 410073, China.
Sensors (Basel). 2017 May 17;17(5):1144. doi: 10.3390/s17051144.
In this paper, a two-echelon cooperated routing problem for the ground vehicle (GV) and its carried unmanned aerial vehicle (UAV) is investigated, where the GV travels on the road network and its UAV travels in areas beyond the road to visit a number of targets unreached by the GV. In contrast to the classical two-echelon routing problem, the UAV has to launch and land on the GV frequently to change or charge its battery while the GV is moving on the road network. A new 0-1 integer programming model is developed to formulate the problem, where the constraints on the spatial and temporal cooperation of GV and UAV routes are included. Two heuristics are proposed to solve the model: the first heuristic (H1) constructs a complete tour for all targets and splits it by GV routes, while the second heuristic (H2) constructs the GV tour and assigns UAV flights to it. Random instances with six different sizes (25-200 targets, 12-80 rendezvous nodes) are used to test the algorithms. Computational results show that H1 performs slightly better than H2, while H2 uses less time and is more stable.
本文研究了地面车辆（GV）及其搭载的无人机（UAV）的两级协同路由问题，其中GV在道路网络上行驶，其UAV在道路以外的区域飞行以访问一些GV无法到达的目标。与经典的两级路由问题不同，当GV在道路网络上行驶时，UAV必须频繁地在GV上起降以更换电池或充电。开发了一种新的0-1整数规划模型来描述该问题，其中包括了GV和UAV路线的空间和时间协同约束。提出了两种启发式算法来求解该模型：第一种启发式算法（H1）为所有目标构建一条完整的路线并按GV路线进行划分，而第二种启发式算法（H2）构建GV路线并为其分配UAV飞行任务。使用具有六种不同规模（25 - 200个目标，12 - 80个会合节点）的随机实例来测试算法。计算结果表明，H1的性能略优于H2，而H2使用的时间更少且更稳定。
