Reference : Exact algorithms for the Equitable Traveling Salesman Problem
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/208849
Exact algorithms for the Equitable Traveling Salesman Problem
English
Kinable, Joris mailto [Carnegie Mellon University > Tepper School of Business > > >]
Smeulders, Bart mailto [Université de Liège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Delcour, Eline [KU Leuven > > > >]
Spieksma, Frits C.R. mailto [KU Leuven > Faculty of Business and Economics > ORSTAT > >]
2017
European Journal of Operational Research
Elsevier Science
Yes (verified by ORBi)
International
0377-2217
1872-6860
Amsterdam
The Netherlands
[en] Combinatorial Optimization ; Exact Algorithms ; Branch- and-Price
[en] 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.
http://hdl.handle.net/2268/208849
10.1016/j.ejor.2017.02.017

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
equitTSP Accepted Manuscript.pdfAuthor preprint616.45 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.