Solving The Family Traveling Salesman Problem with Capacitated Agents

Abstract

This thesis leads towards a new approach for the Family Traveling Salesman Problem (FTSP) using as an example a warehouse common problem. The enterprise owner of the warehouse wants to optimize the picking out total distance of the products, taking into account the available logistic resources.

This new extension of the standard FTSP is denoted as Family Traveling Salesman Problem with Capacitated Agents (FTSP-CA). The formulation of the problem is a single objective model, with binary variables. For the computational experimentation two methodologies were applied: Integer programming and Heuristics.

From a set of 21 benchmark FTSP instances, a new group of 36 adapted instances were created that consider the FTSP-CA parameters. For the integer programming technique, the Cplex solver is used to obtain optimal integer solutions. For the second methodology, a Biased Random-Key Genetic Algorithm (BRKGA) was implemented to improve the performance in time and while maintaining a high-quality value of solutions. Both techniques are compared to show the efficiency solving the FTSP-CA.