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

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

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

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 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

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

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]:

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.