travelling salesman problem quora

Something went wrong. Wait a moment and try again.

Forgot password? New user? Sign up

Existing user? Log in

Traveling Salesperson Problem

Already have an account? Log in here.

A salesperson needs to visit a set of cities to sell their goods. They know how many cities they need to go to and the distances between each city. In what order should the salesperson visit each city exactly once so that they minimize their travel time and so that they end their journey in their city of origin?

The traveling salesperson problem is an extremely old problem in computer science that is an extension of the Hamiltonian Circuit Problem . It has important implications in complexity theory and the P versus NP problem because it is an NP-Complete problem . This means that a solution to this problem cannot be found in polynomial time (it takes superpolynomial time to compute an answer). In other words, as the number of vertices increases linearly, the computation time to solve the problem increases exponentially.

The following image is a simple example of a network of cities connected by edges of a specific distance. The origin city is also marked.

Network of cities

Here is the solution for that network, it has a distance traveled of only 14. Any other path that the salesman can takes will result in a path length that is more than 14.

Relationship to Graphs

Special kinds of tsp, importance for p vs np, applications.

The traveling salesperson problem can be modeled as a graph . Specifically, it is typical a directed, weighted graph. Each city acts as a vertex and each path between cities is an edge. Instead of distances, each edge has a weight associated with it. In this model, the goal of the traveling salesperson problem can be defined as finding a path that visits every vertex, returns to the original vertex, and minimizes total weight.

To that end, many graph algorithms can be used on this model. Search algorithms like breadth-first search (BFS) , depth-first search (DFS) , and Dijkstra's shortest path algorithm can certainly be used, however, they do not take into consideration that fact that every vertex must be visited.

The Traveling Salesperson Problem (TSP), an NP-Complete problem, is notoriously complicated to solve. That is because the greedy approach is so computational intensive. The greedy approach to solving this problem would be to try every single possible path and see which one is the fastest. Try this conceptual question to see if you have a grasp for how hard it is to solve.

For a fully connected map with \(n\) cities, how many total paths are possible for the traveling salesperson? Show Answer There are (n-1)! total paths the salesperson can take. The computation needed to solve this problem in this way grows far too quickly to be a reasonable solution. If this map has only 5 cities, there are \(4!\), or 24, paths. However, if the size of this map is increased to 20 cities, there will be \(1.22 \cdot 10^{17}\) paths!

The greedy approach to TSP would go like this:

• Find all possible paths.
• Find the cost of every paths.
• Choose the path with the lowest cost.

Another version of a greedy approach might be: At every step in the algorithm, choose the best possible path. This version might go a little quicker, but it's not guaranteed to find the best answer, or an answer at all since it might hit a dead end.

For NP-Hard problems (a subset of NP-Complete problems) like TSP, exact solutions can only be implemented in a reasonable amount of time for small input sizes (maps with few cities). Otherwise, the best approach we can do is provide a heuristic to help the problem move forward in an optimal way. However, these approaches cannot be proven to be optimal because they always have some sort of downside.

Small input sizes

As described, in a previous section , the greedy approach to this problem has a complexity of \(O(n!)\). However, there are some approaches that decrease this computation time.

The Held-Karp Algorithm is one of the earliest applications of dynamic programming . Its complexity is much lower than the greedy approach at \(O(n^2 2^n)\). Basically what this algorithm says is that every sub path along an optimal path is itself an optimal path. So, computing an optimal path is the same as computing many smaller subpaths and adding them together.

Heuristics are a way of ranking possible next steps in an algorithm in the hopes of cutting down computation time for the entire algorithm. They are often a tradeoff of some attribute - such as completeness, accuracy, or precision - in favor of speed. Heuristics exist for the traveling salesperson problem as well.

The most simple heuristic for this problem is the greedy heuristic. This heuristic simply says, at each step of the network traversal, choose the best next step. In other words, always choose the closest city that you have not yet visited. This heuristic seems like a good one because it is simple and intuitive, and it is even used in practice sometimes, however there are heuristics that are proven to be more effective.

Christofides algorithm is another heuristic. It produces at most 1.5 times the optimal weight for TSP. This algorithm involves finding a minimum spanning tree for the network. Next, it creates matchings for the cities of an odd degree (meaning they have an odd number of edges coming out of them), calculates an eulerian path , and converts back to a TSP path.

Even though it is typically impossible to optimally solve TSP problems, there are cases of TSP problems that can be solved if certain conditions hold.

The metric-TSP is an instance of TSP that satisfies this condition: The distance from city A to city B is less than or equal to the distance from city A to city C plus the distance from city C to city B. Or,

\[distance_{AB} \leq distance_{AC} + distance_{CB}\]

This is a condition that holds in the real world, but it can't always be expected to hold for every TSP problem. But, with this inequality in place, the approximated path will be no more than twice the optimal path. Even better, we can bound the solution to a \(3/2\) approximation by using Christofide's Algorithm .

The euclidean-TSP has an even stricter constraint on the TSP input. It states that all cities' edges in the network must obey euclidean distances . Recent advances have shown that approximation algorithms using euclidean minimum spanning trees have reduced the runtime of euclidean-TSP, even though they are also NP-hard. In practice, though, simpler heuristics are still used.

