The multi-depot family traveling salesman problem and clustered variants: Mathematical formulations and branch-&-cut based methods

In this article, we study the multi-depot family traveling salesman problem (MDFTSP) and two clustered variants, the soft-clustered MDFTSP (SC-MDFTSP) and the hard-clustered MDFTSP. We emphasize the relevance of this study by relating the problems with warehouse activities supported by scattered storage systems and by pointing out that clustered variants of routing problems have been scarcely addressed in the literature. For these three problems, we present several mixed integer linear programming formulations and develop appropriate branch-&-cut based algorithms which are tested with a newly generated data set including instances with up to 200 nodes and 40 depots. The results from the computational experiments allow us to identify the main differences between the three problems concerning modeling approaches as well as solution methods and put in evidence that these problems are challenging problems, in particular the SC-MDFTSP.

Automated summary

This article focuses on the multi-depot family traveling salesman problem (MDFTSP) and its two clustered variants: the soft-clustered MDFTSP (SC-MDFTSP) and the hard-clustered MDFTSP. The study highlights the relevance of these problems to warehouse activities and points out the lack of discussion on clustered variants of routing problems in the literature. The article presents several mixed integer linear programming formulations and branch-and-cut based algorithms for solving these problems, which are tested on a newly generated dataset. The computational experiments reveal the main differences between the three problems in terms of modeling approaches and solution methods, and demonstrate the challenging nature of the SC-MDFTSP in particular.