Keeping trucks full by algorithmically bundling shipments
Trucking companies often face and need to solve a complicated version of the “Vehicle Routing Problem” to effectively dispatch their fleet. There are many shipments available in the market and choosing the best sequence of loads to haul back-to-back is NOT trivial. Diversity of parameters (e.g. gas price, routes, empty miles) make decision making for transportation business owners arduous. At Convoy, we created a solution called Automated Reloads that algorithmically evaluates and optimizes how loads can be grouped in real-time, all without human intervention. This positively impacts the business of carriers by keeping their trucks full more often and reducing the carbon footprint of burning gas for unnecessary empty trips.
A Problem
The transportation market is inherently asymmetric: some cities and ports produce or export more goods that need to be transported to other places compared to their inbound traffic. Los Angeles and Riverside are good examples. About 25,000 containers arrive everyday to the Port of Los Angeles. Most of them need to be distributed to the rest of the country. Even though the carriers taking these loads out of Los Angeles typically try to find a return load to come home full, it is not always guaranteed that they can find relevant jobs at the right time and right price. This asymmetry in freight demand has created an inefficient and wasteful network where a sizable percentage of trucks are driven empty across US freeways.
Like many other markets in the US, trucking follows the principles of free markets. The majority of supply capacity is not on payroll. They are independent contractors who naturally prefer shipments that work best for their schedule and economic benefits. Freedom of choice has caused carriers to bring their perception and understanding of the market into price negotiations. One example of such perception is the uncertainty in dealing with shipments that end in not-so-popular destinations (from a carrier’s perspective). Let’s pretend Portland, Oregon is more of a consuming city (We are not saying it’s true. It’s just an illustrative example). Carriers might perceive Portland as a not-so-popular destination because most of them don’t know for sure if they will be able to find any outbound load leaving Portland. Hence, in order to gain the perceived benefit of hauling a shipment from Seattle to Portland priced at $300, they would rather demand a little extra, e.g. $400, to compensate for the uncertainty of finding a good load on the way back. This extra fee will be added into their bids thereby reducing their chances of winning price negotiations in auctions they participate in (run by Convoy or other brokers).
An observation
The certainty of being able to find reloads ahead of time boosts the carrier’s confidence in submitting more competitive bids on shipments ending in not-so-popular destinations. For example, if a carrier is offered a round trip from Seattle to Portland and back, they may accept the bundle for $600 total, instead of $400 + $300 = $700 (assuming Portland to Seattle is also $300). The lower bid of $600 significantly increases carriers’ chances of winning more shipments. This is truly a win-win situation as carriers are better utilized and earn more while the amortized cost of shipments is reduced. Bundling shipments is an extremely powerful use of computers in freight matching and planning which benefits shippers, end-consumers, and our environment.
An idea
So how do we help carriers based on this observation? Our idea was to bundle shipments together and offer them as roundtrip package deals in our mobile app.
Of course, due to the asymmetry of the freight market, round trips are not always possible. After all, there are only so many shipments going from Portland back to Seattle, and there will always be some imbalance. So, what else could be done?
Even though we cannot fully solve this puzzle due to imbalanced demand, we can still help carriers get out of not-so-popular destinations. Using the above example, if there is no load back to Seattle, we might route carriers from Portland to Los Angeles, then to Phoenix, then to Las Vegas and finally back to Seattle. Ideally, we can help carriers find a complete tour so drivers end up back at their home base. Even if we don’t manage to complete the loop, it will still be valuable for carriers to get shipments as nicely organized, back-to-back bundles so that their risk of dealing with uncertainty is minimized. In an environment full of uncertainties involving so many variations of price and destinations, we turned to graph algorithms and leverage machine computation power to enhance a carrier’s decision making abilities.
An Algorithm
At Convoy, we created an algorithm that bundles shipments together. At first glance, this algorithm might look like a special case of the Traveling Salesman or Vehicle Routing problem. But in reality, things are a little more complicated. We are dealing with a dynamic system where shipment requests are not a fixed set of inputs, but instead arrive to the marketplace one-by-one and gradually over time. As new shipments come in and existing shipments get matched or canceled, we need to update our bundles in response to the stream of incoming events. In practice, we need an online algorithm that responds to shipment events and re-evaluates bundling options dynamically. This algorithm is subject to a few constraints and objectives such as:
- The algorithm should pick some shipments and put them into a bundle that is highly utilized, so that it’s more beneficial for a single truck to complete the shipments back-to-back.
- Completion of the bundle should be feasible under the laws of physics. This is not trivial as usually the pickup and delivery of shipments are scheduled in the form of appointment windows and not exact times. As an example, a bundle of two shipments with good geographical proximity might look like this:
In practice, a bundle made of above shipments would be infeasible if the sum of drive time for both shipments is more than 8 hours. Under the laws of physics, there would be no way any single truck can fulfill this bundle. However, each shipment might be fulfillable individually by different trucks.
- Completion of the bundle should be feasible under Hours Of Service (HoS) regulations. The Department of Transportation has regulations to ensure the safety of drivers on the roads. These regulations limit the number of hours a driver can continuously and non-continuously drive per day and week.
- The bundling algorithm should consider the wait times at each facility and the drive time required between the facilities. Typically, upon arrival to facilities, trucks need to check in and wait to get called out to a specific loading dock. At the loading dock, drivers have to wait to get fully loaded or unloaded, for cargo inspection, and for getting paperwork sorted out. Finally, they can head out of the facility. This whole process might take a few hours to complete and the bundling algorithm needs to be cognizant of such time constraints.
Running an online algorithm for all shipment events can be a huge challenge. Given the volume of shipments and the exponential nature of all possible combinations, computational needs to solve this problem can quickly grow to an unsustainable level. To address this, Convoy’s engineering team has created, and is constantly improving, a distributed asynchronous decision-making system that can process a stream of an enormous number of shipment events at scale.
Considering the size of this problem, there has to be some pruning process in place to shove off a few combinations that are not very likely to be good bundles. Thanks to the well-developed area of statistical inference in the Search Engines realm, there are machine learning techniques that can be used to help improve our algorithm using historical data. In particular, a simple logistic regression model that, given a bundle, predicts the likelihood of acceptance and completion by a carrier has helped us in tuning and pruning our bundle generation algorithm.
Measurement
So how do we know we are giving carriers the bundles they want? In the early days of creating bundles at Convoy, we turned to our carriers and asked them to help build their own bundles. We built an experience in our mobile apps suggesting related shipments so carriers could choose and book multiple shipments at once and in one transaction.
This way we could explore common characteristics of the bundles that our carriers wanted and over time alter our algorithm to get closer to their preferences. Of course, the historical pattern of the bundles that users accepted was not the only signal that we considered for creation of bundles today. We aimed to optimize for network balance with the objective of minimizing the transportation cost to our customers. Historical preferences of carriers, however, acted as a balancing factor to ensure the algorithm did not produce highly optimized bundles from only the shippers’ perspective but also desirable bundles from the carriers’ point of view. After all, we should not forget that in a free market carriers can choose not to accept bundles; their preferences (time, price, distance) are important inputs to the system.
Measuring the quality of a bundle remains a hard problem as there are so many factors that contribute to accepting or rejecting a bundle. Price negotiations, a driver’s route and schedule preferences, and a driver’s prior HoS context all affect matching results. Isolating these factors and observing the impact of incremental changes to the algorithm isn’t an easy task. Since there are so many nuances in running A/B tests on different bundling algorithms, this is still an exciting area of open discussions.
