We generate time-optimal velocity profiles for a group of path-constrained vehicles with fixed and known initial and goal locations. Each vehicle robot must follow a fixed path, arrive at its goal as quickly as possible (or at least not increase the time for the last robot to arrive at its goal) and stay in communication with other robots in the arena throughout its journey. We seek to solve this multi-objective optimization problem by generating optimal velocities along the paths. The problem is formulated as a nonlinear programming problem (NLP) with constraints on the kinematics, dynamics, collision avoidance and communication. Solutions demonstrate the trade off between the arrival time, the required transmission power and the communication connectivity requirements. Typically the optimization improved connectivity at no appreciable cost in journey time (as measured by the time of arrival of the last-arriving robot).