The P versus NP problem is one of the leading questions in modern computer science. It asks whether or not every problem whose solution can be verified in polynomial time by a computer can also be solved in polynomial time by a computer. TSP, for example, cannot be solved in polynomial time (at least that's what is currently theorized). However, TSP can be solved in polynomial time when it is phrased like this: Given a graph and an integer, x, decide if there is a path of length x or less than x . It's easy to see that given a proposed answer to this question, it is simple to check if it is less than or equal to x.

The traveling salesperson problem, like other problems that are NP-Complete, are very important to this debate. That is because if a polynomial time solution can be found to this problems, then \(P = NP\). As it stands, most scientists believe that \(P \ne NP\).

The traveling salesperson problem has many applications. The obvious ones are in the transportation space. Planning delivery routes or flight patterns, for example, would benefit immensly from breakthroughs is this problem or in the P versus NP problem .

However, this same logic can be applied to many facets of planning as well. In robotics, for instance, planning the order in which to drill holes in a circuit board is a complex task due to the sheer number of holes that must be drawn.

The best and most important application of TSP, however, comes from the fact that it is an NP-Complete problem. That means that its practical applications amount to the applications of any problem that is NP-Complete. So, if there are significant breakthroughs for TSP, that means that those exact same breakthrough can be applied to any problem in the NP-Complete class.

Problem Loading...

Note Loading...

Set Loading...

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Travelling salesman problem

2020 Mathematics Subject Classification: Primary: 90C35 Secondary: 90C27 [ MSN ][ ZBL ]

A generic name for a number of very different problems. For instance, suppose that a facility (a "machine" ) starting from an "idle" position is assigned to process a finite set of "jobs" (say $n$, $n\geq3$ jobs). If the machine has to be "calibrated" (or "set-up" ) for processing each of these jobs and if the machine's "calibration time" (the distance metric) between processing of a pair of jobs in succession is dependent on the particular pair, then a reasonable objective is to organize this job assignment so it will minimize the total machine calibration time. One might want to assume that after the last job is processed the machine returns to its idle position.

A very similar problem exists when the "machine" corresponds to a computer centre which has $n$ programs to run, and each program requires resources such as a compiler, a certain portion of the main memory, and perhaps some other "devices" . I.e., each program requires a specific configuration of devices. Conversion cost (or time) from one configuration to another, say from the configuration of program $i$ to that of program $j$ is denoted by $c_{ij}$ ($\geq0$). Thus, the question becomes that of determining the cost minimizing order in which all the programs ought to be run.

If at the end of running all the programs by the computer centre the system returns to an "idle" configuration, then the number of possible ways to run these programs one after the other equals $n!$ (for $n+1$ configurations).

This is the same problem as that in the story about the lonely salesman who has to visit $n$ sales outlets (starting from his home) and wishes to travel the shortest total distance in the process. It is the salesman's problem to select a distance-minimizing travel order of outlet visits. Thus, the name travelling salesman problem.

In graph terminology terms, the problem is presented as that of a graph $G=(V,E)$, where$V$ is a finite set of nodes ( "cities" ) and $E\subset V\times V$ is the set of edges connecting the node pairs in $V$. If one associates a real-valued "cost" matrix $(c_{ij})$, $i,j=1,\ldots,\lvert V\rvert$, with the set of edges $E$, the travelling salesman dilemma becomes that of constructing a cost-minimizing circuit on $G$ that visits all the nodes in $V$ exactly once, if such a circuit exists (cf. also Graph circuit ).

If the requirement is that all the nodes in $V$ are visited in a cost-minimizing fashion but without necessarily forming a circuit, then the problem is referred to as a travelling salesman path problem, or travelling salesman walk problem. Again, the question of the existence of such a path has to be addressed first.

If the graph $G=(V,A)$, $A\subset V\times V$, assigns a "direction" to each element in $A$ (a subset of arcs), then the corresponding travelling salesman problem is of the "directed" variety. Clearly, there is the option of the mixed problem, where some of the node pairs are connected by arcs and some by edges.

The question of whether a circuit exists in a graph $G$ which visits each node in $V$ exactly once is commonly referred to as that of determining the existence of a Hamiltonian circuit (or path; cf. also Hamiltonian tour ). Graphs for which such a circuit (path) is guaranteed to exist are called Hamiltonian graphs.

The difficulty of determining the existence of a Hamiltonian circuit for a graph $G$ and that of constructing a cost-minimizing travelling salesman circuit on a graph $G$ are very much the same when measured by the worst possible order magnitude of the required number of computer operations. This casts these problems (the travelling salesman and the Hamiltonian circuit problems) as being "hard" (cf. also $\mathcal{NP}$ ). Essentially, for this sort of problems, one does not presently (2000) know of any solution scheme which does not require some sort of enumeration of all possible "configuration" sequences.

See [a1] , [a2] for recent overviews of the problem.

• Mathematics in science and technology
• Operations research, mathematical programming
• This page was last edited on 19 April 2012, at 22:51.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Graph Data Structure And Algorithms
• Introduction to Graphs - Data Structure and Algorithm Tutorials
• Graph and its representations
• Types of Graphs with Examples
• Basic Properties of a Graph
• Applications, Advantages and Disadvantages of Graph
• Transpose graph
• Difference Between Graph and Tree

BFS and DFS on Graph

• Breadth First Search or BFS for a Graph
• Depth First Search or DFS for a Graph
• Applications, Advantages and Disadvantages of Depth First Search (DFS)
• Applications, Advantages and Disadvantages of Breadth First Search (BFS)
• Iterative Depth First Traversal of Graph
• BFS for Disconnected Graph
• Transitive Closure of a Graph using DFS
• Difference between BFS and DFS

Cycle in a Graph

• Detect Cycle in a Directed Graph
• Detect cycle in an undirected graph
• Detect Cycle in a directed graph using colors
• Detect a negative cycle in a Graph | (Bellman Ford)
• Cycles of length n in an undirected and connected graph
• Detecting negative cycle using Floyd Warshall
• Clone a Directed Acyclic Graph

Shortest Paths in Graph

• How to find Shortest Paths from Source to all Vertices using Dijkstra's Algorithm
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm
• Johnson's algorithm for All-pairs shortest paths
• Shortest Path in Directed Acyclic Graph
• Multistage Graph (Shortest Path)
• Shortest path in an unweighted graph
• Karp's minimum mean (or average) weight cycle algorithm
• 0-1 BFS (Shortest Path in a Binary Weight Graph)
• Find minimum weight cycle in an undirected graph

Minimum Spanning Tree in Graph

• Kruskal’s Minimum Spanning Tree (MST) Algorithm
• Difference between Prim's and Kruskal's algorithm for MST
• Applications of Minimum Spanning Tree
• Total number of Spanning Trees in a Graph
• Minimum Product Spanning Tree
• Reverse Delete Algorithm for Minimum Spanning Tree

Topological Sorting in Graph

• Topological Sorting
• All Topological Sorts of a Directed Acyclic Graph
• Kahn's algorithm for Topological Sorting
• Maximum edges that can be added to DAG so that it remains DAG
• Longest Path in a Directed Acyclic Graph
• Topological Sort of a graph using departure time of vertex

Connectivity of Graph

• Articulation Points (or Cut Vertices) in a Graph
• Biconnected Components
• Bridges in a graph
• Eulerian path and circuit for undirected graph
• Fleury's Algorithm for printing Eulerian Path or Circuit
• Strongly Connected Components
• Count all possible walks from a source to a destination with exactly k edges
• Euler Circuit in a Directed Graph
• Word Ladder (Length of shortest chain to reach a target word)
• Find if an array of strings can be chained to form a circle | Set 1
• Tarjan's Algorithm to find Strongly Connected Components
• Paths to travel each nodes using each edge (Seven Bridges of Königsberg)
• Dynamic Connectivity | Set 1 (Incremental)

Maximum flow in a Graph

• Max Flow Problem Introduction
• Ford-Fulkerson Algorithm for Maximum Flow Problem
• Find maximum number of edge disjoint paths between two vertices
• Find minimum s-t cut in a flow network
• Maximum Bipartite Matching
• Channel Assignment Problem
• Introduction to Push Relabel Algorithm
• Introduction and implementation of Karger's algorithm for Minimum Cut
• Dinic's algorithm for Maximum Flow

Some must do problems on Graph

• Find size of the largest region in Boolean Matrix
• Count number of trees in a forest
• A Peterson Graph Problem
• Clone an Undirected Graph
• Introduction to Graph Coloring

Traveling Salesman Problem (TSP) Implementation

• Introduction and Approximate Solution for Vertex Cover Problem
• Erdos Renyl Model (for generating Random Graphs)
• Chinese Postman or Route Inspection | Set 1 (introduction)
• Hierholzer's Algorithm for directed graph
• Boggle (Find all possible words in a board of characters) | Set 1
• Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction)
• Construct a graph from given degrees of all vertices
• Determine whether a universal sink exists in a directed graph
• Number of sink nodes in a graph
• Two Clique Problem (Check if Graph can be divided in two Cliques)

Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.  Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.  For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time known solution for this problem.   

Examples: 

In this post, the implementation of a simple solution is discussed.

• Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.
• Generate all (n-1)! permutations of cities.
• Calculate the cost of every permutation and keep track of the minimum cost permutation.
• Return the permutation with minimum cost.

Below is the implementation of the above idea 

Time complexity:  O(n!) where n is the number of vertices in the graph. This is because the algorithm uses the next_permutation function which generates all the possible permutations of the vertex set.  Auxiliary Space: O(n) as we are using a vector to store all the vertices.

Please Login to comment...

Similar reads.

• NP Complete

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

DSA Tutorial

Linked lists, stacks & queues, hash tables, shortest path, minimum spanning tree, maximum flow, time complexity, dsa reference, dsa examples, dsa the traveling salesman problem.

The Traveling Salesman Problem

The Traveling Salesman Problem states that you are a salesperson and you must visit a number of cities or towns.

Rules : Visit every city only once, then return back to the city you started in.

Goal : Find the shortest possible route.

Except for the Held-Karp algorithm (which is quite advanced and time consuming, (\(O(2^n n^2)\)), and will not be described here), there is no other way to find the shortest route than to check all possible routes.

This means that the time complexity for solving this problem is \(O(n!)\), which means 720 routes needs to be checked for 6 cities, 40,320 routes must be checked for 8 cities, and if you have 10 cities to visit, more than 3.6 million routes must be checked!

Note: "!", or "factorial", is a mathematical operation used in combinatorics to find out how many possible ways something can be done. If there are 4 cities, each city is connected to every other city, and we must visit every city exactly once, there are \(4!= 4 \cdot 3 \cdot 2 \cdot 1 = 24\) different routes we can take to visit those cities.

The Traveling Salesman Problem (TSP) is a problem that is interesting to study because it is very practical, but so time consuming to solve, that it becomes nearly impossible to find the shortest route, even in a graph with just 20-30 vertices.

If we had an effective algorithm for solving The Traveling Salesman Problem, the consequences would be very big in many sectors, like for example chip design, vehicle routing, telecommunications, and urban planning.

Checking All Routes to Solve The Traveling Salesman Problem

To find the optimal solution to The Traveling Salesman Problem, we will check all possible routes, and every time we find a shorter route, we will store it, so that in the end we will have the shortest route.

Good: Finds the overall shortest route.

Bad: Requires an awful lot of calculation, especially for a large amount of cities, which means it is very time consuming.

How it works:

• Check the length of every possible route, one route at a time.
• Is the current route shorter than the shortest route found so far? If so, store the new shortest route.
• After checking all routes, the stored route is the shortest one.

Such a way of finding the solution to a problem is called brute force .

Brute force is not really an algorithm, it just means finding the solution by checking all possibilities, usually because of a lack of a better way to do it.

Speed: {{ inpVal }}

Finding the shortest route in The Traveling Salesman Problem by checking all routes (brute force).

Progress: {{progress}}%

n = {{vertices}} cities

{{vertices}}!={{posRoutes}} possible routes

Show every route: {{showCompares}}

The reason why the brute force approach of finding the shortest route (as shown above) is so time consuming is that we are checking all routes, and the number of possible routes increases really fast when the number of cities increases.

Finding the optimal solution to the Traveling Salesman Problem by checking all possible routes (brute force):

Using A Greedy Algorithm to Solve The Traveling Salesman Problem

Since checking every possible route to solve the Traveling Salesman Problem (like we did above) is so incredibly time consuming, we can instead find a short route by just going to the nearest unvisited city in each step, which is much faster.

