Stochastic Route Cost Minimization (SRCM™)

Traditional Route Cost Minimization

A key financial goal for businesses delivering their own goods via their own truck fleet is minimizing their transportation costs by finding the cheapest route that makes all promised deliveries. It would seem reasonable to assume that the shortest round-trip delivery route is also the cheapest.

Unfortunately the main difficulty in finding the shortest round-trip route is that the number of distinct* delivery 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 (three of which are shown below), and only one of these nearly 2 million routes 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. 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.

An Innovative Approach

As mentioned in the preceding paragraph, the major flaw with traditional route cost minimization is that it focuses solely on finding the shortest round-trip distance and totally disregards the importance of factoring in time when minimizing transportation costs. Obviously paying a driver $30/hour to travel 1000 miles in 19 hours costs more than paying him to travel the same 1000 miles in 14 hours. Yet the standard TSP models 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 both a route's travel distance and time when attempting to minimize overall transportation costs, in 2008 we created Stochastic Route Cost Minimization (SRCM™), a proprietary route cost minimization algorithm. 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. In laymen's terms, SRCM™ finds that combined distance/time round-trip route 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.

It's About Time!

Let's suppose you manufacture custom lawn furniture and once a month the finished products are loaded onto your truck and leave your factory, labeled F, to complete a round-trip circuit delivering to sites S₁, S₂, and S₃ in no particular order. In this particular situation there are only three distinct* round-trips that can be made with one start/finish point F and three delivery points S₁, S₂, and S₃. They are:

The mileage chart describing the distances between the factory and all delivery sites is given in Table 1 below.

Traditional route cost minimization analysis results in the round-trip route F→ S₁→ S₂→ S₃→ F (1041 miles) being the shortest round-trip mileage route as shown below in Figure 1 (map not drawn to scale):

Now let's introduce the variable of time into our search for the cheapest round-trip route. Table 2 below lists the time taken to travel between the factory and all delivery sites. Travel times are listed in hours and decimal representations of hours for minutes, i.e., 4.8 = 4 hours 48 minutes(60 minutes times .80 = 48.)

Table 2 shows that the shortest round-trip time route is F→ S₁→ S₃→ S₂→ F (21.6 hours) as portrayed below in Figure 2:

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

Now things get interesting. To reiterate, there are only three distinct* round-trips that can be made with one start/finish point F and three delivery points S₁, S₂, and S₃. They are:

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

As mentioned above, the traditional approach to route cost minimization states that the shortest round-trip in terms of miles is also the cheapest. In the present example the shortest, and therefore the cheapest round-trip route should be F→ S₁→ S₂→ S₃→ F at 1041 miles and a total cost of $1304. Yet Table 3 clearly shows that the round-trip route of F→ S₁→ S₃→ S₂→ F (1150 miles, total cost $1193), although 109 miles longer than the shortest route, is in fact $111 cheaper! - TIME MATTERS!!!

"Just One Little Flaw"

We made the preceding example very simplistic in order to introduce you to SRCM™'s 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 let's 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. Table 4 below is a revised, more "realistic" time-to-destination presentation reflecting the random nature of travel times:

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: let's say that the individual travel times between points had randomly changed so that the total travel time of path F→ S₁→ S₂→ S₃→ F were to improve (i.e. shorten) by approximately 17% and the round-trip travel time of path F→ S₁→ S₃→ S₂→ F were to worsen (i.e. lengthen) by approximately 24% then the picture would change noticeably as shown in Table 5 below:

Note that now the cheapest round-trip route has changed from F→ S₁→ S₃→ S₂→ F to F→ S₁→ S₂→ S₃→ F! Some time later, say two months from now, the time chart might be in a state such that the following possible configuration Table 6 exists where the LONGEST time route is cheaper than the shortest time route. In this instance the cheapest path has the longest time and shortest distance, whereas the cheapest route in Table 5 had the shortest route time and the shortest distance.

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, let's 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.

The Bottom Line - Why Should You Trust SRCM™?

The simple answer is: "Seeing is believing". The great advantage of our SRCM™ service is that you can see that the minimal cost route we provide for you is indeed minimal - all you have to do is plug in your own data and see that we have saved you money. It's 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.

* We consider route S₀→S₁→S₂→S₃→S₀ to be non-distinct from route S₀→S₃→S₂→S₁→S₀