The traveling salesman problem (TSP) is a complex problem that is raising interest in many scientists. The aim of TSP is to find the set of points that constructs the minimal tour from an initial point (home) to the last point and the last point to the home. Metaheuristics are mostly nature-inspired algorithms that have been applied to combinatorial problems, especially on TSP. In this paper, a new discrete sine–cosine algorithm (DSCA2), which is a population-based optimization algorithm, was applied to the traveling salesman problem. DSCA2 uses two different mathematical expressions to update the solutions in each generation. To evaluate the performance of the DSCA2 with heuristic algorithms, such as swap/or insertion, reverse/or 2-opt swap, swap-reverse/or 3-opt swap, k-opt swap, and nearest neighbor; it has been tested on fifteen benchmark problems and compared to other popular algorithms. The computational results show that the DSCA2 and its hybrid forms can find well-quality solutions compared to the DSCA1, discrete sine–cosine algorithm (DSCA), black hole algorithm (BHA), camel algorithm (CA), whale optimization algorithm (WOA), classical algorithms such as ant-colony optimization system (ACS), and tabu search + nearest neighbor (TS + NN) algorithm. Moreover, the DSCA2 and its derived forms are competitive in CPU time as compared to other test algorithms.