This paper addresses the problem of generating a path for a fleet of robots navigating in a cluttered environment, while maintaining the so called generalized connectivity. The main challenge in the management of a group of robots is to ensure the coordination between them, taking into account limitations in communication range and sensors, possible obstacles, inter-robot avoidance and other constraints. The Generalized Connectivity Maintenance (GCM) theory already provides a way to represent and consider the aforementioned constraints, but previous works only find solutions via locally-steering functions that do not provide global and optimal solutions. In this work, we merge the GCM theory with randomized path-planning approaches, and local path optimization techniques to derive a tool that can provide global, good-quality paths. The proposed approach has been intensively tested and verified by mean of numerical simulations.