Problem REF  is closely related to the well-known traveling salesman problem (TSP) [1]} but with three distinctions: the set of waypoints to be visited is to be determined by the solution; there is no need to return to the starting waypoint; and the cost is defined as the total waiting time over each waypoint instead of the total travel distance.
The above problem is NP-hard [2]} as it contains the TSP as a special case.
A similar formulation appears in the computer wiring problem as discussed in [1]}.
To find the exact solution to Problem REF , we can transform it into a generalized TSP.
In particular, let \(\mathcal {N}_{j,+}^{f}= \mathcal {N}_j^f\cup \lbrace j\rbrace \cup \lbrace \nu \rbrace \) , where \(\mathcal {N}_j^f\)  is the set of source neighbors that robot \(j\)  is connected to and \(\nu \)  is an artificial node.
Recall that the requests \(\textbf {Req}_{ij}(0)=(\Gamma _{i,s_if_i},\,T_{i,s_if_i})\)  satisfy \(\Gamma _{i,s_if_i}=m_{i,s_i}m_{i,s_i+1}\cdots m_{i,f_i}\)  and \(T_{i,s_if_i}=t_{i,s_i}t_{i,s_i+1}\cdots t_{i,f_i}\) .
For ease of notation, let \(\mathcal {I}_{i}^{sf}\triangleq \lbrace s_i,s_i+1,\cdots ,f_i\rbrace \) .
