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

M Burger, Z. Su, Bart De Schutter

Research output: Contribution to journalArticleScientificpeer-review

15 Citations (Scopus)

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 paper, 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
Original languageEnglish
Pages (from-to)463-477
JournalEuropean Journal of Operational Research
Volume265
Issue number2
DOIs
Publication statusPublished - 2018

Keywords

  • traveling salesman
  • node current
  • integer programming
  • fixed-destination problem

Fingerprint

Dive into the research topics of 'A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem'. Together they form a unique fingerprint.

Cite this