Introduction

Welcome back to the blog of the Nexus Analytics Consulting Group! In this entry, we will be introducing the Traveling Salesman Problem (TSP), a common logistics and optimization problem, and illustrate how to solve it using a fun example. This article aims to increase awareness for the TSP and its applications with the hopes that more organizations adopt optimization techniques like these to solving problems.

Background

Suppose that Nexie, a very hungry analytics consultant, wants to go on a food trip. In particular, she wants to try out the top restaurants (as rated on zomato.com) near the office of Nexus Technologies. She brought along her magic carpet, allowing her to traverse the shortest straight-line distance between two restaurants. However, due to carpet safety and budget constraints, she has imposed the following restrictions:

- Any restaurant visited must be within 5km from the Nexus office
- She has a budget of PhP 2,000

o Note: The amount spent at each restaurant is determined by Zomato’s price estimates (e.g. if a restaurant is labelled as PhP 700 for 2, Nexie will spend PhP 350 at that restaurant)

Given this information, she wants to come up with an itinerary and route map that she can follow. As an analytics professional, she feels that there should be a structured and logical approach to this problem.

Framing the Problem

When deciding how to approach a problem, it is always important to first determine the main objective. For this food trip, Nexie considered three main factors and two decision points to decide on an itinerary:

- Factors

o Restaurant ratings
o Cost per person
o Distance travelled

Combining all these factors, Nexie can ask the question, “How do I visit the best restaurants while spending the least possible amount of money and minimizing the total distance travelled?”

- Decision Points

o Selection of which restaurants to visit
o Order of restaurants in itinerary

When constructing the itinerary, the selection of restaurants to visit will address the ratings and cost factors, while the order of restaurants will determine the total distance travelled.

What is the basis for an optimal itinerary? It is not always possible to find an itinerary that gives the best results for these three factors. The factors themselves have different levels of importance to stakeholders, so each factor can be prioritized or weighted according to priority. This prioritization will depend on the problem context and may even change over time. At the end of the day, the definition of optimal is decided by the stakeholders of the problem.

Fortunately for Nexie, these types of problems are not new. There is a classic problem called the Traveling Salesman Problem (TSP). The problem’s context is as follows:

A salesman needs to visit a set of cities. Traveling from one city to another involves a cost (usually a representation for ticket fare, distance, or time). What is the best way for the salesman to visit all cities and return to his starting point while incurring the least cost?^[i]

The TSP is a very well-studied problem in the fields of mathematics and computer science and has many real-world applications, most notably for transportation, logistics, and routing. In fact, this food trip problem can also be modelled as a TSP once Nexie has selected the restaurants she can go to. In this post, we will help Nexie with her two decision points: select which restaurants to include in her itinerary and use two ways to solve the TSP to determine the order of restaurants that minimizes her distance travelled.

Algorithms

Restaurant Selection

To identify the restaurants that Nexie should visit, we computed for the rating-to-cost ratio (rating divided by cost per person) per restaurant to find out which restaurants give the most “ratings per peso.” We start by getting the top 10 restaurants based on the rating-to-cost ratio within 5km from Nexus. From this sorted list of 10 (see below), we select our top restaurants while maintaining Nexie’s budget constraint of P2,000.

Table 1. Top 10 Restaurants Ranked According to Rating-to-Cost Ratio 

Although the exhaustive TSP guarantees the shortest possible distance, it may take too long to compute. A faster, “greedy” way of getting a route for this problem does not compute for all possible routes; instead, it adds locations to the route bit by bit to form a solution. Although this may not necessarily result in the shortest overall distance, it may arrive at a viable solution much faster than the exhaustive TSP.

There are many kinds of greedy solutions, each with its own procedure for ordering locations. This post will focus on Kruskal’s method, a simple way for finding a route that should come close to the best route.

Kruskal’s method first takes the distance between any two restaurants, places them in a list, and then sorts all those distances in ascending order. It then starts with a pair of restaurants with the shortest distance and connects those restaurants if these two conditions are met:

1. A restaurant can only be connected to at most two restaurants: the previous and next restaurants

2. A subgroup of restaurants should not form a cycle. Note that each restaurant should be visited exactly once. A cycle would leave out some restaurants.

If any of the two conditions are not met, it rejects that pair of restaurants from the list. The algorithm then searches for the next pair of restaurants with the next shortest distance and continues this process until it has formed its greedy path.

