C4, Lesson 5: Planning and Routing: The Math Is Not the Hard Part
Tags: Sourced / General / Our view / Illustrative. About 13 minutes.
1. The story: UPS tries to route its drivers, and the first attempt fails
UPS began modernizing its pickup and delivery operations in 2003, and ORION testing began around 2008 (per the verifier). The result was a suite of systems and an optimization system called ORION (On Road Integrated Optimization and Navigation), which, according to the UPS team's own paper in the journal Interfaces (January 2017), gives each of UPS's 55,000 US drivers an optimized route every day. The paper says ORION cost more than $295 million to build and deploy and was expected to save UPS $300 to $400 million a year and cut 100,000 tons of CO2 annually. [Sourced: Holland et al., "UPS Optimizes Delivery Routes," Interfaces 47(1), 2017 (Franz Edelman Award paper); company-authored, figures are UPS's] The part that matters for this lesson is how the project began. The authors describe a first attempt, formulated as a textbook "traveling salesman problem with time windows," as a failure, and give a section titled "An Anatomy of Failure." The algorithm's routes did not follow a consistent pattern from day to day, did not consider how the van was loaded (so drivers took longer finding packages), scheduled commercial deliveries near the end of the day when drivers were supposed to be collecting packages, and the map data was not accurate enough. A second round added practical constraints, including consistency with the driver's usual "base route." The authors say UPS also made "extensive change in management practices" so that users and executives would accept the system. [Sourced: Holland et al., Interfaces, 2017] The lesson: the route math is the easy part. The hard parts are data, rules nobody wrote down, and the people who have to follow the route. [Our view]
2. The one idea
Routing and planning tools search for a low-cost plan among more possibilities than anyone can try. They are only as good as the data (maps, times, stop lists) and the real-world rules built into them (when to visit, how the van is loaded, what drivers know). A good plan that nobody follows saves nothing. [General]
3. The kitchen-table version
You deliver 8 parcels in town. The order you received them in is not the best order to drive. A simple rule, "always go to the closest next stop," gets you most of the way. A computer can find the very best order. But if the best order sends you past a school at pick-up time, you will not drive it. [General]
4. Planning problems in commerce
- Routes: which stops, in what order, on which vehicle.
- Loads: what goes on which truck (fill the truck, balance weights).
- Production and purchase plans: how much to make and buy, when.
- Schedules: dock appointments, shifts (see C2 Lesson 6). AI contributes in two ways: better predictions as inputs (drive times, demand), and faster search for plans. [General]
5. Worked example: how many orders can you try?
All numbers [Illustrative], computed by script. The size of the problem. For 8 stops there are 8! = 40,320 possible orders. For 25 stops there are 24! = about 6.2 x 10^23, far too many to try one by one. That is why routing tools use clever search, not brute force. Simple rule versus best. In 200 random 8-stop problems on a 10 by 10 mile map, the order stops were received in was on average 70% longer than the best route; the "nearest next stop" rule was on average 10% longer than the best (worst case 45% longer). So a simple rule captures most of the saving, and an optimizer captures the rest. What 5% is worth. A fleet of 50 vans, 250 days, 100 miles per route is 1,250,000 miles a year. A 5% cut is 62,500 miles; at $0.70 a mile that is $43,750 a year. If the tool costs more than that, or drivers will not follow its routes, it does not pay. [Our view]
6. What UPS had to add to make routes usable
From the paper's own description: consistency with the driver's usual pattern; commercial customers early in the day and pickups late; how the van is loaded; accurate maps; safe handling of busy-street turns and zigzagging; and a change program for drivers and managers. [Sourced: Holland et al., Interfaces, 2017] Your business has its own version: delivery windows, access rules, dock times, driver knowledge. Ask what rules are in people's heads, and write them down before buying a tool. [Our view]
7. What it costs and what it breaks
- Data work: map corrections, accurate stop times, load info.
- Rules: every unwritten rule becomes a constraint you must discover.
- People: drivers and planners need training and a say. A route they distrust gets ignored.
- Brittleness: a plan optimized for one day's data can fail when traffic or orders change.
- Cost: UPS reports more than $295 million to build and deploy. [Sourced: Holland et al., 2017; company figure] Small businesses should rent, not build.
8. Monday checklist
- Time your last 20 routes. Where do they lose time?
- Write down five unwritten rules your drivers follow.
- Try the "nearest next stop" rule on a week of routes and compare miles.
- Ask any routing vendor to run your real stops and rules, not a demo.
- Pilot with one team first, as UPS did with a small center.
9. Try it yourself (no code, 30 minutes)
Take 8 real stops. Write them in the order received and draw the route on a map. Now reorder by "next closest." Measure both. How much shorter is the second?
10. Self-check
- What happened to UPS's first routing attempt? The paper calls it a failure; routes were inconsistent, ignored van loading and had map data problems.
- How many possible orders are there for 8 stops? 40,320.
- In the example, how much longer was the received order than the best route, on average? About 70%.
- What does "nearest next stop" capture? Most of the saving; about 10% worse than best in the example.
- Why did UPS run a change program? So that drivers and executives would accept the system.
11. Where this is going
Faster solvers and better traffic prediction will keep improving plans. The binding limits will stay data and people. [Our view]
Sources
- Holland, Levis, Nuggehalli, Santilli and Winters, "UPS Optimizes Delivery Routes," Interfaces 47(1), 2017: https://ideas.repec.org/a/inm/orinte/v47y2017i1p8-23.html ; INFORMS Edelman Award page: https://www.informs.org/Recognizing-Excellence/Award-Recipients/UPS-2016-Edelman ; full text read at: https://transp-or.epfl.ch/courses/decisionAid2018/labs/Lab_1/Paper_Lab1_2018.pdf
Review flags
- ACCEPTED LIMITATION (lesson labels it): the paper (Holland et al., Interfaces, published online Jan 18, 2017, doi 10.1287/inte.2016.0875) is by UPS employees; all savings and cost figures are UPS's own, projected ("expected to save"), not independently audited. UPS's current figures were not checked.
- I read the abstract and key sections (the failure analysis and second attempt) of the full text on a university copy; I did not read the whole paper.
- The paper dates the modernization to 2003 and testing to about 2008 (per the verifier); I did not check what UPS reports now.
- The simulation is mine (random stops, plain distance); the fleet numbers are illustrative.
Claim ledger (C4 Lesson 5)
| # | Claim | Source | Verified | Status | Re-check |
|---|---|---|---|---|---|
| 1 | ORION: 55,000 US drivers; cost over $295M; expected savings $300-400M a year; 100,000 tons CO2 | Interfaces 2017 abstract | 2026-10-06 | Read; company figures | none |
| 2 | First attempt failed; reasons (consistency, loading, commercial timing, map data) | Interfaces 2017 text | 2026-10-06 | Read | none |
| 3 | Second round added consistency constraints; change management | Same | 2026-10-06 | Read | none |
| 4 | Route-order simulation and fleet arithmetic | Our computation | 2026-10-06 | Illustrative, script-checked | none |