Stochastic Route Cost Minimization™
"Traditional" Route Cost Minimization
Common sense dictates that the shortest round-trip route a truck can follow and still make all its deliveries is also the cheapest. Unfortunately the main difficulty in finding that 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 the TSP algorithm, commonly
referred to as “The Traveling Salesman Problem". Although this technique has been applied since the late 1930's to determine 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 most trucking company managers 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. 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.
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.
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:
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:
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:
Table 1 below summarizes information for each trip based upon the cost data:
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:
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:
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.
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
We mentioned before 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.
Why Should You Trust Us?
"Seeing is believing". The great advantage of our SRCM service 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.