A descent method for the Dubins traveling salesman problem with neighborhoods
| Autor: | Zheng Chen, Chen-hao Sun, Wenjie Zhao, Xueming Shao |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Series (mathematics) Computer Networks and Communications Computer science 02 engineering and technology Travelling salesman problem Set (abstract data type) Core (game theory) 020901 industrial engineering & automation Hardware and Architecture Signal Processing Path (graph theory) 0202 electrical engineering electronic engineering information engineering Bisection method 020201 artificial intelligence & image processing Electrical and Electronic Engineering Focus (optics) Descent (mathematics) |
| Zdroj: | Frontiers of Information Technology & Electronic Engineering. 22:732-740 |
| ISSN: | 2095-9230 2095-9184 |
| DOI: | 10.1631/fitee.2000041 |
| Popis: | In this study, we focus mainly on the problem of finding the minimum-length path through a set of circular regions by a fixed-wing unmanned aerial vehicle. Such a problem is referred to as the Dubins traveling salesman problem with neighborhoods (DTSPN). Algorithms developed in the literature for solving DTSPN either are computationally demanding or generate low-quality solutions. To achieve a better trade-off between solution quality and computational cost, an efficient gradient-free descent method is designed. The core idea of the descent method is to decompose DTSPN into a series of subproblems, each of which consists of finding the minimum-length path of a Dubins vehicle from a configuration to another configuration via an intermediate circular region. By analyzing the geometric properties of the subproblems, we use a bisection method to solve the subproblems. As a result, the descent method can efficiently address DTSPN by successively solving a series of subproblems. Finally, several numerical experiments are carried out to demonstrate the descent method in comparison with several existing algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink