The Traveling Salesman Problem (TSP) aims at finding the shortest trip for a salesman, who has to visit each of the locations from a given set exactly once, starting and ending at the same location. Here, we consider the Euclidean version of the problem, in which the locations are points in the two-dimensional Euclidean space and the distances are correspondingly Euclidean distances. We propose simple, fast, and easily implementable heuristics that work well, in practice, for large real-life problem instances. The algorithm works on three phases, the constructive, the insertion, and the improvement phases. The first two phases run in time $O\left(n^2\right)$ and the number of repetitions in the improvement phase, in practice, is bounded by a small constant. We have tested the practical behavior of our heuristics on the available benchmark problem instances. The approximation provided by our algorithm for the tested benchmark problem instances did not beat best known results. At the same time, comparing the CPU time used by our algorithm with that of the earlier known ones, in about 92% of the cases our algorithm has required less computational time. Our algorithm is also memory efficient: for the largest tested problem instance with 744,710 cities, it has used about 50 MiB, whereas the average memory usage for the remained 217 instances was 1.6 MiB.

The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining $n-1$ cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances.

In the Multiple Traveling Salesman Problem (MTSP) we are given $n+1$ cities, among which there is one distinct city called depot and $k$ salesmen. A tour for each salesman that starts from the depot, ends also in depot and visits once some other cities, is to be constructed. The cost of a tour is the sum of the individual costs of each pair of cities from that tour. There are lower and upper bounds on the number of cities that each salesman has to visit. Respecting these restrictions, we wish to minimize the total cost of all $k$ tours. We study the two-dimensional Euclidean case and suggest a 3-phase heuristic algorithm. At phase 1 we partition the whole set of cities into $k$ disjoint subsets. At phase 2 we built a feasible tour for each of these subsets. Phase 3 is designed to improve the tours of phase 2. Among the 22 known benchmark instances, our algorithm improved the best known solutions (BKS) for 12 of them, for 4 benchmark instances we obtained the earlier best known costs, for 4 of the instances our algorithm gave an approximation gap within 3% of the BKS, and for the remaining 2 instances the approximation gap was more than 3%.

The Capacitated Vehicle Routing Problem (CVRP) consists of generating a customer route for each vehicle in which the sum of the customer demands does not exceed the vehicle's capacity. Each vehicle must start from the depot, and when it finishes visiting the last customer, it must return to the depot, thus managing to visit all customers only once by any of the vehicles and have a route solution where the sum of the distances of all the routes is the minimum. This research proposed using randomness and the Swap local search algorithm to create an initial solution with a good neighborhood. Later, the Tabu Search algorithm is employed to explore the solution space and obtain an improved solution. The proposed algorithms give feasible solutions with an approximation of less than a 10% difference, and in some cases, the best-known solution is obtained.