Stochastic Route Cost Minimization™



"Traditional" Route Cost Minimization

Common sense dictates that the shortest round-trip delivery route is also the cheapest. The main difficulty in finding the shortest round-trip route is that the number of DISTINCT* round-trip routes that must be examined in order to find the shortest one grows astronomically as the number of delivery points increases. For instance, a round-trip delivery route with just 5 delivery points generates 60 distinct round-trip routes, only one of which is the shortest. A more realistic route with 10 delivery points generates 1,814,400 distinct round-trip routes - and only one of these is the shortest!

The “traditional” approach to finding the shortest round-trip route is to employ a well known optimization technique commonly referred to as “The Traveling Salesman Problem Algorithm" or TSP algorithm. Created in the 1930's (and refined ever since), this technique, for the most part, relies on a kind of "best guessing" algorithm coupled with brute force computer search to find an answer. Although today’s personal computer power is up to the task of determining the shortest route with a large number of delivery stops, a fundamental flaw exists in using the TSP algorithm – it ignores TIME. More specifically the probabilistic nature of route travel time (more on this later).

An Innovative Approach.

As mentioned above, the major flaw with traditional route cost minimization is that it focuses solely on finding the shortest round-trip DISTANCE and totally disregards factoring in the importance of TIME when minimizing transportation costs. It doesn't take a rocket scientist to see that paying a driver $20/hour to travel 1000 miles in 19 hours costs more than paying him to travel THE SAME 1000 miles in 14 hours. Yet many consultants simply ignore the fact that minimizing transportation costs must involve examining both the distance of a delivery route AND the time taken to complete that delivery route - TIME MATTERS!!! More specifically, the uncertainty of time matters.

Taking into account the importance of examining route travel time when attempting to minimize overall transportation costs, we have created Stochastic Route Cost Minimization (SRCM™), a proprietary route cost minimization technique. SRCM™ utilizes elements of both Genetic Algorithms and Monte Carlo Simulation to determine, in a stochastic framework, that distance/time route combination with the highest probability of retaining the least costly round-trip route with the smallest mean cost variance for the longest time interval. What the hell does all that Ph.D-esque BS techno-babble mean? Simply put, SRCM™ finds that combined distance/time round-trip route configuration that will remain the cheapest route over the longest period of time. The following very elementary example should give you a good idea of our innovative approach to route cost minimization.

Time Matters!

Let's suppose you manufacture custom lawn furniture and once a month the finished products are loaded onto a truck and leave your factory, labeled A, to complete a round-trip circuit delivering to sites B, C, and D in no particular order. The mileage chart describing the distances between the factory and all delivery sites is given below.

Travel Distance

FactoryABCD
A0230350311
B2300290360
C3502900210
D3113602100


Using traditional route cost minimization analysis (i.e. TSP) results in the round-trip route A-B-C-D-A (1041 miles) being the shortest round-trip MILEAGE route as shown below (map not drawn to scale):



Now let's introduce the variable of TIME via the following chart describing the time taken (in hours) to travel between all the delivery sites:

Travel Time

FactoryABCD
A0.06.04.88.9
B6.00.08.84.8
C4.88.80.06.0
D8.94.86.00.0


Using the time chart above we find that the shortest round-trip TIME route is A-B-D-C-A (21.6 hours) as portrayed below:



Now let's suppose that the following cost data describes your present situation:

Diesel fuel is $5 per gallon
Delivery truck gets 8 mpg
Truck driver costs $22 per hour

Now things get interesting. There are only three DISTINCT* round-trips that can be made with one start/finish point A and three delivery points B, C, and D. They are:

1) A-B-C-D-A
2) A-B-D-C-A
3) A-C-B-D-A

Table 1 below summarizes information for each trip based upon the cost data:


RouteTime
(in hours)
Distance
( in miles)
Driver's
Costs
Mileage
Costs
Total
Costs
A-B-C-D-A29.731040$654$650$1,304
A-B-D-C-A21.571150$475$719$1,193
A-C-B-D-A27.361311$602$819$1,421

Table 1


As you will recall, the traditional approach to route cost minimization states that the shortest round-trip in terms of MILES is also the cheapest. Therefore in the present example the shortest, and therefore the cheapest round-trip route should be A-B-C-D-A at 1041 miles and a total cost of $1304. Yet as Table 1 clearly shows, round-trip route A-B-D-C-A (1150 miles, total cost $1193), although 109 miles LONGER than the shortest route is in fact $111 CHEAPER!

To reiterate - TIME MATTERS!!!

"Just One Little Flaw"

We made the preceding example very simplistic in order to introduce you to a distance/time approach to route cost minimization. Unfortunately this example has a major real world flaw - we portrayed travel times as being single, constant values like the distance values. Alas in the real world, although the travel DISTANCE of a set route rarely changes, the travel TIMES over the same route are anything but static. Take a moment and consider the following: When someone says "the warehouse-to-Springfield run takes 4 hours", it is usually understood the travel time from the warehouse to Springfield AVERAGES 4 hours give or take, let's say, 15 minutes. This random variability in travel time is the result of the constantly changing values of a number of trip-related variables such as time of day, the driver, the weather, road construction detours, etc.

For the sake of illustration lets say the distribution of travel times to Springfield follows the well known bell-shaped curve (a.k.a. the NORMAL DISTRIBUTION), with a mean of 240 minutes and a standard deviation of 18 minutes. Although the "distance-cost" to Springfield remains static, the "time-cost" to Springfield would fluctuate depending upon the random nature of the travel time distribution. For example, this coming Friday's delivery trip might time-cost 269 minutes, whereas next month's trip might time-cost 217 minutes.

