CONTACT NO +632 5552400, +632 8671191

June 2017 Volume 6 Issue 2

Finding the Shortest Path: Optimizing Food Trips

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 straight-line 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 well-studied problem in the fields of mathematics and computer science and has many real-world 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 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

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 Fil-Mex 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 (A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A), 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 straight-line distances (in km) between the restaurants in Nexie’s itinerary:

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

  Purple Oven Izakaya Kikufuji Manam Cafe Seolhwa The Curator Coffee and Cocktail Silantro Fil-Mex
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 Fil-Mex            

 

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 Fil-Mex
0.0240
Greedy TSP - Kruskal’s 7.52 Purple Oven
Izakaya Kikufuji
The Curator Coffee and Cocktail
Manam
Café Seolhwa
Silantro Fil-Mex
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 Rating-to-Cost Ratio

  Purple Oven Izakaya Kikufuji Manam Cafe Seolhwa The Curator Coffee and Cocktail Silantro Fil-Mex 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 Fil-Mex             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 Fil-Mex
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 Fil-Mex
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/traveling-salesman-problem-theory-and-applications/traveling-salesman-problem-an-overview-of-applications-formulations-and-solution-approaches

[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/traveling-salesman-problem-theory-and-applications/some-special-traveling-salesman-problems-with-applications-in-health-economics

[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

 

DOWNLOAD FORM

Please enter a valid work email address. Free mail services such as Google, Yahoo, Hotmail, and others are not allowed.
Image CAPTCHA
Enter the characters shown in the image.