Good: Finds a solution to the Traveling Salesman Problem much faster than by checking all routes.

Bad: Does not find the overall shortest route, it just finds a route that is much shorter than an average random route.

• Visit every city.
• The next city to visit is always the nearest of the unvisited cities from the city you are currently in.
• After visiting all cities, go back to the city you started in.

This way of finding an approximation to the shortest route in the Traveling Salesman Problem, by just going to the nearest unvisited city in each step, is called a greedy algorithm .

Finding an approximation to the shortest route in The Traveling Salesman Problem by always going to the nearest unvisited neighbor (greedy algorithm).

As you can see by running this simulation a few times, the routes that are found are not completely unreasonable. Except for a few times when the lines cross perhaps, especially towards the end of the algorithm, the resulting route is a lot shorter than we would get by choosing the next city at random.

Finding a near-optimal solution to the Traveling Salesman Problem using the nearest-neighbor algorithm (greedy):

Other Algorithms That Find Near-Optimal Solutions to The Traveling Salesman Problem

In addition to using a greedy algorithm to solve the Traveling Salesman Problem, there are also other algorithms that can find approximations to the shortest route.

These algorithms are popular because they are much more effective than to actually check all possible solutions, but as with the greedy algorithm above, they do not find the overall shortest route.

Algorithms used to find a near-optimal solution to the Traveling Salesman Problem include:

• 2-opt Heuristic: An algorithm that improves the solution step-by-step, in each step removing two edges and reconnecting the two paths in a different way to reduce the total path length.
• Genetic Algorithm: This is a type of algorithm inspired by the process of natural selection and use techniques such as selection, mutation, and crossover to evolve solutions to problems, including the TSP.
• Simulated Annealing: This method is inspired by the process of annealing in metallurgy. It involves heating and then slowly cooling a material to decrease defects. In the context of TSP, it's used to find a near-optimal solution by exploring the solution space in a way that allows for occasional moves to worse solutions, which helps to avoid getting stuck in local minima.
• Ant Colony Optimization: This algorithm is inspired by the behavior of ants in finding paths from the colony to food sources. It's a more complex probabilistic technique for solving computational problems which can be mapped to finding good paths through graphs.

Time Complexity for Solving The Traveling Salesman Problem

To get a near-optimal solution fast, we can use a greedy algorithm that just goes to the nearest unvisited city in each step, like in the second simulation on this page.

Solving The Traveling Salesman Problem in a greedy way like that, means that at each step, the distances from the current city to all other unvisited cities are compared, and that gives us a time complexity of \(O(n^2) \).

But finding the shortest route of them all requires a lot more operations, and the time complexity for that is \(O(n!)\), like mentioned earlier, which means that for 4 cities, there are 4! possible routes, which is the same as \(4 \cdot 3 \cdot 2 \cdot 1 = 24\). And for just 12 cities for example, there are \(12! = 12 \cdot 11 \cdot 10 \cdot \; ... \; \cdot 2 \cdot 1 = 479,001,600\) possible routes!

See the time complexity for the greedy algorithm \(O(n^2)\), versus the time complexity for finding the shortest route by comparing all routes \(O(n!)\), in the image below.

But there are two things we can do to reduce the number of routes we need to check.

In the Traveling Salesman Problem, the route starts and ends in the same place, which makes a cycle. This means that the length of the shortest route will be the same no matter which city we start in. That is why we have chosen a fixed city to start in for the simulation above, and that reduces the number of possible routes from \(n!\) to \((n-1)!\).

Also, because these routes go in cycles, a route has the same distance if we go in one direction or the other, so we actually just need to check the distance of half of the routes, because the other half will just be the same routes in the opposite direction, so the number of routes we need to check is actually \( \frac{(n-1)!}{2}\).

But even if we can reduce the number of routes we need to check to \( \frac{(n-1)!}{2}\), the time complexity is still \( O(n!)\), because for very big \(n\), reducing \(n\) by one and dividing by 2 does not make a significant change in how the time complexity grows when \(n\) is increased.

To better understand how time complexity works, go to this page .

Actual Traveling Salesman Problems Are More Complex

The edge weight in a graph in this context of The Traveling Salesman Problem tells us how hard it is to go from one point to another, and it is the total edge weight of a route we want to minimize.

So far on this page, the edge weight has been the distance in a straight line between two points. And that makes it much easier to explain the Traveling Salesman Problem, and to display it.

But in the real world there are many other things that affects the edge weight:

• Obstacles: When moving from one place to another, we normally try to avoid obstacles like trees, rivers, houses for example. This means it is longer and takes more time to go from A to B, and the edge weight value needs to be increased to factor that in, because it is not a straight line anymore.
• Transportation Networks: We usually follow a road or use public transport systems when traveling, and that also affects how hard it is to go (or send a package) from one place to another.
• Traffic Conditions: Travel congestion also affects the travel time, so that should also be reflected in the edge weight value.
• Legal and Political Boundaries: Crossing border for example, might make one route harder to choose than another, which means the shortest straight line route might be slower, or more costly.
• Economic Factors: Using fuel, using the time of employees, maintaining vehicles, all these things cost money and should also be factored into the edge weights.

As you can see, just using the straight line distances as the edge weights, might be too simple compared to the real problem. And solving the Traveling Salesman Problem for such a simplified problem model would probably give us a solution that is not optimal in a practical sense.

It is not easy to visualize a Traveling Salesman Problem when the edge length is not just the straight line distance between two points anymore, but the computer handles that very well.

COLOR PICKER

Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail: [email protected]

Report Error

If you want to report an error, or if you want to make a suggestion, send us an e-mail: [email protected]

Top Tutorials

Top references, top examples, get certified.

What is a Travelling Salesman Problem (TSP)? Explained!

• Author: Diksha Bhandari
• Read Time: 9 min
• Published: September 14, 2023
• Last Update: November 8th, 2023

Table of Contents

• Asset Tracking
• Dispatch Management
• Driver Behaviour
• Electric Vehicle
• Employee Management
• Field Sales And Service
• Fleet Management
• Fuel Management
• GPS Software
• GPS Trackers and Hardware
• Last Mile Delivery
• Lead Management
• Leave And Attendance
• Roster Management
• Route Optimisation
• Route Planning
• Sensor Integration
• Task and Workflow
• Tech and Beyond
• TrackoBit Industries
• TrackoField
• TrackoField Industries
• TrackoMile Industries
• Vehicle Tracking
• Video telematics
• What's New

Want to know what a travelling salesman problem (TSP) is? Need solutions to real-life TSP challenges. Learn here. 

Do you also look for the shortest route on Google Maps before embarking on a trip?

I am sure, you know multiple routes to reach the office, the mall, or your desired location, but checking on the internet before leaving home has become a ritual. It becomes all the more important to refer to maps when you have to pick up friends or colleagues along the way.

‘ADD STOPS’

Yes, you are right! 💯

That’s what solving the TSP challenge using software means!

What is a Travelling Salesman Problem (TSP)?

The traveling salesman problem is the popular combinatorial optimisation challenge in mathematics and computer science. The prime objective of the problem is to determine the shortest possible route a salesperson must take to cover a set of locations in one go and then return to the starting point.

Addressing travelling salesman challenges and their optimisation are more relevant in this time and age, especially in the supply chain, logistics and delivery space.

TSP may result in delayed deliveries and slimming profits as it’s not easy for delivery agents to choose the most viable and cost-effective route in real-time.

What are Traveling Salesman Problem Challenges to Solve?

When a salesperson is in the field hopping from one client site to another, finding out the best and the shortest route is an added pressure on the agent. In today’s day and age, distance isn’t the only factor that defines efficiency. There are several factors, such as time, fuel consumption, capacity, etc. that together define efficiency.

However, addressing the travelling salesman challenges involves mitigating a few unavoidable challenges along the way that field agents face themselves.

1. Time Constraints

Sales agents often have a tight schedule with multiple deliveries to make with a short TAT. Similarly, in TSP, optimising routes to minimise travel time is a fundamental challenge.

2. Last-minute Changes

Eleventh-hour changes are not a new concept for salespeople. They encounter urgent visits and last-minute cancellations a lot. Similarly, TSP solutions must be adaptable to handle dynamic scenarios and route modifications.

3. Resource Efficiency

Just as salespersons aim at reducing fuel costs and ensuring on-time deliveries, TSP solutions such as TrackoMile must strive for resource optimisation by reducing travel distances and delivery TAT.

4. Objective Diversification

While solving the travelling salesman problem (TSP) , optimising multiple objectives such as cost, time, and environmental factors adds complexity as solutions need to balance conflicting goals.

5. Combinatorial Complexity

TSP is a combinatorial optimisation problem, which means it involves complicated mathematical calculations with numerous variables. Sometimes, complex scenarios get further intricate as multiple variables are involved.

6. Adaptability and Scalability

