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 , where only previously given targets are concerned. We further extend this approach for the more complex case of dynamic scenarios, called , 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. |
Year | DOI | Venue |
---|---|---|
2018 | https://doi.org/10.1007/s10732-017-9359-4 | J. Heuristics |
Keywords | Field | DocType |
Dynamic vehicle routing problem,Dubins vehicle,Traveling salesman problem with neighborhoods | Traveling purchaser problem,Heuristic,Mathematical optimization,Travelling salesman problem,Turning radius,2-opt,Robot,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 1 | 1381-1231 |
Citations | PageRank | References |
0 | 0.34 | 24 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Douglas Guimarães Macharet | 1 | 49 | 9.22 |
Armando Alves Neto | 2 | 61 | 11.32 |
Vilar Fiuza da Camara Neto | 3 | 31 | 3.94 |
Mario Fernando Montenegro Campos | 4 | 557 | 51.60 |