First Tutorial: Shortest Distance Network on Excel

Suppose I am a warehouse manager that are tasked to collect casks of wine from the local vineyards.  I have one truck, and this truck will go around to the vineyards and back.  I want to find the shortest route and the shortest distance for my truck.


The very first thing you want to do is to get the raw data.  As mentioned from my previous post, I use Depiction for that.  Now that we have the raw data, it is time to set up what we need for the linear programming.  For this problem, we will use a shortest distance problem.

A linear programming consists of:

• Goal:  In this case, it will be the distance traveled, and the goal is to minimize it
• Variables: The one that will be changed in order to achieve the most optimum goal
• Constrains: The limitation / constrains that defines the network

So let’s begin.  The data that we need are:

• Starting Location (Starting node)
• Ending Location (Ending node)
• Length of the Arc (distance between the two points)

example 1: Start, Stop, and Arc length

Then you may add a few paths that are not written before if you like.  For example, I draw only one path from point 2 to 3 whereas it is possible to go from point 3 to 2 too.  I add them in this stage.

Next, we define the variable.  Later on we will ask Excel to change these in order to find the minimum route.

example 2: route

Third, we define the goal.  In this case, it is the maximum distance.  There are several ways to do this, but probably the simplest way is to use the Excel function SUMPRODUCT. 

And here’s the trick.  If we set the route to be TRUE or FALSE by using the number ‘1’ for TRUE and ‘0’ for FALSE, then when we multiply the “distance” (column B) and the “route” (column F), the result is the total distance traveled. 

Then we define some constrains

The first constrains that we should set is that our route is TRUE or FALSE only (1 or 0).  That is, we do not want a fraction or a number greater than 1.  Therefore, in the column H, I type this formula, then dragged it down to cover every route. 

=IF(F2=0, 1,  IF(F2=1, 1, 0))

This formula will return “1”if the route number is exactly 0 or 1, and will return 0 for anything else.  We will make it into our first constrain: All number in column H has to be 1.

The next constrain we will define is that the flow summed to 0.  That is, every ending point is chosen only once.  In order to do so, we will have to construct a list of points.  In our case, 1 to 8.  Then we will build the flow using SUMIF.

Suppose Column D is the ending point of the route, column J is the new table we set, and column F is the route.

=SUMIF(D$2:D$37, J2,$F$2:$F$37)

This code will sum the value in F column if the D column is equal to J2.  Therefore, this can be used to determine how many ending point is there. 

Then we add it so that every ending point will lead to another point (aka new route).  Therefore, we add the starting point.  The formula become this:

=SUMIF(D$2:D$37,J2,F$2:F$37)-SUMIF(C$2:C$37,J2,F$2:F$37)

If there is an unconnected ending (i.e. ending point which does not lead to a new point), the value on the cell will be positive, and negative if there is no corresponding ending point for a starting point.  This will be our cross check to make sure every points is connected to each other.  This will have to be 0 all the time.

Last, we don’t want any backtrack, or we want to visit every node.  We sue SUMIF again, but this time only the first part.

Then we use the solver to define all of the said constrains.  

example 3: excel solver

Here is the depiction file and excel file that I use
Depiction file
Excel file


Hope this help!