Ehsan Khodabandeh PhD
Jul 25th, 2017

A transportation specialist needs to determine the best plan for shipping the customers’ orders on a daily basis. One important aspect of the decision is knowing the cost of each shipment, based on the their weight, origin-destination, transportation mode (TL, LTL, rail), etc.

Now let’s assume you, the transportation specialist, have 100 orders to ship to your customers and each order is destined for a different location. Also, suppose you follow a direct shipment policy. In other words, you don’t want the trucks to stop at multiple drop-off locations. So, there is one way to ship each of the orders. For simplicity, we consider just one transportation mode here, truckload (TL). Having 100 orders and one way to ship each, we need the rates for a maximum of 1×100 = 100 shipments.

Now assume you have 100 orders but there are 50 different locations. For the sake of this example, we assume that each location has 2 shipments. How many different ways are there to ship these orders?

You still want to follow your direct shipment policy, but since each location has two orders, you can either ship those orders separately or you can do a simple consolidation by putting them together in the same truck (assuming the truck capacity constraint is not violated). This time you have three options for each location: two direct shipments and one consolidated shipment to each location. Having 50 locations, 150 rates are needed.

I think by now you have guessed where we are heading. Now assume we have 10 different locations and each location places 5 orders. How many combinations do we need to consider this time, if we want to cover every possible rating option? We can ship each order separately, ship any two of them together, any three of them together, any four of them together, or all in the same truck (again, assuming that the truck capacity constraint is not violated). It turns out that there are 31 rating options for shipping each locations’ orders. With 10 locations, the number of rates increases to 310 (hint: you can calculate the number of options using 2N-1 where N is the number of shipments per customer. So for this case where each customer has 5 shipments, we had 25-1 = 31 options).

If you are thinking that not all the 310 rates are necessary, you are probably right (for example, the truckload rate for shipping an order from A to B for loads of 10000 lb, 7000 lb, or the combined load of 17000 lb can be the same. In this case, we just need to know one rate rather than three). But there are situations in which you would need to have all the rates. This example just considered the possibility of direct shipments with order consolidation. No multi-stop options were considered. If, however, we do consider the possibility of shipping to one location and then visiting another for a second delivery, we would need many more than 310 rates . In this case, you need to explore all the possibilities of consolidation at one location combined with those of another location to figure out the best shipping strategy. In the example with 10 locations, just considering 2-stop options can add up to 2790 possibilities (hint: 10×9 = 90 two-stop possibilities with 31 consolidation options for each location gives 90×31 = 2790)!

But you may ask “why these bigger numbers should concern me? Aren’t they all automated or done very quickly?” You are right about the automated part but not so right when it comes to the speed. In these types of combinatorial problems, where we need to consider all the possible options, the relation between the size of the problem and the computation speed is not linear. So, If we go from 100 orders to 1000 orders, the number of possible options and also the computation speed, are not increasing linearly. Consider the above-mentioned example again. For 5 loads in a location, we saw that there are 31 consolidation options; for 10, this number will be 1023; for 50 loads, which is just 5 times more, we need more than 1015 options! If we assume our computers can handle 1,000,000 options in 1 second, we need more than 30 years to go through all the options for just 50 loads!

By knowing the reason behind these exponentially-growing computations, you can understand better why just more powerful computers are not enough and the use of optimization algorithms that can reduce the options logically and speed up the process, is inevitable.

Take Away:

Sometimes seemingly obvious questions can lead to complicated answers. As we saw here, understanding the shipping options for 100 orders going to 100 different locations will require knowing 100 different rates, but 50 orders goring to 10 different locations requires 310 different rates. So, in this example, the number of different rates does not just depend on the number of locations; it also depends on the number of orders going to each location. As the number of possible shipping options grows, there is a need for algorithms that will prune the possibilities such that the resulting solutions will be business-optimal. This is where optimization techniques come to rescue.