Transportation Route Optimization: One Tough Nut to Crack

Transportation route optimization is not for the easily discouraged. The process is monumentally complex. A sufficiently detailed model can tax even the most advanced software and hardware combinations. And, of course, the larger the network, the more variables you need to account for.

Transportation delivery routing could be the ultimate head-scratcher

Optimizing transportation routes (that is, the vehicle routing problem) is one of the toughest mathematical puzzles to solve. The reason is simple — the equation becomes exponentially more complex every time you add a new delivery point. There could be billions — even trillions — of combinations. Finding the best one can take days for even the best mathematician equipped with the latest and greatest tech.

One of our largest food and beverage clients delivers to approximately 24,000 delivery points, through 45 hub locations (or “branches”), spread across the U.S. In addition, there were more than 70 cross docks and drop yards in the system due to some customers being more than 200 miles from the nearest branch — the maximum one-way distance a truck can cover in a day. So, they send shipments from branches to cross docks or drop yards, either in merged or individual shipments, and they travel onward with another driver, like a relay race.

Route optimization demands some tough choices

Decisions, decisions: which customer should be served from which branch? Should we serve a customer directly from the branch or via a cross dock or drop yard? What is the ideal route of each truck and how many assets should each branch have? There were four distinct asset types (trucks of various sizes) with different capacities available. Answering these questions using a single optimization model is impossible. We broke down our approach into three steps:

• Find what branch should serve which customer using a model that minimizes the distance to each customer, considering throughput capacity constraints for each branch
• Run a route optimization model for each branch that assumes just one asset type; we considered all types of costs (driver, fuel, overtime, etc.) in the model
• Assign the routes found in step two and include the actual asset availability for each location; the goal would again be the minimization of the total cost, but since the routes are fixed, it will optimize the number and combination of assets

Each route configuration step comes with its own set of complexities

Step one, optimizing the total distance, doesn’t provide a really accurate picture. Because the routes may have many stops, the actual distance required to serve a customer will not be the actual point-to-point distance between the branch and the customer in question. For example, on one route, it would be 100 miles before we arrived at the first customer. On another route, we could reach the same customer in 200 miles, with a different sequence of delivery. As a result, costs vary and depend on how you form a route. Minimizing the total distance for each customer was just an approximate way to allocate customers to each of the branches. In the end, we chose the nearest site, namely, the site which minimizes the distance traveled in the last leg.

Steps two and three brought with them enormous complexity. In the U.S., there are hard limits on how much time a driver can log over the course of a working week. These constraints restrict the distance a load can travel in one shift (limited to a driver maximum shift of 14 hours). There is the option of giving the driver a 10-hour break between shifts, in a hotel en route, at an additional cost. That set of constraints adds greater complexity. Another limitation is the potential speed of the truck. Speeds differed from one location to another, beginning with an average of 20 miles per hour (MPH) in densely populated, high-traffic areas (such as the northeast), to an average of more than 40 MPH in rural areas with straight-toward-the-horizon highways. We also found the model was very sensitive to speed. A change of one MPH could lead to a gain (or loss) of between 50 and 70 miles traveled per week, per asset.

Specific customer conditions bring additional variables

In most cases, customers did not operate stores 24/7, so there were restrictions on hours of delivery. There were also off days when you couldn’t deliver any shipments. These factors resulted in additional wait time for the truck and the driver. At times, the model found it ideal to reach a location early and wait until they’re operational, rather than deliver to other customers and return to serve the now-open prior stop. In many cases, this constraint was binding. If you could relax the limitation, it would create many opportunities with substantial reductions in cost. A related factor was the actual due date of the shipment. Customers often had multiple shipments due on different days throughout our model horizon of one week. Consolidation of these shipments unearthed substantial cost savings.

As mentioned previously, we had four unique asset types of varying capacity available. It wouldn’t make sense to send a 53-foot trailer to deliver on a route with a total customer demand of, let’s say, just 1,000 cases. Similarly, there is a limit to the number of stores you can serve from a 28-foot truck. Sometimes customer warehouse compatibility with specific asset types was yet another constraint. So, asset selection depends heavily on how you form routes. Solving both problems simultaneously is impossible. This is where steps two and three of our route optimization approach come in.

Additional modeling and experimentation cracked the code

Our initial runs with step two — limiting the asset type to a single option — delivered decidedly impractical results. Some routes were 36 hours long (requiring a hotel stay and thus additional time) and served more than 40 customers. Other routes featured unfeasible shipments due to many constraints. There were routes delivering to only one or two customers, routes with less than 50% asset capacity usage and 30% time usage. However, the results helped isolate the best candidate routes.

Step three, selecting the ideal asset for each candidate route, applied all the asset-related options in the paragraphs above. The new variables, as you’ve probably already guessed, increased complexity by a whole degree of magnitude.

Multitudinous iterations and changing every conceivable parameter led to combinations of routes and assets coalescing. We identified ideal asset types, along with other route configuration refinements, and the optimized model for this subdivision of the network took shape.

As we optimized parameters on specific routes, customers aligned with their currently assigned branch locations, as the existing route formation was close to the optimal one. We found new savings by reducing the number of cross docks and drop yards. These site closures resulted in somewhat longer routes on average. However, this reconfiguration of assets and fine-tuning of routes made way for increasing resource use across the board that brought about additional savings. The primary trade-off would be hiring additional drivers or — as an effect of the longer routes — bearing additional overtime costs for the current roster of drivers. These longer routes also reduced the need for assets, along with a corresponding reduction in maintenance and fuel costs.

— By Pushkar Oke