Similarly, how sales agents adjust to the routes on the fly, the route algorithm must be flexible and responsive to real-time changes such as spiking volumes, vehicle breakdown or traffic slow down. A TSP solution must have a good appetite to handle large datasets and complex networks.

Also Read 4 Key Solutions for Fuel Management System 2023

Top 5 Solutions to The Travelling Salesman Problem

The traveling salesman problem solutions offer various trade-offs between computational intricacies and the quality of the resolution, allowing practitioners to choose the best-suited approach based on their needs and problems.

Here are the Top 5 solutions to the Traveling Salesman Problem (TSP) :

1. Brute Force Algorithm

The Brute Force algorithm is a straight approach to solving the Traveling Salesman Problem (TSP). It systematically explores all possible routes to identify the shortest one among them all. While it guarantees an optimal solution, its downside lies in its major time complexity, making it practical only for small TSP challenges.

2. Nearest Neighbour Algorithm

The Nearest Neighbour method is the simplest heuristic for the TSP. It starts from the first location and repeatedly selects the closest unvisited location to form a tour. Although it is quick to implement this method, it may always yield the optimal solution for it prioritises proximity over other factors.

3. Genetic Algorithm

This technique or method draws inspiration from nature itself. They evolve TSP solutions through selection, crossovers and mutation. They pick the best routes and mix them up. This creates new routes that might be even better. Then, they keep the best ones and repeat the mixing and picking process. Survival of the fittest in the true sense.

4. Ant Colony Optimisation (ACO)

Ants have a tendency to leave pheromones on the shorter routes they find, calling fellow ants on the same route. They keep leaving more pheromones on the shorter routes they find. Over time, the collective behaviour of the ants causes them to converge on the shortest route. Inspired by the nature of ants, ACO finds the shortest route by analysing the trails of data left by artificial ants based on the strength of these data trails.

5. Dynamic Programming

Dynamic Programming is like solving a puzzle, step-by-step, by breaking it into smaller pieces. In TSP challenges, it finds the best route to visit all locations. It begins with figuring out the shortest route between two locations; then it builds on that to find ways to more locations. It’s a smart TSP solution for small scenarios but may require significant memory resources for larger and more complex problems.

What Are Real-world Travelling Salesman Problem Applications?

The Traveling Salesman Problem (TSP) has a wide array of applications across various domains due to its relevance in optimising routes and sequences. Here are several crucial real-word TSP applications and implementations in the real world.

1. TSP implementation in Logistics and Delivery Services

The logistics and supply chain sectors have the widest TSP applications.

• Courier, Express & Parcel : Companies like FedEx, UPS, and DHL rely on TSP algorithms to optimise delivery routes for their fleet of delivery trucks. By finding the most efficient sequence of stops, they minimise fuel consumption , reduce delivery TAT, and save on operational overheads too.
• On-demand Delivery : Food delivery companies, instant grocery delivery apps and at-home appointment platforms like Swiggy, BlinkIt and UrbanCompany, respectively, leverage TSP solutions to ensure timely delivery. Enhancing the customer experience and increasing the number of deliveries each rider can make.

2. TSP Applications in Transportation and Urban Planning Waste collection routes, Traffic light synchronisation, optic cable installation, etc. are some areas where TSP Solutions works like a knight in shining armour. Other real-world TSP applications include

• Public Transport : City planners and public transport agencies use TSP principles to design bus, tram and train routes that reduce travel for passengers.
• Emergency Service Dispatch : Ambulance services, Police PCR vans employ TSP algorithms to dispatch vehicles quickly and efficiently in response to emergency calls. Finding the shortest route to reach the incident location can save lives.
• Urban Mobility Solution : In the era of ride-sharing and on-demand mobility apps like Uber, Ola, Lyft, etc., real-world TSP applications become prominent. TSP solutions optimise the route to destinations, ensuring quick and cost-effective transportation.

Other significant real-life applications of the Travelling Salesman Problem are

• TSP in Healthcare and Medical Research – for DNA sequencing and understanding genetic patterns and diseases.
• TSP in Manufacturing and Production – In circuit board manufacturing and job scheduling of technicians.
• TSP in Robotics and Autonomous Vehicles -Self-driving cars and drones use TSP-like algorithms for efficient navigation.

Solving the Travelling Salesman Problem – Last Mile Delivery Route Optimisation

Route optimisation is the key to efficient last-mile delivery . In order to attain flawless route optimisation, the software must solve the traveling salesman problem every step of the way.

Why it’s essential to solve TSP for Last Mile Delivery?

In simple and minimal words, solving TSP problems helps in many ways:

• Saves Time : It makes deliveries faster, so your customers get orders sooner.
• Customer Satisfaction : Fast deliveries give you an edge over the competition and enhance customer experience too.
• Saves Money : It reduces fuel wastage and vehicle wear, making deliveries cheaper.
• Environment Friendly : It lowers pollution by using fewer vehicles and shorter routes.
• Happy Staff: Drivers and dispatchers have less stress and can finish their work faster.

How do we solve the travelling salesman problem for last-mile delivery?

Solving TSP challenges for Last-mile delivery is like solving a big jigsaw puzzle. There are a hundred thousand addresses to visit daily. The software must find the shortest and most optimised route to them and come back to the starting point at the end.

• Our route optimisation software , TrackoMile, leverages capacity management , routing algorithms and robust rule engines to present the most optimal combination of delivery addresses. Thereby giving the most optimally planned routes or trips.
• All delivery managers have to do is upload the CSV file of the addresses or integrate TrackoMile to their CRM to fetch the delivery addresses. Now trip allocation, route optimisation, dispatch and everything else happen in a few clicks.
• ETA when the delivery is en route, POD when the order is delivered successfully, and trip analysis, are added features to simplify overall operations.

The Vehicle Routing Problem is very similar to TSP, with wide applications in logistics, delivery services and transportation. While TSP focuses on finding the shortest route for a single traveller visiting various locations, VRP deals with multiple vehicles serving multiple customers, considering added constraints like vehicle capacity, TATs and more.

How Can AI Help in Solving Traveling Salesman Problem (TSP)?

AI or Artificial Intelligence are becoming the driving force for business growth across various industrial sectors. AI particularly aids in solving the Traveling Salesman Problem(TSP) in the logistics and delivery sector by employing advanced algorithms and techniques. What are a few tricks up AI’s sleeves that help in automating TSP resolution? Let’s find out!

1. Advanced Algorithms

AI algorithms such as Genetic Algorithms, ACO, simulated annealing and a few others mentioned above, tackle complex Travelling Salesman Problem scenarios.

2. Machine Learning

Gathering information from historical data and optimising routes based on real-time insights is what AI is best for. Machine learning models are trained to adapt to changing conditions, like traffic, weather and delivery constraints, to provide a more accurate plan of action.

3. Parallel Computing

AIi enables the use of a parallel computing process, which means solving multiple segments of TSP simultaneously. This accelerates the problem-solving process for large-scale challenges.

4. Heuristic Improvement

TSP Heuristics powered by AI can groom initial solutions, gradually improving their results over time. These heuristics can be applied iteratively by AI to reach better results.

5. Hybrid Approaches

Applying hybrid algorithms is not a new technique to refine techniques and produce more accurate results. AI on top of it singles out data-oriented combinations that work the best in varied use cases.

Wrapping Up!

The travelling salesman problem’s importance lies in its real-world applications. Whether optimising delivery routes, planning manufacturing processes or organising circuit board drilling, finding the most efficient way to cover multiple locations is crucial to minimise costs and save time.

The TSP problems have evolved over the years, and so have TSP algorithms, heuristics and solutions. With the advent of advanced technologies such as GPS and machine learning, TSP continues to adapt and find new applications in emerging fields, cementing its status as a fundamental problem in optimization theory and a valuable tool for various industries. Mobility automation software like Trackobit, TrackoMile and TrackoField resort to TSP heuristics to solve challenges along the way.

Read Blog – Best Delivery Route Planner Apps for 2023

Traveling Salesman Problem FAQs

What is tsp.

TSP is an abbreviation for Traveling Salesman Problem. It’s the routing problem that deals with finding the shortest route to travel to a combination of locations in the most optimal manner.

Is Travelling Salesman Problem Solvable?

Yes, the Traveling Salesman Problem (TSP) is solvable, but the time to find the solution can grow proportionately with an increase in the number of locations. With the evolution of travelling salesman problem applications, various TSP algorithms and heuristics, their hybrids have also emerged.

Wh at is the objective of TSP?

The objective of the Traveling Salesman Problem (TSP) is to find the shortest possible route that covers all given locations or waypoints and comes back to the starting point with the least resource utilisation.

Diksha Bhandari

Currently creating SaaSy content strategies for TrackoBit and TrackoField, this content professional has dedicated a decade of her life to enriching her portfolio and continues to do so. In addition to playing with words and spilling SaaS, she has a passion for traveling to the mountains and sipping on adrak wali chai.

