Solving the family traveling salesman problem

Raquel Bernardino and Ana Paias

European Journal of Operational Research, 2018, vol. 267, issue 2, 453-466

Abstract: In this paper we address the family traveling salesman problem (FTSP), an NP-hard problem in which the set of nodes of a graph is partitioned into several subsets, which are called families. The objective is to visit a predefined number of nodes in each family at a minimum cost. We present several compact and non-compact models for the FTSP. Computational experiments with benchmark instances show that the non-compact models outperform the compact ones. One of the non-compact models is able to solve instances with 127 nodes, in less than 70 seconds, and one of the instances with 280 nodes in 3615 seconds. The optimal values of these instances were not known. For the higher dimensioned instances, the ones whose optimal value remains unknown, we propose an iterated local search algorithm that is able to improve the best known upper bounds from the literature.

Keywords: Combinatorial optimization; Traveling salesman problem; Multicommodity flows; Branch-and-cut; Metaheuristics (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717310743
Full text for ScienceDirect subscribers only

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:eee:ejores:v:267:y:2018:i:2:p:453-466

DOI: 10.1016/j.ejor.2017.11.063

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().