JRM Vol.35 No.2 pp. 271-278
doi: 10.20965/jrm.2023.p0271


Optimization of Drone-Based Surface-Wave Seismic Surveys Using a Multiple Traveling Salesman Problem

Yohei Hamasato*, Akinori Sakaguchi** ORCID Icon, Takeshi Tsuji*** ORCID Icon, and Kaoru Yamamoto* ORCID Icon

*Graduate School and Faculty of Information Science and Electrical Engineering, Kyushu University
744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan

**Research Institute of Advanced Electric Propulsion Aircrafts, Kyushu University
744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan

***Department of Systems Innovation, Graduate School of Engineering, The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

October 30, 2022
December 27, 2022
April 20, 2023
multi-drone routing, drone applications in seismic survey, multiple traveling salesman problem, fuzzy c-means clustering

In this study, we investigate the problem of finding energy-efficient routes for multiple drones conducting a surface-wave seismic survey. The survey utilizes one seismic source and multiple measurement points spread over a designated area. Each drone carries a seismometer, and is tasked with visiting pre-specified points to take measurements of seismic signals by resting idle on the ground for a set time. Due to this mandatory idling time, their energy consumption is not proportional to the flight distance, nor it is possible to apply standard path minimization algorithms. To address this issue, we establish an energy consumption model for each drone and propose algorithms to optimally allocate points to each drone and generate routes that minimize total energy consumption. The validity of these algorithms is discussed using numerical simulations.

Automated seismic survey using drones

Automated seismic survey using drones

Cite this article as:
Y. Hamasato, A. Sakaguchi, T. Tsuji, and K. Yamamoto, “Optimization of Drone-Based Surface-Wave Seismic Surveys Using a Multiple Traveling Salesman Problem,” J. Robot. Mechatron., Vol.35 No.2, pp. 271-278, 2023.
Data files:
  1. [1] T. Ikeda, T. Tsuji, M. Nakatsukasa, H. Ban, A. Kato, K. Worth, D. White, and B. Roberts, “Imaging and monitoring of the shallow subsurface using spatially windowed surface-wave analysis with a single permanent seismic source,” Geophys., Vol.83, No.6, pp. EN23-EN38, 2018.
  2. [2] T. Tsuji, J. Kinoshita, S. Tsuji, K. Yamamoto, and T. Ikeda, “Drone-based active-source multichannel seismic survey system,” Summit on Drone Geophysics, 2021.
  3. [3] T. Tsuji, S. Tsuji, J. Kinoshita, T. Ikeda, and A. Ahmad, “4 cm Portable Active Seismic Source (PASS) for Meter-to Kilometer-Scale Imaging and Monitoring of Subsurface Structures,” Seismol. Res. Lett., 2022.
  4. [4] S. Anily and G. Mosheiov, “The traveling salesman problem with delivery and backhauls,” Oper. Res. Lett., Vol.16, No.1, pp. 11-18, 1994.
  5. [5] H. Jin, Q. He, M. He, F. Hu, and S. Lu, “New method of path optimization for medical logistics robots,” J. Robot. Mechatron., Vol.33, No.4. pp. 944-954, 2021.
  6. [6] S. Cavani, M. Iori, and R. Roberti, “Exact methods for the traveling salesman problem with multiple drones,” Transp. Res. Part C: Emerg. Technol., Vol.130, Article No.103280, 2021.
  7. [7] S. Kim and I. Moon, “Traveling salesman problem with a drone station,” IEEE Trans. Syst., Man, Cybernet.: Syst., Vol.49, No.1, pp. 42-52, 2018.
  8. [8] Y. Hamasato, A. Sakaguchi, K. Yamamoto, and T. Tsuji, “Multiple drone route optimization for a seismic survey,” Trans. Inst. Syst., Control Inf. Eng., 2023 (in press) (in Japanese).
  9. [9] H. Watanabe, T. Ono, A. Matsunaga, and A. Kanagawa, “Multiple traveling salesman problems using the fuzzy c-means clustering,” J. Japan Soc. Fuzzy Theory Syst., Vol.13, No.2, pp. 119-126, 2001 (in Japanese).
  10. [10] J. Bezdek, “Pattern recognition with fuzzy objective function algorithms,” Plenum Press, 1981.
  11. [11] T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega, Vol.34, No.3, pp. 209-219, 2006.
  12. [12] K. Bérczi, M. Mnich, and R. Vincze, “Approximations for Many-Visits Multiple Traveling Salesman Problems,” Omega, Article No.102816, 2022.
  13. [13] O. Cheikhrouhou and I. Khoufi, “A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy,” Comput. Sci. Rev., Vol.40, Article No.100369, 2021.
  14. [14] R. Alyassi, M. Khonji, A. Karapetyan, S. Chau, K. Elbassioni, and C. Tseng, “Autonomous recharging and flight mission planning for battery-operated autonomous drones,” IEEE Trans. Autom. Sci. Eng., 2022.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Jul. 12, 2024