  The generalized multiple depot traveling salesmen problem (GMDTSP) is a
variant of the multiple depot traveling salesmen problem (MDTSP), where each
salesman starts at a distinct depot, the targets are partitioned into clusters
and at least one target in each cluster is visited by some salesman. The GMDTSP
is an NP-hard problem as it generalizes the MDTSP and has practical
applications in design of ring networks, vehicle routing, flexible
manufacturing scheduling and postal routing. We present an integer programming
formulation for the GMDTSP and valid inequalities to strengthen the linear
programming relaxation. Furthermore, we present a polyhedral analysis of the
convex hull of feasible solutions to the GMDTSP and derive facet-defining
inequalities that strengthen the linear programming relaxation of the GMDTSP.
All these results are then used to develop a branch-and-cut algorithm to obtain
optimal solutions to the problem. The performance of the algorithm is evaluated
through extensive computational experiments on several benchmark instances.
