The traveling salesman problem has been known as a tough problem to solve since it was first discussed in the 19th century. Multiply it by the 55,000 routes, more than 100 stops on each, add in additional constraints like time commitments, and it goes beyond being tough to becoming seriously challenging. But, there’s a big payoff in solving tough problems, and that’s why UPS developed ORION (On-Road Integrated Optimization and Navigation). This award-winning predictive analytics route planning algorithm combines map data with package details and customer priorities to create efficient routes that save UPS significant money, keep customers happy, and make the planet a little greener, too.
The Traveling Delivery Person Problem
The number of possible routes a UPS driver can take on any day to make their deliveries is enormous. Optimizing the route for delivery, fuel, and time would save the company significant money. Unlike a traditional traveling salesman problem, finding the shortest route alone isn’t the answer.
As Chuck Holland, VP of Industrial Engineering at UPS explained, “It was really quite a challenge because we have to balance multiple things.” The company usually delivers to commercial customers in the morning and residential customers in the afternoon, but there are many deliveries that don’t conform to those guidelines. Some next-day air packages need to be delivered by a certain time, and there are specific arrangements with certain customers for scheduled delivery times as well.
“We have soft constraints and hard constraints both, and ORION takes all of those into consideration. It meets all business rules, all service commitments, while trying to have the minimum number of miles and the least cost to make that delivery for that day,” Holland continued.
Saving just one mile per driver each day amounts to saving $50 million for UPS. Once ORION is fully deployed in the US, it’s expected to save UPS up to $400 million per year, and reduce greenhouse emissions by 100,000 metric tons every year.
A Quick Calculation with Detailed Maps
ORION develops a new delivery sequence for each driver every morning; the calculation takes about eight seconds and incorporates customized map data, package details, customer preferences, and historical data. It runs continually throughout the morning as trucks are loaded with packages.
One of the key technical challenges was creating the detailed maps. Holland said, “There are really no maps off the street that are good enough and pristine enough for the ORION algorithm to work.”
But despite the technical challenges, the project didn’t succeed due to incorporating new technology. The technical team said:
“The technology we used was truly a standard technology stack (C/C++, C#, .NET, SQL). We used an industry leading mapping engine and used creative ways of segmenting the data to achieve very stringent SLAs. We also created ways to automate attaching hundreds of millions of data points to a commercial map to facilitate the optimizations.”
The real key to ORION’s success was UPS’s commitment to introducing new technology and allowing their project team time to develop solutions that work.
Holland explained the process. “What we did first is, we built a prototype. My engineering group combined with the OR group built a prototype, and it took us about five years to get out of the lab. It was a huge commitment.”
The system wasn’t ready for deployment then.
“After about five years we were able to get it to work on one route for one day. Now, to get things in perspective, just in the domestic United States we typically have about 55,000 drivers on the road, and just Monday through Friday there’s 252 operating days during the course of the year. So I had to make a huge jump from working on one route for one day to be able to work on 55,000 routes for 252 days.”
The next step was to roll it out in a depot with about 30 drivers. The results from that were successful enough that the C-suite gave support to continue on with the project. The following year they deployed in two more depots and made it work with similar results.
Still not confident enough for deployment, they spent a third year with a test deployment, this time in eight sites. Finally, Holland said:
“At that point we got approval from it no longer being a research and development project just with my engineering and operations research folks, but it became a true project that would now include IT. It would no longer be a prototype and would be built to interact with the package flow system.”
The package flow system was technology UPS had started deploying in the 1990s. By the 2000s, they had a suite of tools called Package Flow Technology that includes the drivers’ hand-held delivery information acquisition device (DIAD). Adding optimization on top of this infrastructure was an obvious next step.
“To get the product out faster,” Holland said, “we worked with IT and hardened the prototype. So our initial deployment in 2012 was a hardened prototype while in parallel we were building the first true version.”
The deployment required a significant commitment in addition to the commitment for development. The first year’s rollout involved 125 people, which increased to 425 people the next year, and ultimately to 700 people. A variety of skill sets were needed, including industrial engineers and operational staff.
It takes about six days to train a driver to work with ORION. Part of the roll-out involves the trainers adding even more detail to the maps and talking with drivers to learn the intricacies of their routes.
Typically ORION can save six to eight miles for each driver, though some drivers still out-perform the system. “ORION is not perfect. We have a certain percentage of drivers that still beat the ORION algorithm and we encourage them to do what they believe is right if the algorithm isn’t perfect,” Holland said.
While some drivers dislike the system, because the routes don’t always match human standards of reasonableness, Holland says many do like the fact that they don’t have to focus on figuring out their route plans and can instead focus on customer service.
Commitment Beyond ORION’s Current Functionality
Although ORION is currently deployed throughout the United States for route planning, it isn’t yet deployed internationally. That’s expected to occur after some of the underlying technology is deployed in 2017. There are also plans to develop additional features in the next release of ORION. One feature will be allowing the route to change if conditions change during the day; another will be specific navigation instruction. They also expect to add functionality where ORION will help decide which work should be assigned to which driver.
ORION is just one of the predictive analytics projects that UPS has committed to developing. The company is working on numerous projects, emphasizing developing predictive and prescriptive analytics solutions. One project that provides predictive maintenance has helped the company reduce its vehicle maintenance expenses by around 15 percent.
Commitment to Data Science Education
Beyond its commitment to applying predictive analytics internally to its own benefit, UPS contributes to the broader Data Science community through the UPS George D. Smith Prize awarded by INFORMS.
Holland explained, “We take a look at learning institutions that are preparing students to practice operations research in the field and having an impact.” He went on, “The award is a $10,000 prize and a very prestigious trophy. Many of these universities have literally built special display cabinets to put them in.”
The company also brings many students onboard through internship programs. With their hundreds of analytics projects in place, they need the next generation of data scientists to develop and apply their expertise as quickly and effectively as possible.