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 language | English |
---|---|
Pages (from-to) | 463-477 |
Journal | European Journal of Operational Research |
Volume | 265 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2018 |
Keywords
- traveling salesman
- node current
- integer programming
- fixed-destination problem