Ushering in a New Era of Drop-and-Hook Through Combinatorial Optimization

In this post, we highlight the complex and innovative combinatorial optimization techniques used by Convoy scientists and engineers to achieve efficiency and scale in what is fast becoming the most popular way for retailers and manufacturers to move truckload freight: drop-and-hook. We’ll explain what drop-and-hook is, why it’s historically presented problems of inefficiency to companies who move freight (“shippers”), and how Convoy has been able to solve these challenges by introducing technology to the equation. 

Traditional drop-and-hook’s challenges

As opposed to “live” shipments, where trucks are loaded and unloaded while the driver waits, drop-and-hook allows drivers to simply arrive at a facility, pick up a preloaded trailer, and drop it off at its destination. This leads to higher service utilization hours for drivers and the ability to transport more loads for shippers. 

Supply chains are intrinsically imbalanced in terms of empty trailer needs. The following figure shows the flow of trailers in a supply chain environment. Usually, upstream players fill a trailer and downstream elements consume the trailer’s product, requiring trucking companies (“carriers”) to move empty trailers in the reverse direction to keep the operation running. Upstream components frequently are not located near downstream components, so for any company wishing to be involved in drop-and-hook, it is essential to have efficient repositioning operations. 

Repositioning drop trailers is time-consuming and inefficient for carriers. Most asset based carriers manually gather information to forecast their shippers’ long-term needs. After processing that data, they have enough information to create a repositioning plan, typically on a weekly or even monthly basis. As you can imagine, the data is often stale by the time the plan is confirmed. This outdated data creates inaccuracy and inconsistency in supply, which in turn requires extra trailers in the carrier’s fleet so they can respond to shipper demand. Owning, managing, and maintaining these extra trailers is expensive and inefficient.

Driving innovation from a traditional problem with a familiar model

One way to solve this problem while eliminating inefficiencies is to leverage technology and sophisticated computational modeling. Drop-and-hook freight and combinatorial optimization models have both existed for quite some time. In fact, there are numerous classic transportation problems in the combinatorial optimization literature. So, why have we not seen their real-world application in drop-and-hook?

There are several factors that contribute to this, including a lack of data, inaccurate data, and the inability to solve the problem in a timely manner. In theory, it is not that cumbersome to develop a mathematical model to tackle this problem, but the input data significantly impacts any model’s accuracy. For example, a model could not reposition empty trailers with missing or inaccurate facility demand volume. On top of this, assuming you are provided with perfect data, if your model takes several hours to run, your data will be stale by the time it presents a solution. 

How does Convoy solve this problem?

Convoy uses machine learning and combinatorial optimization to keep repositioning costs low while maintaining a lean trailer fleet. Our drop-and-hook program, Convoy Go, leverages real-time data to avoid the stale data issues that make traditional, asset-based carriers inefficient. 

We created a solution for Convoy Go that we call TRIP (trailer rebalancing integer programming), which is a mixed-integer programming (MIP) model that includes several hundred facilities and thousands of loaded moves. This mathematical model describes the network with 100,000+ variables and 30,000+ mathematical inequalities. TRIP is responsible for repositioning all our empty trailers based on real-time information provided by our data-driven platform, such as trailer demand by facility, available trailers at each facility, and all ongoing shipments. TRIP is aware of each facility’s status at all times with the most up-to-date information. This model is running 24/7 and responds to any change in the network. Does a facility need more trailers tomorrow? No problem, TRIP can find the most efficient moves to satisfy the facility’s needs with minimal human intervention.

How did we effectively model TRIP to solve this problem? 

One route could have been to model TRIP with a common network optimization technique, such as a Minimum Cost Flow Network Problem (MCFNP). Another option could have been to create a time-layered version of MCFNP, where each node represents a facility at one point in time with its respective demand/supply, and arcs represent empty trailer moves between two nodes in the network. 

We chose neither route. Why? Putting aside that an MCFNP of this size might not be solved in a timely manner, gathering all of the necessary information to build that network is almost impossible. For example, for such a network one would need to price all of the possible arcs between any two nodes. This poses a huge burden on different machine learning models within Convoy to predict the price of specific future moves. 

Every loaded move in Convoy Go has an Empty Trailer Return (ETR) attached to it. Knowing this, we develop different heuristics and machine learning algorithms to provide reasonable ETR options for each of the loaded moves. Based on these ETR options, we can build a mathematical model that evaluates different options for each move and makes coordinated decisions across the network to reduce repositioning costs for the next eight-day planning horizon. Additionally, TRIP utilizes a forecasting model to determine the loaded moves between facilities when there is less concrete data available. This helps operations to pre-position empty trailers before the demand is even realized.

After developing the mathematical model utilizing all the information through our data platform or algorithms, we use a MIP solver to find the best option. Because of the mathematical model’s structure, it only takes 10 seconds on average to find the optimal plan. In other words, TRIP evaluates all of its options and selects the best repositioning plan to satisfy facilities’ needs while also minimizing routing costs. 

You might wonder how many options TRIP evaluates each time. The number of scenarios that TRIP considers is around 10⁶⁵⁰. To put that number into perspective, there are only 10⁸² atoms in the known universe. 

Here is high-level schema of the TRIP pipeline:

Results

By leveraging the real-time data and optimization, we have tackled one of the main obstacles of running a drop-and-hook program. This enables Convoy to run a leaner fleet as a digital freight network vs. fleets run by asset-based carriers, all while keeping repositioning costs low. 

In order to measure the impact TRIP has on our trailer rebalancing costs, we built another tool to mimic the actions a human team would have taken without the assistance of an optimization algorithm. This was used as a counterfactual and showed that TRIP’s repositioning plan saves us 2.5% in routing costs and 3% in empty miles. Even if we were able to throw enough humans at the problem to tackle it in a reasonable amount of time (which is not possible), TRIP would still save in routing costs and empty miles. This is the power of integrating combinatorial optimization with a digital freight network in an $800 billion industry.

Come Join Us

If you want to work on interesting problems that can have a significant and immediate impact in such a big sector visit our website to start your journey as a scientist at Convoy.