A few months ago I was talking to a friend of mine, George, who is in the food service business and delivers ready for pick up food to an important chain of convenience stores in Mexico. His business is small and has a local market, but still he must supply over 200 stores weekly.
During the conversation Georges asked me:
“Is there an intelligent way to make my deliveries without spending so much in gas?” The answer, “of course there is!”
In fact, it turns out this same question was proposed by a known American mathematician in 1959. That year, George Danzig proposed to the scientific community a problem that would turn out to be one of the most popular in the history of resource optimization problems.
The Truck Dispatching Problem proposed a ‘very simple’ project (at least in words) whose objective was to find “the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal”. This problem as simple as it sounds represents a problem with direct application to real life, which is also very interesting, and even more, very hard to solve. These characteristics made the truck dispatching problem of the favorites of the scientific and engineering community since the beginning.
Google N-gram showing the trend in popularity
Since then, the problem has evolved and now is actually better known as the Vehicle Routing Problem (VRP) and has grown to consider vehicle capacity, working schedules, demand, and even delivery time windows, among others.
While explaining all these, George started wondering about the actual complexity of the problem. “To tell you the truth it doesn’t sound too complex, wouldn’t be possible that mathematicians always tend to complicate problems?”. And he kept arguing:
“I mean, how hard can it be to decide in which order to deliver my customers’ requirements? It’s just a matter of getting a simple software to do it and that’s it, right?”
The answer is no and yes. “On one hand, it is NOT a simple problem, but on the other hand, a good and simple route planning software can indeed be the solution”.
To better explain the situation, I asked George to take a sheet of paper and without getting into details to make the following exercise. “Georte, let’s assume you have three customers you want to supply from your distribution center using your only vehicle in the fleet. For now, let’s assume these customers aren’t specific locations in a city map, but just three circles in your sheet”. Then I asked George to draw in the sheet of paper all the possible routes he could identify using different colors to avoid confusion.
After a minute, George finished, showed me the diagram and said “done! I could find 6 possible routes to deliver these orders… easy thing!”
“That’s right!” I said, and continued with my explanation. Mathematically there’s a very easy way to find the total number of possible routes with an operation called factorial or n!. In this specific case, n represents the number of customers, so n equals 3, and the factorial is:
3! = 3 x 2 x 1 = 6.
“For three customers, you have six possible routes to choose from as you showed me in your diagram.” I then asked George to take another sheet of paper and do the exercise again, but this time for 5 customers instead of 3. After a couple of minutes he took his calculator and smiling he said “Very funny!” while he showed me the number 120 on the screen.
Indeed, the factorial of 5 equals 120, which means there are 120 possible routes to choose from and it also means George won’t even keep trying to enumerate them one by one. Then George took his calculator again and quickly understood the complexity of the problem:
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5,040
8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320
9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880
10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3’628,800
The George questioned me, “but in good days I have to visit up to 40 customers, does that mean I have tenths of millions of possible routes to choose from?”.
I explained that “in theory you do, although in practice, the complexity does not depend only on the number of possible routes but also in many other factors which must be taken in account, as the capacity of every vehicle, the real distances to be traveled, the number of vehicles available, the operation schedules, the delivery time-windows of customers, among others.”
In fact, in real life, the process of route planning doesn’t mean that you must identify, calculate and choose your route from the total possibilities list as we did before. Given the huge complexity of the problem, to enlist all possible options, and even mathematical optimization, are not practical options to solve the problem (unless we were willing to wait for days or even weeks to obtain a solution).
But the most important part of my message to George was the fact that leaving the entire route planning responsibility to your drivers was definitely a huge mistake.
George seemed a little overwhelmed. Moreover when I started explaining to him the modern methods of route planning that are used by large companies, programming languages, mathematical optimization solutions, heuristics, the new developments in Universities, hundreds of thesis, dissertations and journal publications aimed at the specific problem of the VRP.
George complained, “I’m just a small company”, and continued “what can I do to make my operation more efficient? Maybe I don’t have tons of cash as the big companies, but every week my vehicles run over 300 miles to deliver my products. Just in gas and maintenance I spend over $8,000 dollars per year! Perhaps for a big company this ain’t much but for me it is. If I consider the rest of the expenses related to my routes –all logistics cost are a very important segment of my total operation”.
It was right then Routics was born, the idea and concept of bringing custom made solutions to small and medium businesses using modern systems. It was then when we established the objective of developing algorithms that would help small companies to be more competitive without asking too much in exchange:
- Not requiring specialized personnel,
- Not requiring expensive equipment, and
- Not requiring them to make big investments in software
Routics provides a great option with a cloud based software as easy to use as your email. With Routics, George will be able to solve his problem and much more, he’ll be able to plan routes and monitor its performance, he will geo reference his customers and visualize his demand, and with time he’ll discover how to get the max out of Routics so his business can make and grow more.
Soon, we’ll be writing more about George’s case (among other topics) and we’ll take a look at other case studies as well. We’ll also analyze real data of companies and how they’ve obtained great benefits from using Routics’ route planner. I hope this topic interest you and keep reading us in the future. If you have any comments about this post or any question please contact us in our website or in twitter.