A survey on routing problems and robotic systems. Issue 12 (6th August 2018)

• Record Type: Journal Article
• Authors: Macharet, Douglas G.; Campos, Mario F. M.
• Is Part Of: Robotica. Volume 36:Issue 12(2018)
• Page Start: 1781
• Page End: 1803
• Publication Date: 2018-08-06
• Subjects: Traveling Salesman Problem, -- Vehicle Routing Problem, -- Dubins vehicle, -- Dubins TSP, -- TSP with neighborhoods, -- k-TSP, -- Dynamic VRP; Robots -- Periodicals; 629.89205
• DOI: 10.1017/S0263574718000735
• Languages: English
• ISSNs: 0263-5747

Abstract

SUMMARY: Planning paths that are length or time optimized or both is an age-long problem for which numerous approaches have been proposed with varied degree of success depending on the imposed constraints. Among classical instances in the literature, the Traveling Salesman Problem and the Vehicle Routing Problem have been widely studied and frequently considered in the realm of mobile robotics. Understandably, the classical formulation for such problems do not take into account many different issues that arise in real-world scenarios, such as motion constraints and dynamic environments, commonly found in actual robotic systems, and consequently the solutions have been generalized in several ways. In this work, we present a broad and comprehensive review of the classical works and recent breakthroughs regarding the routing techniques ordinarily used in robotic systems and provide references to the most fundamental works in the literature.