Travelling Salesman Problem : Its Definition and Implementation

Travelling Salesman Problem : Its Definition and Implementation

Travelling Salesman Problem – The ability to determine the best sales route remains a challenge for sales until now. Some maps software  is still perceived as less useful when it comes to mapping out how salespeople can return to their starting point one way.

Due to maps software limited functionality, it does not optimize routes when more than one intersection is encountered, and it does not assist in other sales processes.

One solution that can be used by business people to deal with those issues is by using Travelling Salesman Problem. 

Get to Know Travelling Salesman Problem 

image via wikipedia

Traveling salesman problem, or TSP, is about finding the best route to reach a given destination given a set of specific destinations.

TSP was first introduced in the 1930s by Karl Menger, a mathematician, and economist. Menger called it the “Messenger Problem,” a problem faced by lettermen and many travelers.

To more easily understand TSP, consider the example below.

A salesperson wants to visit several locations to offer their product. He knew the name of the area and the distance between each house.

TSP tried to answer the question about which shortest route the salesperson had to take so that he only visited each location once before returning to his starting point.

Challenges Faced By Sales

A variety of routes are available, but selecting the best one that costs a little and takes only a short distance is not easy.

According to Roitific, there are more than 300,000 permutations and combinations of departure and departure routes with 10 destinations, whereas with 15 destinations, 87 billion routes are possible.

Without using the shortest route, sales will take a lot of time to get to their destination, not to mention if you encounter various routes,  if you fail to choose an efficient route, the result will increase the company’s operational costs.

The importance of Travelling Salesman Problem for Sales

In most cases, every salesperson already follows a schedule, but sudden client appointments do happen from time to time.

As a result, sales teams generally work irregular hours and sometimes have to travel long distances to meet with clients. In some cases, they miss valuable business opportunities due to taking the longer route.

Traveling salespeople have an important role in avoiding these things. As explained above, TSP is useful for finding the shortest route to several cities or destinations and returning to the first place.

Here are some solutions that are often used for the salesman problem;

The Brute-Force Approach

The Brute-Force approach or also known as the Naive approach is to calculate and compare all possible permutations of routes to determine the shortest route solution.

By using this approach, businesses need to count the number of routes, draw them, and make a list of all possible routes. Calculates the distance of each route and then chooses the shortest one.

 

The Branch and Bound Method

Using this method, the problem to be solved is divided into several sub-problems. Business people must decide on a departure or node and then move to various destinations.

Choose the easiest arc between the unvisited and current point and then add the distance to the current distance.

Repeat the process until the current distance is less than the limit. If that happens, the result will be displayed.

 

The Nearest Neighbor Method

The last method is the Nearest Neighbor. The key to this method is always to visit the closest destination first and then return to the starting city when all the towns have been visited.

The way to use this method is to select a city randomly, then look and find the nearest city that has not been visited and go there. After sales have visited all cities, sales must return to the city of departure.

The Implementation of Traveling Salesman Problem

As an example, TSP can be used for last-mile delivery, which involves delivering products from a depot or warehouse to the customer.

The last-mile delivery takes up a lot of shipping costs, approximately 28 percent. Companies usually bear these costs so they can compete.

However, the fact is that the company’s last-mile delivery costs an average of $10, or Rp. 150,432, but customers only pay an average of $8 or Rp. 120,346.

This is why businesses want to minimize the cost of last-mile delivery. The cost reduction is using the Vehicle Routing Problem. VRP itself is a general version of TSP.

Its primary function is to find a set of routes to reduce shipping costs. The problems usually involve one set of depot locations, hundreds of delivery locations, and several vehicles.

Route Planning for Salesmen with LOKASI Enterprise 

One of the keys to the company’s success is route planning. The more efficient the route you have, the faster the field sales will arrive at their destination.  As a result, you will spend less time driving the vehicle and more time working.

Our platform, LOKASI Enterprise, can help businesses analyze and find the best and most efficient routes for salesmen. By doing this, businesses can save on shipping costs, increase customer satisfaction, and save on operational costs.

Learn more by contacting [email protected] or WhatsApp on 087779077750

Related Posts