Now let's take a fresh look at our simplistic example. When we added a static time-to-destination component to compute travel costs the result was that the shortest route, which traditionally is the cheapest, was no longer the cheapest route. In fact a longer mileage round-trip route was the overall cheapest. Yet, as mentioned above, a problem with this example is that the time chart was fixed just like the distance chart. Consider now what could happen if the travel times listed on the time chart were allowed to change randomly. Figure 1 below is a revised, more "realistic" time-to-destination presentation reflecting the random nature of travel times:

Travel Time

FactoryABCD
A0,0(6.0,.50)(4.8,.30)(8.9,.20)
B(6.0,.50)0,0(8.8,.70)(4.8,.18)
C(4.8,.30)(8.8,.70)0,0(6.0,.10)
D(8.9,.20)(4.8,.30)(6.0,.10)0,0

Figure 1


The first number is the average (Mean) travel time between the two points. The next number is the Standard Deviation of travel time between the two points, given as a percentage of an hour. Since travel times between points can change depending on the value of the travel time variables previously mentioned, it helps to think of the time chart as being fluid, with individual travel times between points changing randomly from time to time, causing round-trip route costs to also become fluid. Consider the following possible scenario: if the individual travel times between points had randomly changed so that the total travel time of path A-B-C-D-A were to improve (i.e. shorten) by approximately 17% and the round-trip travel time of path A-B-D-C-A were to worsen (i.e. lengthen) by approximately 24% then the picture would change noticeably as shown in Table 2 below:

RouteTime
(in hours)
Distance
( in miles)
Driver's
Costs
Mileage
Costs
Total
Costs
A-B-C-D-A24.721040$544$650$1,194
A-B-D-C-A26.791150$589$719$1,308
A-C-B-D-A27.571311$607$819$1,426

Table 2

As you can see the cheapest route has changed from A-B-D-C-A to path A-B-C-D-A! Some time later, say two months from now, the time chart might be in a state such that the following possible configuration (Table 3) exists where the LONGER time route is cheaper than the shorter time route. In this instance the cheapest path has the longest time and shortest distance, whereas the cheapest route in Figure 1 had the shortest route time and a middle range distance.


RouteTime
(in hours)
Distance
( in miles)
Driver's
Costs
Mileage
Costs
Total
Costs
A-B-C-D-A29.001040$638$650$1,288
A-B-D-C-A27.001150$594$719$1,313
A-C-B-D-A25.931311$570$819$1,390

Table 3

Granted, the time difference in this very simple example is only 2 hours with a savings of a measly $25. Still, being able to free a driver 2 hours earlier than before could very well be worth a great deal more than just saving $25. Whatever the case, hopefully the point has been made: the overall cheapest round-trip route changes from time to time.

"Cheapest For The Longest" - The Heart Of SRCM™

In a previous paragraph we mentioned that "a more realistic route with 10 delivery points generates 1,814,400 distinct round-trip routes - and only one of these is the cheapest!". That cheapest referred to shortest distance. Now that we have demonstrated how fluctuating travel times effect costs, adding the "time variable" into the search for a cheapest route makes the number of possible round-trip routes immense. Making the situation even more complex is the fact that in the real world, travel times can be quite different from the "well-behaved" normal curve. The travel times might follow more "exotic" distributions such as POISSON, LOGNORMAL, GAMMA, etc.

It might just be that the warehouse-to-Springfield run can take anywhere from 50 to 75 minutes depending on the random value of trip-time variables. Furthermore this time interval could in fact show, depending on the value of the variables, a kind of random "lopsidedness" so that the concept of "average" travel time becomes meaningless. For example, lets say that at the moment the values of the variables are such that ROUGHLY 70% of the time the Springfield trip takes about 60 minutes, give or take 10 minutes and roughly 30% of the time it takes 75, give or take 15 minutes.

The enormity of the problem of finding the cheapest round-trip route should be quite clear - at any particular point in time there exists a single, cheapest route from among a truly astronomical number of possible round-trip routes. Yet this cheapest route will most likely change in the near future and no longer be the cheapest route. Maybe it will take a month, or even a year - but it will change, and sometimes dramatically.

Now obviously you can't keep changing routes every time a better one comes along, it would be a logistical nightmare! No, the answer is to implement SRCM™ which has the ability to take into account the random, probabilistic variations of future travel times when searching for the most cost effective, "longest lasting" round-trip delivery route.

A Little Brutal Honesty

To be brutally honest (and to make our nervous house counsel stop biting his nails) we can not state unequivocally that the route we provide to our clients is the ABSOLUTE cost minimum - that's the reason we call it Stochastic Route Cost MINIMIZATION, not ABSOLUTE Stochastic Route Cost Minimization.

Do we personally believe that the minimal routes we find for our clients are the closest to the ABSOLUTE cost minimum possible? - you bet. Based upon certain advanced statistical analyses of the minimal route we discover, we are generally quite confident that a cheaper route doesn't exist. And if a cheaper route does exist, the percentage difference is statistically insignificant and quite inconsequential in terms of realistic savings. The bottom line is that after 11 years of offering SRCM™, we have yet to encounter a single client who has found a more realistically cost effective path than the one we ultimately provide for them. Furthermore you will not find a single complaint/lawsuit filed against us on the Internet.

Why Should You Trust Us?

The simple answer is: "Seeing is believing". The great advantage of our SRCM™ service in terms of your acceptance is that before you pay us a dime we provide you with a minimal cost route and all you have to do is plug in your own data and see that we have saved you money. Its right there in front of your eyes - no waiting to see IF our new route will save you money, you can immediately see that it DOES save you money.

If you take the time to look around our website, you will see that virtually all our analytic services have the character that before you pay us a dime, you can first see that our services work. Easier for you, easier for us. So contact us, you literally have nothing to lose.

* We consider route A-B-C-D-A to be non-distinct from route A-D-C-B-A


BACK
HOME