In this paper, we consider the problem of routing multiple robots to service spatially distributed requests at specified time instants. We show that such a routing problem can be formulated as a pure assignment problem. Additionally, we incorporate connectivity constraints into the problem by requiring that range-constrained robots ensure a connected information exchange network at all times. We discuss the feasibility aspects of such a spatio-temporal routing problem, and derive the minimum number of robots required to service the requests. Moreover, we explicitly construct the corresponding routes for the robots, with the total length traveled as the cost to be minimized. (C) 2015 Elsevier Ltd. All rights reserved,