Menu

Menu

Let's Talk!

Say Hello

Send us an inquiry quote request, using the form below and we'll get back to you as soon as we can.

Concern

Please enter a work email address

SEND

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

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

Table not displaying properly?  Click here.

 

 

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

Kruskals Greedy TSP Algorithm Flowchart

 

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 steady and minor rate.

 

This is the reason why other suboptimal but substantially quicker algorithms are more preferred to exhaustive TSPs, especially when working with a large number of locations.

Figure 2. Runtimes of Exhaustive and Kruskal’s (in seconds) 

Runtimes of Exhaustive and Kruskals in seconds

 

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 

 

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

1.18

 

0.72

3.80

0.42

4.97

Manam

1.55

0.72

 

3.09

0.38

4.39

Cafe Seolhwa

4.21

3.80

3.09

 

3.41

2.45

The Curator Coffee and Cocktail

1.20

0.42

0.38

3.41

 

4.55

Silantro Fil-Mex

4.76

4.97

4.39

2.45

4.55

 

 

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

 

 

Exhaustive and Kruskal Route for the P2000 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 

 

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

0

1.18

1.55

4.21

1.20

4.76

1.17

1.27

Izakaya Kikufuji

1.181834

0

0.72

3.80

0.42

4.97

1.35

1.36

Manam

1.55

0.71528

0

3.09

0.38

4.39

1.08

1.04

Cafe Seolhwa

4.205183

3.800104

3.089139

0

3.41

2.45

3.05

2.95

The Curator Coffee and Cocktail

1.200545

0.422256

0.378821

3.405151

0

4.55

1.00

0.99

Silantro Fil-Mex

4.75887

4.96518

4.393532

2.44914

4.5487997

0

3.71

3.66

Gino's Brick Oven Pizza

1.168753

1.348959

1.081759

3.051617

0.9950056

3.711903

0

0.11

Toby's Estate

1.26648

1.364969

1.038607

2.947006

0.990842

3.655898

0.1099636

0

 

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

Algorithm

Total Distance (km)

Route Order

Run Time

Exhaustive TSP

8.57

Purple Oven

Izakaya Kikufuji

The Curator Coffee and Cocktail

Manam

Gino’s Brick Oven Pizza

Toby’s Estate

Café Seolhwa

Silantro Fil-Mex

1.8552

Greedy TSP - Kruskal’s

9.37

Purple Oven

Gino’s Brick Oven Pizza

Toby’s Estate

Manam

The Curator Coffee and Cocktail

Izakaya Kikufuji

Café Seolhwa

SIlantro Fil-Mex

0.0005

 

 

Exhaustive TSP Route for the P3000 Budget

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

  

Greedy TSP Kruskals Route for the P3000 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]:

 

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[iii]

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

LEARN HOW