XVII Международная студенческая научная конференция Студенческий научный форум - 2025

Introduction

The Traveling Salesperson Problem (TSP) is a well-known combinatorial optimization problem that seeks to find the most cost-effective route that visits a specified set of cities exactly once and returns to the starting city.

Formally, a salesperson needs to start from the first city, visit cities 2, 1, 3...n exactly once in an unknown order, and return to the first city. The distances between all cities are known. What is the optimal order to visit the cities such that the total closed-loop tour of the salesperson is minimized?

Objective:

To determine the best route for delivering flowers from a regional center to cities in the surrounding region by solving the Traveling Salesperson Problem.

Tasks:

1. Investigate existing methods for solving the Traveling Salesperson Problem and identify which are definitely unsuitable for the specific problem constraints.

2. Determine the methods that will be used to solve the problem.

3. Write code in the Python programming language to simplify calculations.

4. Select the optimal route for flower delivery.

Relevance

Currently, many companies promote their goods and services on their own websites and arrange for delivery to pick up points or directly to customers' homes via courier. Route optimization for the timely delivery of goods to consumers plays a crucial role in the operations of these companies, which essentially involves solving the Traveling Salesperson Problem.

To address our specific problem, we have selected three main methods: the brute-force method (complete enumeration), the nearest neighbor method, and the branch and bound method. These are among the most common methods for solving the TSP and are even used by large companies such as Aeroflot (branch and bound method) and Yandex (Dijkstra's algorithm or the nearest neighbor method).

We chose flower delivery as a specific use case because it is consistently relevant and demands accuracy and punctuality.

This work examines several methods for solving the Traveling Salesperson Problem to determine the best route for delivering flowers from a regional center to cities in the surrounding region.

Brute force search

The brute-force method is a mathematical problem-solving approach that involves examining all possible solutions. The complexity of this method increases as the number of solutions grows, and for problems in the NP (Non-deterministic Polynomial time) class, the search time can reach decades. In the case of the Traveling Salesperson Problem (TSP), the size of the search space grows factorially with the number of cities. For example, for the five cities in the Sverdlovsk region that we are considering, the number of possible routes is (5 - 1)! = 24, and for an asymmetric problem, the number of options to iterate through is (