Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks

Doo-Hyun Cho, Dae-Sung Jang and Han-Lim Choi

International Journal of Systems Science, 2020, vol. 51, issue 4, 608-630

Abstract: This paper formalises path planning problem for a group of heterogeneous Dubins vehicles performing tasks in a remote fashion and develops a memetic algorithm-based method to effectively produce the paths. In the setting, the vehicles are initially located at multiple depots in a two-dimensional space and the objective of planning is to minimise a weighted sum of the total tour cost of the group and the largest individual tour cost amongst the vehicles. While the presented formulation takes the form of a mixed-integer linear programme (MILP) for which off-the-shelf solvers are available, the MILP solver easily loses the tractability as the number of tasks and agents grow. Therefore, a memetic algorithm tailored to the presented formulation is proposed. The algorithm features a sophisticated encoding scheme to efficiently select the order of performing tasks. In addition, a path refinement technique that optimises detailed tours with the sequence of visits fixed is proposed to finally obtain further optimised trajectories. Comparative numerical experiments show the validity and efficiency of the proposed methods compared with the previous methods in the literature.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721.2020.1737263 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tsysxx:v:51:y:2020:i:4:p:608-630

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207721.2020.1737263

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().