Useful ideas for maximizing the power of Microsoft Excel for Supply Chain Analysis, Part III
This is the final post in a three-part series that describes how to perform desktop network optimization, job scheduling and vehicle routing with nothing but Microsoft Excel.
Introduction
In the last two articles, I’ve shown ways to develop solutions for some of the classic supply chain problems. These problems can be characterized as facility location problems and production scheduling problems.
This entry will follow that pattern leveraging the traveling salesman problem as an example. However, we will call this the vehicle routing problem (VRP) to make it a bit more supply chain. Fortunately, regardless of how you refer to it, people will know what you are talking about because this is one of those classic problems in supply chain and operations research.
The idea is to create the shortest, closed-loop route, visiting each customer only once and returning to the starting point. Many companies must solve this problem daily, and there are multiple software providers that offer software solutions. Parcel delivery companies like UPS have elevated this to an art form and even sell their own software. Unfortunately, this software is expensive to license, expensive to set up and install, and expensive to operate. Thus, a business case must be carefully constructed to justify the expense.
Constructing this business case should include a comparison to a reasonable alternative that produces a satisfactory solution within a satisfactory timeframe at a satisfactory price point. By developing a solution in Excel, the price point is free (assuming it was already purchased), the length of time is 10 minutes and the solutions, while typically not optimal, are very reasonable.
If you have read the other blog entries you can probably guess that we will be using Microsoft Excel and the Evolutionary Solver with the “AllDifferent” constraint. As in the other two blog entries, we will extend the problem to make it a bit more realistic. The extension will result in the three shortest routes, served by a single depot so that all the routes start and end at the depot. Further, the routes need not have the same number of stops, but with each stop taking 10 minutes and averaging a driving speed of 40 mph, each route should be close to the same duration.
Characterizing the Problem
The problem can be stated as “is it possible to create three short and time-balanced routes that start and end at the same depot and visit all of the customers?”
Setting up the Problem for Solution
Like the problem from the previous blog post, this can be categorized as a sequencing problem. Leveraging what was done before, stops will be sequenced on three routes just like allocating and sequencing production jobs to production lines. However, in the production problem, we found that sorting by a particular grouping provided a very satisfactory simplification of the solution. There is the possibility to do this for the VRP as well by evaluating the angular distribution of customer locations and allocating stops to routes based on the angle from the starting location.
- Customer locations
- Depot location (starting point for all routes)
- Distance matrix
- Angular vector
For the sake of simplicity, the locations we will use fall on an XY coordinate plane. Therefore, we will be using the Euclidean distance formula. We could use the Haversine formula from the first article, but the distance formula is not the central issue. The route stop sequence is. Further, using XY coordinates makes this very easy to graph in Excel.
For this problem, we will sequence 37 customer stops on three routes. A snapshot of the data is provided below:
The angular allocation results in a setup that places the cities in a numerically increasing order:
Solver Setup
The solver set up for sequencing a single route is straightforward.
Following the same procedure but combining all three routes in the solver simultaneously yields:
However, the best view of the solution is obtained by graphing it.
The solver has done an adequate job of producing the routes, but there is room for improvement. To improve the results, a second optimization can be performed on the individual routes. Using Route 1 it is possible to re-sequence the stops and reduce the distance by 80 units, a 20% reduction. The results look like this:
Early in first article mentioned that there was a way to group the stops to speed up and simplify the solver routine. One way to perform this grouping is to divide the stops into sections. One of the simplest ways to do this is through an angular sweep of the stops produced by dividing the graph into equal 120 deg sections. The stops that fall into each section can then be optimized using the techniques similar to the ones discussed here to obtain faster solutions that are much closer to optimal.
Vehicle routing is a core competency for many companies and improvements result in improved asset efficiency, reduced cost, and improved customer deliveries. Some companies have produced closed-loop routes over time, but never reviewed them in any systematic way to insure they remain efficient as routes of deliveries are added or deleted. In some cases, these routes have been run for years without a review to determine if there are opportunities to consolidate or reorganize routes.
We believe this is a huge opportunity to save money and miles and would like to review the way your organization performs its routing. Please contact us to discuss ways that Centric can help you review your routes and determine opportunities for improvement.
Other published posts in this series:
- How to Conduct a DIY Network Analysis to Understand How Location Impacts Service and Transportation Expense (Part I)
- How to Perform DIY Production Scheduling to Make the Most of Your Production Assets (Part II)
Author’s Note: The skills required to understand the concepts are, admittedly, advanced but we feel that anyone with the willingness to learn can work through these samples and 1. Build their own skills and 2. Distinguish themselves by delivering value at their own company.
Granted, this is not completely altruistic. After all, we are consultants. Our hope is that you are sufficiently interested in these articles (and the ones to come) to ask questions and contact us to come to you and discuss ways we may build on what is here.