TY - JOUR

T1 - Exact algorithms for the Equitable Traveling Salesman Problem

AU - Kinable, J.

AU - Smeulders, B.

AU - Delcour, E.

AU - Spieksma, F.C.R.

PY - 2017/9/1

Y1 - 2017/9/1

N2 - Given a weighted graph G = (V , E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute difference in costs between the two matchings is minimized. The problem is shown to be NP-Hard, even when the graph G is complete. We present two integer programming models to solve the ETSP problem and compare the strength of these formulations. One model is solved through branch-and-cut, whereas the other model is solved through a branch-and-price framework. A simple local search heuristic is also implemented. We conduct computational experiments on different types of instances, often derived from the TSPLib. It turns out that the behavior of the different approaches varies with the type of instances. For small and medium sized instances, branch-and-bound and branch-and-price produce comparable results. However, for larger instances branch-and-bound outperforms branch-and-price.

AB - Given a weighted graph G = (V , E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute difference in costs between the two matchings is minimized. The problem is shown to be NP-Hard, even when the graph G is complete. We present two integer programming models to solve the ETSP problem and compare the strength of these formulations. One model is solved through branch-and-cut, whereas the other model is solved through a branch-and-price framework. A simple local search heuristic is also implemented. We conduct computational experiments on different types of instances, often derived from the TSPLib. It turns out that the behavior of the different approaches varies with the type of instances. For small and medium sized instances, branch-and-bound and branch-and-price produce comparable results. However, for larger instances branch-and-bound outperforms branch-and-price.

KW - Combinatorial optimization

KW - Traveling Salesman Problem

KW - Branch-and-bound

KW - Branch-and-price

KW - Exact algorithms

U2 - 10.1016/j.ejor.2017.02.017

DO - 10.1016/j.ejor.2017.02.017

M3 - Article

VL - 261

SP - 475

EP - 485

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -