A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem


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.


Downloads:
 * Online version of the paper
 * Corresponding technical report: pdf file (240 KB)
      Note: More information on the pdf file format mentioned above can be found here.


Bibtex entry:

@article{BurSu:17-013,
        author={M. Burger and Z. Su and B. {D}e Schutter},
        title={A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem},
        journal={European Journal of Operational Research},
        volume={265},
        number={2},
        pages={463--477},
        month=mar,
        year={2018},
        doi={10.1016/j.ejor.2017.07.056}
        }



Go to the publications overview page.


This page is maintained by Bart De Schutter. Last update: March 21, 2022.