Exact algorithms for the equitable traveling salesman problem

Joris Kinable, Bart Smeulders, Eline Delcour and Frits Spieksma

No 538102, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: 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. One model is solved through branch-and-bound-and-cut, whereas the other model is solved through a branch-and-price-and-cut 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; however, the branch-and-bound-and-cut approach implemented in Cplex seems to work best overall.

Date: 2016-04
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1610 , volume 261, issue 2, pages 475-485

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/383122 Exact algorithms for the equitable traveling salesman problem (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ete:kbiper:538102

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().