• Author Showcase
• All Blog Post

Never Miss a Beat

Related Blog

Top 12 Google Map Alternatives – Offering Precise Navigation

Explore our best picks for 12 free Google map alternatives that offer accurate and secure location and navigational solutions. 

Food Delivery Trends to Watch in 2024 & Beyond

Food and technology are both revolving along with consumer demands. Here are some of the food delivery trends to watch in 2024.

Biofuel – An Alternative to Fossil Fuels in Transportation | G20

Transportation industries are moving towards a greener future through the sustainable use of biofuels like Ethanol — discussed in the G20 2023 summit.

Top 10 Navigation Apps for Android and iOS | 2024

Discover the 10 best navigation apps in 2024 that offer personalised navigation just like Sherpas (experienced guides of Himalayan terrain) do.

What are Thematic Maps? Types, Applications And Advantages

Maps have come a long way, and their usage has gone beyond just navigating distances. Thematic maps are now being used to interpret data, gain information, etc. 

From a Bachelor Pad to a Multinational Firm: Tracking TrackoBit’s 5-year Journey

“It’s when ordinary people rise above the expectations and seize the opportunity that milestones truly are reached.” – Mike Huckabee

Stay Updated on tech, telematics and mobility. Don't miss out on the latest in the industry.

Thank you for reaching out! We'll speak to you soon.

In the meantime, why not find out more about us, explore our products, or visit our blog?

Cookie Consent

We use cookies to enhance and personalize your browsing experience. By continuing to use our website, you agree to our Privacy Policy.

• Graph Theory

Travelling Salesman in a Grid

The travelling salesman has a map containing m*n squares. He starts from the top left corner and visits every cell exactly once and returns to his initial position (top left). The time taken for the salesman to move from a square to its neighbor might not be the same. Two squares are considered adjacent if they share a common edge and the time taken to reach square b from square a and vice-versa are the same. Can you figure out the shortest time in which the salesman can visit every cell and get back to his initial position?

Input Format

The first line of the input is 2 integers m and n separated by a single space. m and n are the number of rows and columns of the map. Then m lines follow, each of which contains (n – 1) space separated integers. The j th integer of the i th line is the travel time from position (i,j) to (i,j+1) (index starts from 1.) Then (m-1) lines follow, each of which contains n space integers. The j th integer of the i th line is the travel time from position (i,j) to (i + 1, j).

Constraints

1 ≤ m, n ≤ 10 Times are non-negative integers no larger than 10000.

Output Format

Just an integer contains the minimal time to complete his task. Print 0 if its not possible to visit each cell exactly once.

Sample Input

Sample Output

Explanation

As its a 2*2 square, all cells are visited. 5 + 7 + 8 + 6 = 26

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website

The Traveling Salesman Problem and Its Variations pp 1–28 Cite as

The Traveling Salesman Problem: Applications, Formulations and Variations

• Abraham P. Punnen 5  

7885 Accesses

27 Citations

Part of the book series: Combinatorial Optimization ((COOP,volume 12))

The traveling salesman problem (TSP) is to find a routing of a salesman who starts from a home location, visits a prescribed set of cities and returns to the original location in such a way that the total distance travelled is minimum and each city is visited exactly once. Although a business tour of a modern day traveling salesman may not seem to be too complex in terms of route planning, the TSP in its generality represents a typical ‘hard’ combinatorial optimization problem.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Unable to display preview.  Download preview PDF.

Author information

Authors and affiliations.

Department of Mathematical Sciences, University of New Brunswick-Saint John, New Brunswick, Canada

Abraham P. Punnen

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Royal Holloway, University of London, UK

Gregory Gutin

University of New Brunswick, Saint John, Canada

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer Science+Business Media, LLC

About this chapter

Cite this chapter.

Punnen, A.P. (2007). The Traveling Salesman Problem: Applications, Formulations and Variations. In: Gutin, G., Punnen, A.P. (eds) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, vol 12. Springer, Boston, MA. https://doi.org/10.1007/0-306-48213-4_1

Download citation

DOI : https://doi.org/10.1007/0-306-48213-4_1

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-44459-8

Online ISBN : 978-0-306-48213-7

