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 on finding the shortest path, and illustrate how to solve it using a fun example: optimizing food trips. This article aims to increase awareness for the TSP and its applications to encourage more organizations to adopt similar frameworks for solving problems.
BACKGROUND
Suppose that Nexie, a very hungry analytics consultant, wants to go on a Friday night 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 straightline distance between two restaurants and avoid the Friday night traffic. 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
 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)
Framing the Problem
Nexie's main objective is to visit the best restaurants while spending the least possible amount of money and minimizing the total distance travelled. As an analytics professional, she wants to have a structured and logical process to come up with an itinerary and route map that she can follow.
To start creating Nexie's optimal itinerary, it is important to create a priority list of restaurants that Nexie is most likely to visit based on Zomato data. The factors to be considered for the list are the following:
 Restaurant ratings
 Cost per person
 Distance travelled
What determines if an itinerary is optimal? It is not always possible to find an itinerary that gives the best results for all three factors. Depending on the stakeholders, problem context, and even time, the prioritization of the factors may change.
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 wellstudied problem in the fields of mathematics and computer science and has many realworld applications, most notably for transportation, logistics, and routing. This food trip problem can be modelled as a TSP with the restaurants as cities and distance as cost. However, we will be doing a modified implementation that fixes the restaurant nearest Nexus Technologies as the starting point and does not require Nexie to go back to the starting point. In the succeeding sections, we will help Nexie accomplish the following:
 Select which restaurants to include in her itinerary based on ratings and cost
 Determine the order of restaurants that minimizes her distance travelled using two ways to solve the TSP
Note: From this point onwards, any reference to the TSP refers to the modified TSP as described above.
Algorithms
Restaurant Selection
To identify the restaurants that Nexie should visit, we computed for the ratingtocost 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 ratingtocost 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 RatingtoCost Ratio
Restaurant Name  City  Locality  User Rating  Ave. Cost for 1  Cumulative Cost  Rating to Cost Ratio 

Purple Oven  Makati City  San Antonio  4.5  150  150  0.030 
Izakaya Kikufuji  Makati City  Legaspi Village  4.5  300  450  0.015 
Manam  Makati City  Greenbelt  4.6  350  800  0.013 
Cafe Seolhwa  Taguig City  Bonifacio Global City  4.6  350  1150  0.013 
The Curator Coffee and Cocktail  Makati City  Legaspi Village  4.6  350  1500  0.013 
Silantro FilMex  Pasig City  Kapitolyo  4.8  400  1900  0.012 
Gino's Brick Oven Pizza  Makati City  Salcedo Village  4.6  400  2300  0.012 
Toby's Estate  Makati City  Salcedo Village  4.5  400  2700  0.011 
Mendokoro Ramenba  Makati City  Salcedo Village  4.9  500  3200  0.010 
Seryna  Makati City  Legaspi Village  4.7  500  3700  0.010 
Nexie will be able to visit 6 of the top 10 restaurants without going over her budget. Now that we have finalized Nexie’s list of restaurants, we can solve this problem as a TSP problem.
Finding the Shortest Route
The first method for solving the TSP is called the exhaustive method. An exhaustive TSP solves for the shortest possible route by getting the minimum distance among ALL of the possible routes (every possible ordering or permutation) to visit each restaurant. Doing an exhaustive TSP becomes very tedious as the number of locations increases. For example, with only three locations (A, B, and C), there are only 6 routes to consider (ABC, ACB, BAC, BCA, CAB, CBA), but this number grows very quickly as more restaurants are added. The table below shows how quickly the number of possible routes grows as the number of locations is increased.
Table 2. Number of Possible Routes by Number of Restaurants for Exhaustive TSP
No. of Restaurants  No. of Possible Routes 

