Whether we know it or not, at some point we have all dealt with variants of transportation routing problems. Consider a time when you and a group of friends (7 people total) are having dinner and have decided to transition to some drinks at a bar too far to walk to. You all agree to calling Lyft/Uber. The question becomes, ‘should you call an UberXL/Lyft Plus for 6 people and have one person go alone,” or ‘should you call two UberX/Lyft which can accommodate four people each?” Disregard the cruel part of sending one of your friends alone and focus just on the monetary benefits for the whole group for now. What do you think? What pieces of data would you want to include in this consideration? This is smaller scale but very similar to a common problem a company’s transportation specialist is trying to solve when looking for the best way to pool different customer orders together on as few trucks as possible, as cheaply as possible and as timely as possible.

Saving a few dollars on fuel or reaching the destination half an hour faster, may not have a huge impact on our own lives, but according to the American Trucking Associations, more than 37 billion gallons of diesel fuel are consumed in order to move 9.2 billion tons of freight annually. We cannot overlook the savings that can be obtained by making the best transportation routing decisions, and that is only considering fuel.

To see how these decisions can be made, we start by looking at a load consolidation problem, one of the simplest forms of transportation problems. Let’s consider the example shown in the table below. There are 10 orders received throughout the day at different times and they are all destined to arrive at the same location (much like the Uber/Lyft example). We would like to load these orders in as few trucks as possible to save on cost.

Order |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Weight (lb) |
35,200 | 22,000 | 4,400 | 30,800 | 26,400 | 4,400 | 15,400 | 15,400 | 8,800 | 8,800 |

**Problem:** Considering the 44,000 lb capacity for the trucks, how many trucks are needed to ship these orders?

**Potential Solution 1:** The solution for this small and simple consolidation problem is probably not very clear at first. Your intuition might lead you to assume we simply start loading the orders on the trucks as they come and use a new truck when there is not enough room for an order in a partially filled truck. Doing this we will end up with the following solution:

Orders {1, 3, 6} in truck 1 with total capacity of 44,000

Orders {2, 7} in truck 2 with total capacity of 37,400

Orders {4, 9} in truck 3 with total capacity of 39,600

Orders {5, 8} in truck 4 with total capacity of 41,800

Order {10} in truck 5 with total capacity of 8,800

This solution requires 5 trucks and the last truck is 80% empty!

**Potential Solution 2:** With some trial and error (and if we get lucky in trying different combinations) we find that we can load all the orders in 4 trucks. This is another way to do that:

Orders {1, 9} in truck 1 with total capacity of 44,000

Orders {2, 6, 7} in truck 2 with total capacity of 41,800

Orders {5, 8} in truck 3 with total capacity of 41,800

Orders {3, 4, 10} in truck 4 with total capacity of 44,000

This solution would save the company on the extra truck and driver. This solution also fills the trucks to minimize the amount of empty space being transported to the customer.

If you assume that the only drawback of the extra truck for the first solution would be paying for the truck and driver and the empty space, that is not the full story. Imagine a situation where you only have four shipping docks to load trucks simultaneously and all the trucks are currently scheduled to leave before 3:00 PM in order to arrive at the customer location on time. Sending the extra truck will mean a delay in the arrival of that trucks orders which would affect the fill rate and customer on time performance. So if we have 5 loading docks then it’s not a big deal right? Maybe not, even if all the trucks leave on time, what if the customer only has 4 docks to unload on? The fill rate and on time performance still suffers.

This is only a quick look at the difficulty in finding the best answer even in a small load consolidation problem with only 10 orders and one destination for all of the orders. So, it should not be hard to see that there may be large savings possible in problems with hundreds of orders. Now consider a more realistically sized problem where there are more orders received throughout the day, destined for different locations, and shipped by different trucks or other modes of transportation (TL, LTL, rail, air). Minimizing the number of trucks is not the only measure either: fuel cost, total distance traveled, and other variables will play key roles in the decision. Furthermore, weight is not the only constraint, since product volume might also restrict how much can fit into one vehicle. Some orders do not need to be shipped as they arrive. They can wait and later be pooled with orders received in other days, or with orders that will be received in the future. Customers don’t accept orders if they arrive earlier than a certain time (we still pay for those idle times before the unloading can happen) or later than a certain time. In case of a delay, even if we don’t lose our reputation for bad customer service, we still need to pay for all the time the truck and the driver are idle before unloading the next day.

Add to all of this the competitive market and the customers who want to receive their orders conveniently, timely, and as cheaply as possible. There are many more features that should be considered and it is impractical to explore all the combinations quickly without the help of optimization algorithms.

Our simple consolidation problem above is an example of a classical optimization problem called the “Bin Packing Problem (BPP)” . The methodology required for solving this seemingly simple problem is not as trivial as it may appear. Rather, it requires the implementation of algorithms that depend on each problem’s specific properties to ensure a high quality solution is achieved.

**Final Take Away**

The problem of how to best consolidate loads into trucks, one of the simplest forms of the transportation routing problems, requires the implementation of optimization algorithms in order to achieve maximum savings. It’s not hard to imagine the benefits of implementing optimization tools and techniques in more difficult problems and what these methods might uncover. Stay tuned for more blogs where we dive deeper into the optimization, tricks and tips for these types of problems in future months!