Selective generalized travelling salesman problem. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Derya, Tusan; Dinler, Esra; Keçeci, Barış
• Is Part Of: Mathematical and computer modelling of dynamical systems. Volume 26:Issue 1(2020)
• Page Start: 80
• Page End: 118
• Publication Date: 2020-01-02
• Subjects: Travelling Salesman -- Routing Problems with Profits -- Mathematical Formulation; Engineering -- Mathematical models -- Periodicals; Computer simulation -- Periodicals; 515.39
• DOI: 10.1080/13873954.2019.1705496
• Languages: English
• ISSNs: 1387-3954

Abstract

ABSTRACT: This paper introduces the Selective Generalized Traveling Salesman Problem (SGTSP). In SGTSP, the goal is to determine the maximum profitable tour within the given threshold of the tour's duration, which consists of a subset of clusters and a subset of nodes in each cluster visited on the tour. This problem is a combination of cluster and node selection and determining the shortest path between the selected nodes. We propose eight mixed integer programming (MIP) formulations for SGTSP. All of the given MIP formulations are completely new, which is one of the major novelties of the study. The performance of the proposed formulations is evaluated on a set of test instances by conducting 4608 experimental runs. Overall, 4138 out of 4608 (~90%) test instances were solved optimally by using all formulations.