The flowchart on the bottom illustrates the process for easier reference.

Figure 1. Kruskal’s Greedy TSP Algorithm Flowchart 

Results

Here are the straight-line distance (in km) between the restaurants in Nexie’s itinerary:

Table 3. Distance Matrix of the Top 6 Restaurants Based on Rating-to-Cost Ratio 

The shortest distance is between The Curator Coffee and Cocktail and Manam (0.38km). Although this pair will be the first pair used by Krukal’s algorithm, the completed route’s starting point is flexible so long as the order of restaurants is followed. Given that, the starting point will then be the restaurant nearest to Nexus Technologies, Inc., which is Purple Oven.

Below are the resulting routes generated by the exhaustive TSP and greedy TSP using Kruskal’s:

Table 4. Resulting Routes of the Top 6 Restaurants with the P2,000 Budget 

 Figure 3. Exhaustive and Kruskal Route for the P2,000 Budget

Fortunately, for our problem, Kruskal’s method produced the same results as the exhaustive TSP. Kruskal’s method ran approximately 48 times faster than the exhaustive TSP, but because both runtimes were in milliseconds, the difference was negligible.

Suppose now that Nexie was promoted and wants to celebrate the occasion. She increases her budget from PhP 2,000 to PhP 3,000 to be able to include two additional restaurants (Gino’s Brick Oven Pizza and Toby’s Estate) using the same selection process used earlier. Will Kruskal’s method still give the same route as the exhaustive TSP in this case?

Table 5. Distance Matrix of the Top 8 Restaurants Based on Rating-to-Cost Ratio 

Table 6. Resulting Routes of the Top 8 Restaurants with the P3,000 Budget 

 Map 1. Exhaustive TSP Route for the P3,000 Budget

 Map 2. Greedy TSP - Kruskal's Route for the P3,000 Budget

Now we see a difference in the routes provided by the two algorithms. Kruskal’s result is ~800m longer than the shortest possible route. However, runtime of the exhaustive TSP increased to almost 2 seconds, while the increase for Kruskal’s was miniscule. Whether or not deviations like these are acceptable in practice will depend on the relative size of the deviation, the required runtime duration, and the objectives of the project. If Nexie puts a priority on instant response and is willing to cover a little more distance, then Kruskal’s algorithm will be better than the exhaustive method.

Applications

Applications of the TSP model are definitely not limited to food trips. There are several business areas that can benefit from using TSP as an optimization tool. Here are some examples of how the TSP (or its variations) is used by different industries to model and solve complex problems^[ii]:

Although the TSP is associated with a certain type of problem like the examples above, creative applications have also surfaced, such as in genome sequencing^[iv] in biology. These create parallel interpretations for locations or cities and involve the use of metrics other than distance or time (e.g. measure of similarity).

Complex problems like the TSP do not have to remain theoretical and academic for your organization. As we demonstrated in this blog, it is possible to frame optimization problems to come up with practical and realistic solutions. Our Analytics Consulting Group can work with your organization to find solutions to your business challenges and find opportunities to optimize your processes. Drop us a line at analytics@nexustech.com.ph and let’s have a quick chat.

[i] ___. (2015, Aug). The Problem. University of Waterloo, Faculty of Mathematics. Retrieved on November 25, 2016 from http://www.math.uwaterloo.ca/tsp/problem/index.html

[ii] Matai, R. et al. (2010). Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches. Traveling Salesman Problem, Theory and Applications (Davendra, D. ed.). InTech, DOI: 10.5772/12909. Retrieved on February 17, 2017 from http://www.intechopen.com/books/traveling-salesman-problem-theory-and-applications/traveling-salesman-problem-an-overview-of-applications-formulations-and-solution-approaches

[iii] Lupsa, L. et al. (2010). Some Special Traveling Salesman Problems with Applications in Health Economics. Traveling Salesman Problem, Theory and Applications (Davendra, D. ed.). InTech, DOI: 10.5772/13365. Retrieved on February 17, 2017 from: http://www.intechopen.com/books/traveling-salesman-problem-theory-and-applications/some-special-traveling-salesman-problems-with-applications-in-health-economics

[iv] ___. (2005, Jan). Genome Sequencing. University of Waterloo, Faculty of Mathematics. Retrieved on February 17, 2017 from http://www.math.uwaterloo.ca/tsp/apps/genome.html