Dynamic region visit routing problem for vehicles with minimum turning radius

Douglas G. Macharet (), Armando Alves Neto (), Vila F. Camara Neto () and Mario F. M. Campos ()
Additional contact information
Douglas G. Macharet: Universidade Federal de Minas Gerais
Armando Alves Neto: Universidade Federal de Minas Gerais
Vila F. Camara Neto: Fundação Centro de Análise, Pesquisa e Inovação Tecnológica
Mario F. M. Campos: Universidade Federal de Minas Gerais

Journal of Heuristics, 2018, vol. 24, issue 1, No 4, 83-109

Abstract: Abstract In this paper we address the problem of planning optimized routes among dynamically selected target regions for vehicles with a turning radius motion constraint, hereinafter called dynamic Dubins traveling salesman problem with neighborhoods (DDTSPN). Initially, we present a heuristic to solve a simpler version of this problem, called off-line step, where only previously given targets are concerned. We further extend this approach for the more complex case of dynamic scenarios, called on-line step, addressing the inclusion of new targets during the execution of the initial route, whilst minimizing the impact on the total traveled distance. Formal analyzes of our techniques are provided, presenting upper bounds for the total length of the final tour. Results with statistical investigation over a large number of trials in a simulated environment are also provided. Finally, to demonstrate the applicability of our technique in solving the DDTSPN at real-world scenarios, we also report on results of an experiment performed with a real car-like robot.

Keywords: Dynamic vehicle routing problem; Dubins vehicle; Traveling salesman problem with neighborhoods (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9359-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:24:y:2018:i:1:d:10.1007_s10732-017-9359-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-017-9359-4

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().