A Two-Index Formulation for the Fixed-Destination Multi-Depot Asymmetric Travelling Salesman Problem and Some Extensions

Abstract

We introduce a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP). It consists of m salesmen distributed among D depots who depart from and return to their respective origins after visiting a set of customers. The proposed model exploits the multi-depot aspect of the problem by labelling the arcs to identify the nodes that belong to the same tour. Our experimental investigation shows that the proposed-two index formulation is versatile and effective in modelling new variations of the FD-mATSP compared with existing formulations. We demonstrate this by applying it for the solution of two important extensions of the FD-mATSP that arise in logistics and manufacturing environments.