Exact and matheuristic approaches for the Capacitated Family Traveling Salesman Problem

The Capacitated Family Traveling Salesman Problem (CFTSP) models critical operational decisions in modern warehouse management, particularly in large-scale distribution centers where items are organized into families. This problem requires selecting specific items from each family and assigning them to capacitated pick-up agents while minimizing total travel distance. We propose two novel solution approaches: an exact method based on Constraint Programming (CP) and a matheuristic that hybridizes a bin-packing formulation, which acts as a surrogate model for determining the number of family items assigned to each agent, with a Reactive Greedy Randomized Adaptive Search Procedure incorporating probabilistic stopping criteria. Computational experiments on benchmark instances demonstrate that our CP approach outperforms existing mixed-integer programming formulations, solving 93% of instances compared to 51% for the state-of-the-art method. Our matheuristic achieves superior solution quality, obtaining the best-known solutions for 91% of test instances while maintaining reasonable computational times. These results establish new benchmarks for the CFTSP and provide practical tools for warehouse optimization.