Unmanned aerial vehicles (UAVs) are being widely exploited for various applications, e.g., traversing to collect data from ground sensors, patrolling to monitor key facilities, moving to aid mobile edge computing. We summarize these UAV applications and formulate a problem, namely the general waypoint-based PoI-visiting problem. Since energy is critical due to the limited onboard storage capacity, we aim at minimizing flight energy consumption. In our problem, we pay special attention to the energy consumption for turning and switching operations on flight planning, which are usually ignored in the literature but play an important role in practical UAV flights according to our real-world measurement experiments. We propose specially designed graph parts to model the turning and switching cost and thus transfer the problem into a classic graph problem, i.e., general traveling salesman problem, which can be efficiently solved. Theoretical analysis shows that such problem transformation has the graph redefinition approximation ratio upper bound, $max\lbrace \Theta /\delta ,2\rbrace$, where $\Theta$ is related to the designed graph parts and $\delta$ is a constant. Finally, we evaluate our proposed algorithm by simulations. The results show that it costs less than 107% of the optimal minimum energy consumption for small scale problems and costs only 50% as much energy as a naive algorithm for large scale problems.
Low-altitude airspace in major cities across the world is increasingly congested with uncrewed aerial vehicles (UAVs) and other aircraft. Emerging technologies, innovative business models, and supportive government policies are driving the growth of the low-altitude economy, where UAVs play a crucial role. Given the limited on-board energy of UAVs, this paper investigates the Joint UAV Speed and Altitude Scheduling (JUSAS) problem for data collection from sensors deployed along power transmission lines, bridges, highways, railways, water/gas/oil pipelines, or rivers/coasts. Distinct from existing work, the paper focuses on jointly optimizing UAV speed and altitude scheduling while determining the wireless sensor collection order. It accounts for the altitude-specific sensor transmission range model and the complexities of overlapping range relationships. We first propose the Slowest Segment First (SSF) policy to obtain an optimal UAV speed scheduling for fixed-altitude scenarios. Building upon this, we then reformulate JUSAS as a shortest-path-type problem using our novel flight scheduling graph, solved efficiently through the SSF-based Ant Colony Optimization (SSF-ACO) algorithm. To handle practical scenarios without prior sensor information along the path, we develop SSF-ACO-Online for real-time scheduling. Extensive simulations demonstrate that SSF-ACO significantly outperforms four other algorithms (i.e., SSF-Only, SSF-GA, SSF-PSO, and SSF-SA) in energy efficiency, and reduces 13.11% energy consumption on average. SSF-ACO-Online achieves comparable performance with energy consumption 1.24% higher than offline counterpart in average.