We consider multi-depot multiple asymmetric traveling salesmen problem (MmATSP) where each tour starts and ends at the same depot. The problem can be modeled in several ways with different variables. We analyze strengths and limitations of the compact linear integer formulations: the corresponding linear programming relaxations are compared and their non-dominant relations are explained by deriving additional valid inequalities. Also, we propose novel constraints to formulate the depot fixing feature (sometimes referred as path elimination constraints) and consequently novel formulations. Another particular feature we study is lower and upper bound restrictions on the number of nodes visited in a tour. Our results can be directly applied to relevant multi-depot vehicle routing problems as well.
| Subject : | : | Abstracts |
| Topics | : | Exact Methods |
| Topics | : | TSP Variants |
| PDF version | : |  PDF version |
