In 2018, Rohit Malshe, an Amazon principal scientist, looked across the street from his home in Portland, Oregon, and spotted two trucks delivering Amazon packages to neighboring houses.
Malshe and his colleagues within Amazon Logistics (AMZL) Research Science and Amazon’s Supply Chain Optimization Technologies (SCOT) organizations had already started developing new methods to synchronize deliveries to neighboring locations. The goal: to avoid situations similar to the one he just observed — multiple trucks visiting the same area on a given day — to improve deliveries and reduce costs.
Important advances had been made by that time. Around 2017, scientists developed a method to group packages delivered to the same address on the same day. When that succeeded, the algorithm expanded to whole buildings.
“Those local optimizations were tackled first, and we solved them rather quickly,” says Malshe.
The next step: develop the concept of a stop consolidation — a chain of addresses linked by a small road segment. For example, a small group of houses in a cul-de-sac may be grouped together and, if two of them order items that will be delivered on the same day, the system will attempt to combine these deliveries into a single truck.
Focusing on the route
Following these initial advancements, AMZL and SCOT scientists turned their attention to optimizing shipment assignment and delivery systems by focusing on the routes.
“Instead of considering one address or building at a time, one should consider all demand assigned to a route, the time spent delivering, and the geographical blocks assigned to a route,” says Andrea Qualizza, a SCOT senior principal scientist.
The researchers drew from the prize-collecting vehicle routing problem (PCVRP), which builds upon the traveling salesman problem (TSP), one of the most popular combinatorial problems among the theoretical computer science and operations research communities.
“In the TSP, you just want to find the optimal way — or the shortest possible route — to traverse a certain number of locations,” says Weihong Hu, a SCOT senior applied scientist. But as the number of destinations rises, the number of possible routes surpasses the capabilities of even the fastest computers.
For example, in a scenario with 10 destinations, there can be more than 300,000 possible routes. If the number of destinations increases to 15, the number of possible routes expands to more than 87 billion.
The PCVRP is a more challenging variant of the TSP. Imagine a scenario where there are packages sitting at each customer’s door and you send a driver to pick up all the packages they can within a certain time interval. Every package collected adds a “prize” that is equivalent to the cost of assigning that package to a third-party carrier.
“For every package assigned to AMZL, you collect a reward, but you are also spending your time and truck space to do so,” says Malshe.
Deploying CONDOR
The team iterated on this approach over the past couple of years, developing a new algorithm: Customer Order and Network Density OptimizeR (CONDOR).
Qualizza notes that CONDOR solves a problem even harder than the PCVRP: simultaneously determining how orders are split into shipments and the sourcing fulfillment center for each shipment.
“This project uses a combination of various techniques,” says Qualizza. “There is mathematical optimization, local search, capacitated vehicle routing problem solvers — all of that came together because these techniques considered various aspects of the problem and linked them very naturally with the way our systems work.”
The breakthrough of CONDOR, Qualizza notes, is its ability to determine the right tradeoff between the levels of complexity and optimality.
While the problem involves a high number of possible decisions per geographical block, the program reduces that number to less than 10 per block.
“You’re losing some optimality, but at the same time, you make the problem tractable,” he says. “The key is squeezing enough bits of utility from the current data when it is processed and considering it all together to achieve meaningful improvements.”
Once confident with the prototype, Malshe says, the scientists tested it in production, working side-by-side with engineers to make that happen. In one of the tests performed — a crossover experiment — a few selected cities were divided into two groups: one of them used the new program, and the other didn’t.
That experiment determined that use of CONDOR resulted in roughly 0.5% fewer routing resources required.
“That means that if the whole network needs 50,000 routes without CONDOR, with CONDOR we should need just 49,750 routes,” says Malshe. Applied over Amazon’s extensive trucking network, the potential gains could be enormous.
CONDOR started running in a few delivery stations in January, and expanded to more locations this spring. Now it is deployed across the entire United States, and there are plans to deploy it in other countries within the next few months. The research behind the new program was presented at the 2021 INFORMS Annual Meeting.
How customers benefit
When a customer places an order on the Amazon store, Amazon immediately reserves inventory for it. Within minutes, Amazon’s logistics models evaluate thousands of options for fulfilling the order. Fulfillment location is one variable: a single warehouse may assemble the order if it has all the items; if not, the order can be split into multiple shipments. Amazon also reserves capacity within its transportation network to ensure the order can be delivered on time.
At that point, a decision is made about how the order will be fulfilled, but it won’t necessarily be the final one. There will be opportunities to revisit the decision before the shipment process starts. If a neighbor places an order later that day, for example, the logistics plan may be updated so that the same carrier delivers both orders.
Different programs may work together to make all of that happen. One program will consolidate orders by the customer’s address, for example, so that a carrier visits the address only once if possible. Another will consolidate the orders by buildings and another by groups of buildings.
CONDOR takes that to the next level by looking at the entire geographic area that a delivery station serves. Every once in a while, the decisions are reevaluated to ensure routes are optimized. From the time a customer places an order to the time it starts being processed by a fulfillment center, it could be five or six hours. During that time span, the CONDOR code might reassess the order three to four times, providing many opportunities for further optimization.
The team estimates that this year alone, CONDOR will help avoid millions of miles driven, boosting sustainability.
“We can enable carriers to deliver more packages to more customers on time, while reducing miles driven and carbon emissions from fuel,” Qualizza says. “That is the essence of CONDOR; it revisits all those decisions and finds those opportunities for us to further delight customers.”