1  1 
2  2 
3  6 
4  24 
5  120 
6  720 
7  5,040 
8  40,320 
9  362,880 
10  3,628,800 
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[ii] (illustrated by the flowchart below), a simple way for finding a route that should come close to the best route.
Figure 1. Kruskal’s Greedy TSP Algorithm Flowchart
Figure 2. Runtimes of Exhaustive and Kruskal’s (in seconds)
To the right is a runtime comparison of exhaustive TSP and Kruskal’s greedy algorithm.
We can see that for a small number of restaurants, the differences in runtimes are negligible, but as the number of restaurants increase incrementally, the runtimes for exhaustive algorithm increase at a much faster rate. Kruskal’s runtimes, however, increase at a very slow and negligible rate.
This is the reason why other potentially suboptimal but substantially quicker algorithms are more preferred to exhaustive TSPs, especially when working with a large number of locations.
Results
Here are the straightline distances (in km) between the restaurants in Nexie’s itinerary:
Table 3. Distance Matrix of the Top 6 Restaurants Based on RatingtoCost Ratio
Purple Oven  Izakaya Kikufuji  Manam  Cafe Seolhwa  The Curator Coffee and Cocktail  Silantro FilMex  

Purple Oven  1.18  1.55  4.21  1.20  4.76  
Izakaya Kikufuji  0.72  3.80  0.42  4.97  
Manam  3.09  0.38  4.39  
Cafe Seolhwa  3.41  2.45  
The Curator Coffee and Cocktail  4.55  
Silantro FilMex 
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
Algorithm  Total Distance (km)  Route Order  Run Time (sec) 

Exhaustive TSP  7.52 
Purple Oven Izakaya Kikufuji The Curator Coffee and Cocktail Manam Café Seolhwa Silantro FilMex 
0.0240 
Greedy TSP  Kruskal’s  7.52 
Purple Oven Izakaya Kikufuji The Curator Coffee and Cocktail Manam Café Seolhwa Silantro FilMex 
0.0005 
Figure 3. Exhaustive and Kruskal Route for the 2,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 RatingtoCost Ratio
Purple Oven  Izakaya Kikufuji  Manam  Cafe Seolhwa  The Curator Coffee and Cocktail  Silantro FilMex  Gino's Brick Oven Pizza  Toby's Estate  

Purple Oven  1.18  1.55  4.21  1.20  4.76  1.17  1.27  
Izakaya Kikufuji  0.72  3.80  0.42  4.97  1.35  1.36  
Manam  3.09  0.38  4.39  1.08  1.04  
Cafe Seolhwa  3.41  2.45  3.05  2.95  
The Curator Coffee and Cocktail  4.55  1.00  0.99  
Silantro FilMex  3.71  3.66  
Gino's Brick Oven Pizza  0.11  
Toby's Estate 
Table 6. Resulting Routes of the Top 8 Restaurants with the P3,000 Budget
Algorithm  Total Distance (km)  Route Order  Run Time (sec) 

Exhaustive TSP  8.57 
Purple Oven Gino’s Brick Oven Pizza Toby’s Estate Izakaya Kikufuji The Curator Coffee and Cocktail Manam Café Seolhwa Silantro FilMex 
1.8552 
Greedy TSP  Kruskal’s  9.37 
Purple Oven Izakaya Kikufuji The Curator Coffee and Cocktail Manam Gino’s Brick Oven Pizza Toby’s Estate Café Seolhwa Silantro FilMex 
0.0005 
Figure 4. Exhaustive TSP Route for the P3,000 Budget
Figure 5. 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.
Industry 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[iii]:
Industry  TSP Application 

Logistics, Delivery Services 
Scheduling of deliveries to a set of destinations to reduce time and fuel spent while meeting order deadlines. 
Semiconductors  Optimize the order of drilling holes into circuit boards to reduce changing of tools and total drilling time. 
Healthcare  Planning visits and schedules of medical registrars to maximize the number of patients registered when visiting a particular city[iv] 
Manufacturing  Designing plant layouts to minimize the routes taken by items moving through the production line 
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[v] 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] (n.d.). A Greedy Algorithm for TSP. Data Structures and Algorithms, Computer Science and Automation, Indian Institute of Science – Bangalore. Retrieved on February 2, 2017 from http://lcm.csa.iisc.ernet.in/dsa/node186.html
[iii] 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/travelingsalesmanproblemtheoryandapplications/travelingsalesmanproblemanoverviewofapplicationsformulationsandsolutionapproaches
[iv] 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/travelingsalesmanproblemtheoryandapplications/somespecialtravelingsalesmanproblemswithapplicationsinhealtheconomics
[v] (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