Reference:
M. Burger,
Z. Su, and
B. De Schutter,
"A node current-based 2-index formulation for the fixed-destination
multi-depot travelling salesman problem," European Journal of
Operational Research, vol. 265, no. 2, pp. 463-477, Mar. 2018.
Abstract:
The travelling salesman problem forms a basis for many optimisation
problems in logistics, finance, and engineering. Several variants
exist to accommodate for different problem types. In this article we
discuss the fixed-destination, multi-depot travelling salesman
problem, where several salesmen will start from different depots, and
they are required to return to the depot they originated from. We
propose a novel formulation for this problem using 2-index binary
variables and node currents, and compare it to other 2-index
formulations from the literature. This novel formulation requires less
binary variables and continuous variables to formulate a problem,
resulting in lower computation times. Using a large benchmark the
effectiveness of the new formulation is demonstrated.