eBook Packages : Mathematics and Statistics Mathematics and Statistics (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Interview Q

DAA Tutorial

Asymptotic analysis, analysis of sorting, divide and conquer, lower bound theory, sorting in linear time, binary search trees, red black tree, dynamic programming, greedy algorithm, backtracking, shortest path, all-pairs shortest paths, maximum flow, sorting networks, complexity theory, approximation algo, string matching.

Interview Questions

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

• United Arab Emirates
• Switzerland
• The Netherlands
• Puerto Rico
• United States
• New Zealand
• ➨ Choose from World Map
• Budget Travel
• Family Travel
• Getting Around
• Visas & Passports
• Work with Us

Browsing Category

• Czech Republic
• Saint Martin
• Uncategorized

Moscow Travel Guide: Best Things to Do + More [2023]

· everything to know about visiting moscow, including the best things to do and how to get around. ·.

Moscow is Russia’s vibrant capital city, and it also happens to be the largest city in all of Europe. The city’s long and infamous history makes it one of the most unique places we have ever visited.

The architecture ranges from centuries-old palaces to uniform, gray concrete buildings. The people range from cold and private to warm and welcoming. Moscow is a city is strong juxtapositions, and we learned a lot during our time there.

This post will break down all you need to know about visiting Moscow, including the best things to do, how to get there, how to get around, and more.

The Best Things to Do in Moscow

1. explore the red square.

The Red Square is the heart of Moscow. Most of the city’s top attractions can be found here, including just about everything on this list. The Kremlin, St. Basil’s Cathedral, and Lenin’s Mausoleum are all located here, and the State Historical Museum and GUM are not far from here, either.

The Red Square is a common home for parades, protests, and seasonal celebrations. There are massive Christmas celebrations here, with food vendors and carnival rides set up in numbers.

2. Check Out the Ziferblat

The Ziferblat is a café in Moscow that is unlike any café we have ever been to. While most cafes charge you for your drinks and food, the Ziferblat charges you for your time.

Upon arrival, you are given a clock. When you leave, the barista calculates how much time you spent in the café and charges you accordingly. This concept was created to help visitors to be more intentional with their time, and the cafe itself is incredibly charming.

For a detailed look at everything you need to know before you visit, make sure you read my post about visiting the Ziferblat Cafe in Moscow .

3. Marvel at St. Basil’s Cathedral

St. Basil’s Cathedral is one of the most iconic churches in the world, and it was the single thing we were most excited to see while in Moscow. Built almost 500 years ago, St. Basil’s Cathedral is recognized by its colorful domes and whimsical style. The church is of the Russian Orthodox faith, and the inside is just as wondrous as the outside.

St. Basil’s Cathedral is located on the edge of the Red Square, making it incredibly convenient to visit. Entrance for non-worshippers costs 800 rubles, and tickets can be bought at the church

4. Explore the Kremlin

The Kremlin is the largest active fortress in Europe, and it is the site of most of Russia’s government affairs. In addition to government buildings, the Kremlin Complex is filled with courtyards, towers, and museums that are open to the public. If you have the time, you could spend a couple of days fully exploring all that there is to see in the Kremlin.

5. Walk Through Lenin’s Mausoleum

Vladimir Lenin is one of the most important figures in Russian history, and his body is located perfectly embalmed in a mausoleum in the Red Square. The Mausoleum is open to the public to visit, and as long as you are willing to go through a few security checks, it is easily one of the best things to do in Moscow. Its convenient location in the Red Square makes it a can’t miss attraction.

There is absolutely no photography allowed inside the Mausoleum. Do not test this rule.

6. Wander Along Arbat Street

The Arbat is a very popular street in Moscow that is lined with stores, cafes, and other touristy attractions. It is one of the oldest streets in the city, dating back to the 1400s. This street is both quaint and trendy, and there are many walking tours that introduce tourists to the neighborhood’s wonders and highlights.

7. Catch a Show at the Bolshoi Theatre

As a lover of the arts, it is hard to think of Moscow and not think of ballet. Russia has always been a top dog in the world of fine arts, and Bolshoi Theater is one of the best places to catch a performance. We were lucky enough to attend an Opera here, and it is a venue that you don’t want to miss out on if you enjoy opera, ballet, or orchestral performances.

8. Visit the State Historical Museum

The State Historical Museum is one of the most respected museums in Moscow. Despite its name, it is not really focused on the history of Russia as a nation. Rather, it contains a collection of artifacts from all throughout Russia’s history.

The museum’s collection is very broad in nature. It houses some items from indigenous tribes that used to occupy the region, pieces collected by the Romanov family, and more.

9. Wander Around GUM

GUM is an absolutely massive mall within walking distance of the Red Square. It isn’t just the size that draws visitors here; it’s the sense of luxury. The mall is so beautiful inside, much like the metro stations.

While visiting a mall might not sound like it belongs on a bucket list, this mall does. You will not want to miss out on visiting GUM while in Moscow.

10. Admire the Cathedral of Christ the Saviour

While St. Basil’s Cathedral is the most iconic church in Moscow, it isn’t the only one. The Cathedral of Christ the Saviour is absolutely stunning, with massive golden domes. It is the tallest Orthodox church in the world, and it is the seat of the Orthodox Patriarch of Moscow.

It is located just about a mile from the Red Square, just south of the Kremlin Complex. You can walk to it from the Red Square in about 20 minutes.

How to Get to Moscow

Flying to moscow.

Moscow has three major international airports: Sheremetyevo (SVO) , Domodedovo (DMO) , and Vnukovo (VKO) . All three of them are directly connected to downtown Moscow by the Aeroexpress trains, which leave every 30 minutes throughout the day. By Aeroexpress train, you can expect to get to the city center in 25-45 minutes depending on the airport that you fly into.

Sheremetyevo is the biggest and busiest of the three airports, and it is the one you are most likely to fly into – especially if you are coming from outside of Europe or the Caucus region. We flew into Sheremetyevo on a direct flight from New York City.

I usually provide backup airport options, because flying right into the city isn’t always the cheapest way to get where you’re going. Unfortunately, when it comes to Moscow, don’t really have a choice other than to fly right into Moscow. It is a very remote city, and it is usually the cheapest place to fly into in Russia as a whole.

Since Sheremetyevo is so busy, you will probably find a great flight option anyway. I wrote in  my post about finding cheap flights  that using hub airports will lead to more affordable airfare, and the same logic applies here. Even though Russia’s national airline, Aeroflot, is no longer a member of the SkyTeam Alliance, Moscow is still a major hub connecting passengers from all over the world.

READ OUR CHEAT SHEET

Train or Bus to Moscow

Trains and buses are one of the most popular ways to get around Europe. However, they’re of very little use when you’re trying to get to Moscow.

Moscow is hundreds of miles from the nearest major cities. The only major European city that can even be reached within 8 hours on the ground is St. Petersburg, and even the Baltic capitals of Riga, Vilnius, and Tallinn are over 12 hours away.

If you want to get to Moscow, the best option is almost always to fly. While the train routes to Moscow are scenic, they simply take forever.

How to Get Around Moscow

METRO | TROLLEYS | TRAMS | BUSES

Moscow has one of the most memorable metro systems in the world. Its metro lines are very deep underground, and the stations are absolutely stunning. Each station has its own unique style, but all of them contain escalators that seem to go on forever.

The system was built in an effort to showcase the power of the Soviet Union and its bright future. The plans were a form of propaganda, but they resulted in what is still one of the most visually appealing subway systems on earth.

Moscow’s metro system isn’t just pretty. It is also very useful and accessible. The system has 17 lines that connect the city and its surrounding area.

But wait; there’s more!

The Moscow metro system is also incredibly affordable, with each ride costing less than a dollar. The metro is by far the best way to get around Moscow, as it is almost impossible to beat the connection times and the low cost to ride.

Tickets can be bought at electronic, English-speaking kiosks in stations, or directly from ticket counters at certain larger stations. There are also day passes available, which are a very solid option if you plan on riding the metro several times per day.

The metro is by far the best way to get around Moscow.

In addition to the metro system, Moscow also has a network of buses, trams, and trolleys. This system is nowhere near as convenient or well-connected as the metro, though, and is likely of little use to you during your trip. There is no Uber in Moscow, but a similar app named Yandex is available if you need a ride in a pinch.

How Many Days Do You Need in Moscow?

Moscow is the biggest city in all of Europe, and it is absolutely loaded with things to do. You could spend weeks in Moscow and still find new things to do. Of course, most travelers don’t have that kind of time to spend in one place!

I recommend spending no less than three full days in Moscow, and ideally closer to five or seven.

Moscow is very spread out, and it can take some time to get from one major point to another. There are also so many places that are nice to just sit back and relax, which is hard to do when you’re in a hurry trying to cram activities into just a few days.

If you only have a week to visit Russia, I’d advise spending all of the time in one city. If you decide to split your time between Moscow and St. Petersburg, I recommend not trying to squeeze in any day trips beyond those two cities.

When Is the Best Time of the Year to Visit Moscow?

There are two different ways to approach this question. Personally, I think the best time to visit Moscow is around Christmas and New Year’s Day. While the weather will be absolutely freezing, Moscow is a surreal winter wonderland in December and January.

We were in Moscow right before Christmas. While it was very cold, you can always bundle up. Exploring the Christmas markets and pop-up ice skating rinks throughout Moscow is one of my favorite memories from anywhere I’ve traveled, and I dream of going back to do it again.

If you aren’t fond of the cold, Moscow is beautiful in the summer. It tends to get pretty cold in the shoulder seasons, so if you want warm weather, you should plan to visit in the summer. Moscow actually gets pretty warm in July and August, and there are a bunch of fantastic places to soak up the sun within the city.

The best time to visit Moscow is either around Christmas or from late May to August.

Is Moscow Safe to Visit?

While Moscow is a truly wonderful city, there’s no denying that visiting Russia comes with risks. As the country is run by an infamous communist dictator, concerns about visiting are valid. While we didn’t experience any sort of threat or negative treatment during our time in Moscow, we visited in a peaceful time.

In our experience, Russia doesn’t seem to detain normal Americans or Westerners to use as pawns. As a regular person, as long as you don’t commit any crimes, there is a slim chance you will run into any issues. However, Russia will not hesitate to enforce its laws against foreigners, and illegal behaviors will likely land you in a very compromising position.

Russia will not hesitate to enforce its laws against foreigners, and illegal behaviors will likely land you in a very compromising position.

To make matters worse, Russia has a bad reputation for gang violence. While the Russian mafia has very little interest in normal Western tourists, they won’t hesitate to pick a fight with anyone who ventures into their sphere of influence. If you seek out illegal substances or activities, you could be a target of the mafia.

If you seek out illegal substances or activities, you could be a target of the mafia.

Finally, since Russia’s invasion of Ukraine, things are all very different. Russia is currently at war, and there are battles raging within 8 hours of Moscow. While it is still relatively safe to visit, that could change at any time as the war with Ukraine continues.

Is Moscow Worth Visiting?

Without a doubt, Moscow is worth visiting. It is one of the most unique major cities we have ever visited, and we hope to make it back one day. The Russian Orthodox churches are stunning, the city’s history is unlike any other, and the food is to die for.

While many visitors prefer St. Petersburg to Moscow, I think Moscow deserves a lot of hype of its own. Moscow is the beating heart of Russian culture and history, and it’s a place I highly recommend checking out if you have the chance.

That’s all we have for you about Moscow! I hope this post was helpful as you plan your trip to Russia’s capital.

Have you been to Moscow? Or is this your first time visiting? Comment below if you have anything to add to our travel guide!

Hi, I'm Greg. I'm an avid traveler who has traveled to over 50 countries all around the world with my wife and kids. I've lived in Italy, Mexico, China, and the United States, and I dream of moving abroad again in the future. With this blog, I provide my audience with detailed destination guides to my favorite places and pro-tips to make travel as stress-free as possible.

Leave a comment

Save my name, email, and website in this browser for the next time I comment.

Meet The Author - Greg

Recent Post

How Much Does a Trip to Egypt Cost: Budget Breakdown

March 10, 2024

Best Time to Visit the India Gate in Delhi [2024]

March 1, 2024

Flying with a Sinus Infection: Tips to Avoid Pain

February 20, 2024

11 Best Things to Do in Breckenridge Besides Skiing

February 12, 2024

10 Best Beaches in Mexico for Families (We Lived Here)

February 3, 2024

Come with me on my travels, as you plan yours

11 Things You Need to Know Before Moving to Moscow, Russia

This post contains affiliate links. That means I may earn a small commission at no extra cost to you, if you buy through my site. I appreciate your support of my site.

Despite all the places I have visited during and after my time living in Moscow, everyone wants to know what is it like to live in Russia. When I accepted a teaching job at an international school in Moscow I knew very little about the country. Of course I did some research, but the United States presents a very skewed view of life in Russia today. Moving abroad is always an emotional experience, but anyone from the USA planning on living and working in Moscow might be surprised about what is and isn’t a challenge in Russia.

After a year living in the country I can say that I didn’t love living in Russia, but I did love the new cultural experience. I already wrote about what it is like to live in Russia in general. In this post I go into the logistics and details of moving to and living in Moscow, Russia.  If you are debating whether or not you should move to Moscow, Russia here are 11 things to know before you pack your bags.

1. The Visa Process is a Hassle

When I was living in Moscow I came across an article about the hardest visas for US citizens to obtain. Russia was one of the top five. Go figure, I decided to move to Russia!

The US embassy website says it best, “The Russian government maintains a restrictive and complicated visa regime for foreigners who visit, transit, or reside in the Russian Federation.” I may not agree with the US government on a lot of things, but they are correct on that!

A Russian-based sponsor is always required in order to obtain a visa. I’m not going to go into details on the process, that could be a whole different post. It’s unlikely that you could move to Russia without a work/school sponsorship, so your new employer/school should help you through the steps. Before accepting a position that is something to check into!

After receiving sponsorship and your invitation letter you will need to apply for the visa and get an HIV test done. Be aware it needs to be the formal blood drawn test that gets sent to a lab and not just a finger prick instant test. I found that out the hard way!

2. Registration is Required Every-time you Return to Russia

Within a specific period of time when returning back to Russia from another country you or your company needs to register you using the migration card you are given at customs. For most of my time in Moscow this was within 3 days, during the World Cup this needed to be done within 24 hours. One guy from my school did not give his migration card to HR within the required amount of time and had to leave the country and then immediately return in order to avoid issues. 

You will need your migration card in order to leave the country. Needless to say keep it in a safe spot!

3. Documentation Needs to Be Carried at All Times

When walking the streets of Russia you need to carry your papers at all times. This includes your passport, visa, and migration card. A police officer can ask you for these for no reason and you can be detained if you do not have them on you. According to the HR department at my school you can also have an officially stamped copy of your passport and visa instead of your originals.

4. The Cost of Living is Low

If you are coming from the USA or Western Europe you will most likely find the cost of living low. My phone bill was about $15 a month and my internet was about $20 a month. I had a monthly membership at one of the nicest two story gyms with various classes and a pool for $58 a month. Taxis cost only a few dollars for 10 – 20 minute rides. Overall if you compare costs to what you paid back ‘home’ you will be pleasantly surprised.

Retail shopping was the one thing I found more expensive than in other parts of Europe or the US. The prices of both familiar worldwide brands and unfamiliar Russian brands seemed pricier. Coming from NYC I didn’t think the restaurants were too expensive, but many of my colleagues thought they also had higher prices.

5. Bill Paying is an Odd Process

It took me awhile to figure out how to pay my phone and internet bills. In the US I always had a set monthly fee due on a specific date. I could easily set up bill pay. In Moscow the way I found out that my phone and internet bill was due was when they stopped working. For my internet I wouldn’t be able to use it on a random day and had to enter my credit card information to pay for the next month. Without having access to the internet to translate this page I had no chance of figuring out the form correctly. Not to mention, it was a guessing game of figuring out how much I owed. Initially I was confused about the conversion rates so I didn’t even know in the ballpark what monthly internet cost.

Oh my goodness did I struggle with my phone in Moscow! The data wouldn’t work. Sometimes it was because I had to ‘top up’ my payment. Similar to the internet, I didn’t know how much I owed or when. There was some other issue with my phone that took three visits to the phone store with Russian colleagues to resolve. I still don’t know what the issue was because according to my co-worker who translated I would have to pay for them to tell me what they had to fix on my phone. I didn’t have to pay for them to fix it, but I would have to pay if I wanted to know what they fixed??? Welcome to life in Moscow! 

I loved how cheap internet and phone service was, but sometimes I wished I could pay a little more just to simplify using them.

6. Many Online Sites are Blocked

Internet and WiFi in Moscow usually work really well. That is unless the site is blocked. Some sites you would never guess would be blocked like Target.com. I found many American online store websites blocked. Also many important financial sites are blocked. M y US bank’s entire website was blocked online, as well as my credit card company. TV shows direct from the networks are often blocked. No watching American Ninja Warrior on NBC or Amazing race on CBS. Hulu is also blocked. Your best bet is through youtube.com or VPN blockers. 

7. Transferring Money is Not Fun

My school set me up with Raiffeisen Bank. It worked well except for when I needed to transfer money. As I mentioned above my bank (Capital One) couldn’t be accessed online and wouldn’t except transfers from Russia. Before moving to Russia make sure you have a bank back home that you can transfer money to if you plan on doing that. It was very difficult to set up once out of the country. Luckily my parents set up a Chase account that was able to except money from Russia. They then transferred the money to my US bank account.

8. Hardly Anyone Speaks English

The hardest part of all the challenges I have listed above is that most people don’t speak English. It’s one thing being a tourist and trying to communicate at an attraction while traveling. It’s another thing to attempt banking, bill paying, grocery shopping and everything else that living and working in Moscow entails. 

Some Russians speak a little English in the city center, but don’t count on it. In other outlying neighborhoods, like mine, it was rare that someone spoke English. I had so many experiences when people would just speak more Russian to me when I didn’t understand. Unlike a lot of countries that attempt to put more things in English for tourists, Russia seemed to have the attitude of, it is your problem, figure it out. 

Have Yandex Translate or Google Translate at the ready if you don’t speak Russian. Also set your web browser to translate web pages into English.

9. Learning Russian is Hard

I knew that learning Russian would improve my life in Moscow a great deal. If you know me personally, you know I am a pretty persistent person. If I set my mind to something, I will do it…..except for learning Russian . My Russian teacher would say a word and I couldn’t remember it two seconds later to repeat it. To be fair I did learn the alphabet, how to count to ten and a few greetings and other nouns.

10. Getting Around Moscow is Easy

The Moscow Metro is very nice, cheap and easy to use. It follows the same basic system of metros around the world. If you are considering learning Russian start with the alphabet, it will help you use the metro. Not all the stops and stations are in English. Have a metro map downloaded on your phone in English. You can use it to help you figure out the stop names in Russian. The metro runs from about 5:30am to 1am.

I took the metro whenever I could, but on off hours, going to the airport or when traveling somewhere not on a metro line I used Yandex taxis . They are the Uber of Moscow and very cheap. Most drivers don’t speak English, so this is a good time to have a translator app handy.

11. Hot Water is Shut Off for 10 Days Every Year.

Between May and August almost all of the apartment buildings have an assigned 10 days when the hot water is shut off for maintenance. You can check online at Oaomoek to see when it will be shut off for your apartment building. If you have a new building you may not have to deal with this (most buildings are old though). 

As an American moving to Moscow, Russia I definitely had an adventure! If you have moved to Moscow let me know in the comments below what your experience has been like. Feel free to leave any questions about moving to Russia below as well. 

More About Russia

• Moscow Things to Do: The Must See Sights , Unique Things to Do ,  Spartak Stadium
• Moscow Markets:  Izmailovsky Market , Danilovsky Market
• Moscow Museums: Moscow City Museum , Victory Museum , Museum of the Patriotic War in 1812 , State Historical Museum ,
• Moscow Life: Malls , Christmas in Moscow , Metro , Learning Spanish , My Russian Apartment , What is Life Really Like in Russia , FiFa World Cup , Russian Winters , and more posts about life abroad in Russia .
• St Petersburg: City Guide , The Hermitage Museum , Kayaking the Rivers & Canals , Peterhof Palace

Share this:

• Click to share on Pinterest (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Twitter (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on Tumblr (Opens in new window)

You May Also Like

What is it Like to Live in Russia?

Oh so very lost, all the time – 9/27/17.

Russian Winters

33 comments.

The hot water thing happened to me while living (and teaching english too) in Prague! I had no idea that was a thing! Luckily it was for 3 days.

Interesting, I didn’t know it happened in other countries too!

Thank you for such a great article! Moving to a new country is always a stressful process no matter how prepared you are and knowing these little ins and outs of the process really helps. Having to get an HIV test before moving kind of surprised me and registering every time you return to Russia seems like a hassle! I have heard that Russian is a very difficult language to learn. I tried learning the basics when I was travelling through Eastern Europe and the Balkans and almost immediately gave up because I found it incredibly difficult to teach myself from free online resources. I’ve heard that Moscow has some of the most beautiful metro stations in the world and would love to see them one day!

You’re welcome, thanks for reading! I’m terrified of needles, so I really hated having to do an HIV test. Also we had to do them a couple times of year at the school I worked at. I found Russian really hard to learn when I had a private teacher. I can imagine it would be even more difficult to try to teach yourself. Yes, the metro stations are beautiful!

Tell me about it (the visa progress, internet, hot water shut off!), I lived for a while in Moscow many years ago and the paperwork was a nightmare and by the sounds of it, nothing has changed. I learnt Russian pretty fast (had no choice) but I did enjoy my time there. Would I go back? Maybe….

It’s great to hear from someone else who lived in Moscow! That’s awesome that you learned Russian really quick, I’m impressed!

I had heard about a lot of things about Russia and turns out most of them are true! They have this strictest Visa process and paperwork. One of my acquaintances arrived in Russia after visiting some other Central Asian countries. He was apparently deported with no proper reason. He was told if you want to visit Russia, come directly from your country and not through any other country! It was good to know a lot about Russia and Moscow in general from your blog. I hope you had a good and exciting time there.

Oh wow that’s quite the scary story! I traveled to other countries quite a bit when I lived there and luckily didn’t have any problems going back to Russia.

First off – kudos for having managed in this city. It does seem like a challenge to get here and more importantly stay here. The amount of documentation and forms. And to not be able to pay your bills in a jiffy. Oof! Russian only and no English can be hassle if you are staying there for long term. The last point totally put me in a bind – no hot water for 10 days in a cold country! Brrrr….

Hahaha the visa the visa the visa!!!! I was had planned for my trip in December 2019… The hardest part was figuring out how to get an invitation letter when staying at an Airbnb. That took me quite a while to figure out and was a bit costly about $65 but the Airbnb was affordable so the costs balanced out. On arrival don’t be in a hurry, it took about 3 hrs to be cleared at immigration as a first time tourist to Russia. But once that was done i really enjoyed my stay. I love how beautifully decorated it is in December and the fireworks on 31st. Being an African I was a tad cautious but boy are those people kind and friendly… I got so many hugs and numerous people eager to find out more about what I think of Russia and where I’m from. I’d definitely go back. Oh and I visited Voronzeh by bus… Small nice and really affordable town but not as much to do as Moscow though..

The Fearless Foreigner

The visa process and the invitation letter are quite the hassle. Glad you had a good experience in Russia overall though!

This really opened my eyes to some of the things we take for granted in the US, like consistent WiFi, phone service and hot water. And paying bills sounds as though it would be very frustrating. As someone who has a tendency to misplace things, I was relieved to hear an officially stamped passport and visa copy would be accepted. Imagine losing the originals? Ugh. All worth it, I’m sure, to have this incredible opportunity to experience Russia as a resident. These tips are very helpful and I do hope to visit in the near future. Thank you!

That’s so true, we do take a lot for granted in the US. Moving to Moscow was a challenging experience, but still rewarding!

Sheriannekay

I am hoping to visit Moscow in the fall. I know it won’t be my easiest trip and have put off research. This is a great starting point. The tips for apps are greatly appreciated. I didn’t realize language would be as huge a barrier as it sounds so I will do extra prep. Thanks for the heads up on carrying papers with me at all times, I don’t usually do that

As a tourist you will hopefully have an easier time with the language barrier and your hotel will send you the invitation letter to start the visa process. It still is a hassle and takes more planning than other countries though. I have several other Moscow posts, I hope you check them out and let me know if you have any questions!

Most of the “rough” things mentioned are truly in the eye of the beholder – and a matter of simple adjustment. WI-FI is a lot more consistent and readily available in Russia’s big cities than in cities of comparable size in the US. As to cell phones – the vast majority of plans is “prepaid” vs “pay-as-you-go”, which essentially means you can hypothetically run out of money. That said, internet banking is a lot more developed in Russia – so “topping up” your phone is a matter of a couple of clicks on your phone (or, alternatively, and “auto-payment” from your bank account as soon as you hit a certain limit). Back in 2018, I went for 7 days in Moscow and Spb without any cash or credit cards at all – paying for everything with my phone (Samsung Pay, Google pay, etc).

Hot water – yes, that’s something I had a hard time getting used to. Luckily, most rental apartments have a back up water boiler (or in-line water heater) to help you through those 10 days 🙂 If not – you can always get one (costs about $70, no electrical license or skills needed to install – it’s a simple plug and play. Plug and shower, rather 🙂

As to visa – well, yes, it’s a bit of a pain. To give you some perspective, though – the wait times for a (mandatory) visa interview at the US embassy in Moscow back in 2018 started at 1 year (yes, that’s 365 days), and Russians have to travel to the US embassy, regardless of where in the country they reside. If they happen to live, say, in Petropavlovsk, they need to fly into Moscow (a 9-hr flight across 9 time zones)

Linda (LD Holland)

Wow! A move to Moscow is certainly adventurous. I know that visiting requires a whole big process. So I am sure residency is a degree of magnitude harder. I am not surprised that internet is blocked. But the process for paying bills is just bizarre. And I am not sure how to deal with no hot water for 10 days. Some great tips for people wanting to do a longer stay in Russia.

Moving to Moscow was an adventure! Some people tough it out and take cold showers for 10 days. I heated up some water and took showers at my gym some days.

Bhushavali N

Oh wow! That’s quite an experience. Language barrier when you move to a country is indeed difficult, unlike being a tourist for a few days. I know that feeling, coz I’ve been through that! Interesting to know that the cost of living is cheaper than USA or EU! I wonder if the situation of money transfer is difficult only with banks of USA or with any other country! Just like China, I’m not surprised that many sites are blocked in Russia as well!

Most of my co-workers were from the UK or other countries around the world. I talked with them about the money transferring and none of them seemed to have any problem. So I guess it is more of an issue with US banks!

Victoria immigration expert

Thank you for sharing your experience. This is very valuable. I think it is the language barrier that causes many inconveniences. Good luck to you!

Yes, the language barrier was one of my biggest challenges! Thank you.

I loved reading this! I am SO curious about Russia right now. It’s somewhere I really really want to go but as you mentioned, the visa process is a bit tricky. It’s just such an unknown place to me, I don’t really know anyone who has been there. I think it’s very cool that you taught English there! I appreciated your honestly about how you didn’t technically love it nor hate it, it seems like there were many challenges but a great experience overall!

Russia is an interesting place! It is a hassle to get a visa, but if you are intrigued you should visit! It’s unique because it is Europe, but doesn’t feel like the other European countries, yet doesn’t feel like Asia either. Let me know if you have any questions about visiting!

Anton Vasilyev

Just read your article and having traveled to Russia multiple times I think you made it sound a bit too complicated. First, the visa issue – Google an online Russian visa support site and they will do it for you for a modest fee. You all seem to mention that 7- 10 day hot water maintenance. It does take place in the middle of the summer so it’s not that dramatic. When searching for an Airbnb make sure it comes with a water heater. That way you don’t depend on centrally supplied hot water. Most local apartments come with a tankless water heater installed to avoid this exact situation – just ask. And I’ll just ignore your other complaint that English is not widely spoken in Moscow. I actually enjoy that there are not that many English speaking tourists in Moscow and St Petersburg.

Living in a country and traveling in a country is very different.This post is geared to expats moving to Russia and people who like to know all the pros and cons of moving somewhere, even if they are minor inconveniences. For the most part our companies choose where we live and we have no control over the apartment (no AirBnBs). That’s great that you enjoy that many people do not speak English. As I said that is the point of this post, for people to determine if they would like to live in the country or not. Anything that does not pertain to your situation or needs you are free to ignore!

Hey Elizabeth! I came across your blog after participating in the collab about teaching abroad, with Monica from This Rare Earth! I resonated with what you said here — many of the same things happen in China where I work. It is definitely an adventure 🙂

Thanks for stopping by! That’s very cool that you are teaching in China! I’m sure there are a lot of similarities….teaching abroad is an adventure for sure 🙂

It was interesting to read, so let me give you Russian point of view. As for visa, I really can not understand what’s the purpose of such hassle – if I was responsible for Russian visa policy, I would make visa-free regime for the majority of countries. We had quite nice experience during the World Cup 3 years back, so I hope things will be changing. Even now, they introduced new e-visa policy, at least for various European countries. However, they always state that all visa policies should be reciprocal, though it doesn’t make sence for me at all. As for passports I strongly disagree with you – you don’t need to carry it all the time, at least in Moscow. It is not required by law and normally no one will ask it as well, at least if you’re not looking like people from Caucasian & Central Asian republics. Attitude towards foreigners from “rich countries” from police is mostly much better, than towards any Russian. As for internet, it amazes me that you found it problematic. Wi-Fi is all over Moscow, Apple Pay can be used almost everywhere, and the unlimited internet package I have on my tablet is less than 10$ per month – i never found anything like that in other countries, though I am travelling a lot. As for blocked sites – there are some, but target.com is blocked not by Russians, but by target.com itself, because it does not accept our cards and doesn’t provide any services to us. Absolutely same situation applies to Ukraine – you will not open it there either. However, absolutely nobody in Russia uses and even knows about that site, we use other websites for shopping, both local and international. In general, we use local sources – we have our analogues of Facebook, Netflix, Spotify etc, and in some cases they are really much more convenient. In general I am happy to read you report – visit us again!

Thanks for reading and sharing your thoughts!

Thank you for sharing so many details living in Moscow ,and i am gald that i have read this article before i go to Moscow ,yes i will study in Moscow for few years and i don’t know what is the life will be there ,i am nervious and at mean time don’t know if it is right for me to live in Moscow ,because i know they have low salary too ,so maybe it’s hard for a student to find a good part time job,anyway ,i will start to my life in Moscow soon,hope everything will go smoothly,thank you for sharing this again!

You’re welcome! I hope you enjoy your time in Moscow.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Notify me of follow-up comments by email.

Notify me of new posts by email.