Abstract
Unmanned vehicles, both aerial and ground, are being used in several monitoring applications to collect data from a set of targets. This article addresses a problem where a group of heterogeneous aerial or ground vehicles with different motion constraints located at distinct depots visit a set of targets. The vehicles also may be equipped with different sensors, and therefore, a target may not be visited by any vehicle. The objective is to find an optimal path for each vehicle starting and ending at its respective depot such that each target is visited at least once by some vehicle, the vehicle–target constraints are satisfied, and the sum of the length of the paths for all the vehicles is minimized. Two variants of this problem are formulated (one for ground vehicles and another for aerial vehicles) as mixed-integer linear programs and a branch-and-cut algorithm is developed to compute an optimal solution to each of the variants. Computational results show that optimal solutions for problems involving 100 targets and 5 vehicles can be obtained within 300 seconds on average, further corroborating the effectiveness of the proposed approach.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Frew, E.W., Brown, T.X.: Networking issues for small unmanned aircraft systems. J. Intell. Robot. Syst. 54, 21–37 (2009)
Curry, J.A., Maslanik, J., Holland, G., Pinto, J.: Applications of aerosondes in the arctic. Bull. Amer. Meteorol. Soc. 85(12), 1855–1861 (2004)
Zajkowski, E.J.T., Dunagan S: Small UAS communications mission. In: Eleventh Biennial USDA Forest Service Remote Sensing Applications Conference. Salt Lake City (2006)
Levy, D., Sundar, K., Rathinam, S.: Heuristics for routing heterogeneous unmanned vehicles with fuel constraints. Math. Prob. Eng. (2014)
Sundar, K., Venkatachalam, S., Rathinam, S.: Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem. In: 2016 American Control Conference (ACC), pp. 6489–6494 (2016)
Reeds, J., Shepp, L.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145(2), 367–393 (1990)
Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Amer. J. Math. 79(3), 497–516 (1957)
Benavent, E., Martínez, A.: Multi-depot Multiple TSP: A polyhedral study and computational results. Ann. Oper. Res. 207(1), 7–25 (2013)
Lawler, E.L., Lenstra, J.K., Kan, A.R., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, vol. 3. New York, Wiley (1985)
Sundar, K., Rathinam, S.: Generalized multiple depot traveling salesmen problem–polyhedral study and exact algorithm. Comput. Oper. Res. 70, 39–55 (2016)
Kara, I., Bektas, T.: Integer linear programming formulations of multiple salesman problems and its variations. Eur. J. Oper. Res. 174(3), 1449–1458 (2006)
Bektas, T.: The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega 34(3), 209–219 (2006)
Gavish, B., Srikanth, K.: An optimal solution method for large-scale multiple traveling salesmen problems. Oper. Res. 34(5), 698–717 (1986)
Tang, Z., Ozguner, U.: Motion planning for multitarget surveillance with mobile sensor agents. IEEE Trans. Robot. 21(5), 898–908 (2005)
Rathinam, S., Sengupta, R., Darbha, S.: A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Trans. Autom. Sci. Eng. 4(1), 98–104 (2007)
Savla, K., Frazzoli, E., Bullo, F.: Traveling salesperson problems for the dubins vehicle. IEEE Trans. Autom. Control 53(6), 1378–1391 (2008)
Le Ny, J., Feron, E., Frazzoli, E.: On the dubins traveling salesman problem. IEEE Trans. Autom. Contr. 57(1), 265–270 (2012)
Manyam, S.G., Rathinam, S., Darbha, S.: Computation of lower bounds for a multiple depot, multiple vehicle routing problem with motion constraints. J. Dyn. Syst. Measur. Control 137(9), 094501 (2015)
Manyam, S., Rathinam, S.: On tightly bounding the dubins traveling salesmans optimum. arXiv preprint (2015)
Laporte, G., Nobert, Y., Taillefer, S.: Solving a family of multi-depot vehicle routing and location-routing problems. Transp. Sci. 22(3), 161–172 (1988)
Baldacci, R., Mingozzi, A.: A unified exact method for solving different classes of vehicle routing problems. Mathem. Program. 120(2), 347–380 (2009)
Taillard, É.D.: A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Oper. Res. 33(01), 1–14 (1999)
Baldacci, R., Battarra, M., Vigo, D.: Routing a heterogeneous fleet of vehicles, in The vehicle routing problem: Latest advances and new challenges. Springer, 3–27 (2008)
Nag, B., Golden, B.L., Assad, A.: Vehicle routing with site dependencies. Veh. Rout. Methods Stud., 149–159 (1988)
Chao, I.-M., Golden, B.L., Wasil, E.A.: A new algorithm for the site-dependent vehicle routing problem, in Advances in computational and stochastic optimization, logic programming, and heuristic search. Springer, 301–312 (1998)
Doshi, R., Yadlapalli, S., Rathinam, S., Darbha, S.: Approximation algorithms and heuristics for a 2-depot, heterogeneous hamiltonian path problem. Int. J. Robust Nonlin. Control 21(12), 1434–1451 (2011)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization, vol. 18. Wiley, New York (1988)
Labbé, M., Laporte, G., Martín, I.R., González, J.J.S.: The ring star problem: Polyhedral analysis and exact algorithm. Networks 43(3), 177–189 (2004)
Sussmann, H.J., Tang, G.: Shortest paths for the reeds-shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control. Rutgers Center Syst. Control Tech. Report 10, 1–71 (1991)
Toth, P., Vigo, D.: The Vehicle Routing Problem. Siam (2001)
Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The traveling salesman problem: A computational study. Princeton University Press (2011)
Sundar, K., Rathinam, S.: An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem. In: 2015 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 366–371. IEEE (2015)
Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005)
Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7(1), 67–80 (1982)
Fischetti, M., Salazar Gonzalez, J.J., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45(3), 378–394 (1997)
Sundar, K., Rathinam, S.: Multiple depot ring star problem: A polyhedral study and an exact algorithm. J. Global Optim., 1–25 (2016)
Reinelt, G.: TSPLIB - a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sundar, K., Rathinam, S. Algorithms for Heterogeneous, Multiple Depot, Multiple Unmanned Vehicle Path Planning Problems. J Intell Robot Syst 88, 513–526 (2017). https://doi.org/10.1007/s10846-016-0458-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-016-0458-5