This seems like a combinatorial problem that would very much be worth solving. I can actually come up with some fun mathematics already to deal with it.
I attended a presentation from Jack Levis at a supply chain conference. At first glance it seems like a traveling sales person problem, but it's much more than that. They have contracts to pickup and deliver at specific times for specific businesses. They have to optimize which packages are on which vehicles, the route, the volume available and numerous other considerations. The combinations get out of hand very fast, you can't do anything near brute forcing. Sometimes the path which will work best looks unintuitive.
They have real time issues that come up (water main shuts a road down for 1 day, in under a minute that info is available to all delivery drivers). They have their own custom developed hardware for the scanning guns which are GPS and network enabled, they have a team of around 700 people working on their ORION project (largely optimization, many PhD's included).
Couple resources on it:
https://blogs.oracle.com/database/big-data-at-ups-interview-...
https://www.google.com/amp/s/www.wired.com/2013/06/ups-astro...
I'd like to try using it before I finish.
The issue with deliveries is more complex as there are several systems with different incentives involves (and managers who bonus is determined by different factors then simply efficient delivery).
1. Deliveries arrive via large container and are organized by postal code but not in any specific order. Why? Because the plane/truck is packed for maximum haul not maximum efficiency of delivery.
2. When packages are sorted for their destination and packaged onto trucks, the incentive is to maximize haul, not maximize delivery efficiency. Why? The worker is incentivized to clear the backlog not to organize for delivery method. There are size constraints. As someone commented further down, it’s like a game of Tetris.
3. The delivery person just has to deal with what’s given and has to complete three rounds (usually).
In a normal situation, my buddy used some “fun math” and an excel sheet to attempt to maximize deliveries. Theoretically, his system would save an average of $0.02 on each package (his calculation, have no clue how he came up with this number or can verify). He was given recognition and bonus as, supposedly, this was a huge feat. However, his system totally broke down during holidays/peak season; There was no way to organize packages in step one accuretly enought that translates to step 2 and 3.
I, as a novice, suggested something like: “why don’t they use robots to sort, scan, and organize packages?” He patiently explained that the cost to retrofit all delivery stations would be enormous. The delivery margin on standard packages are razor thin and would require too much time to recoup and that any advancements went to the “big boys” (freight and overnight) as they generate the most profit).
As such, any suggestion that this is an easy problem that can be solved by some math is obtuse. The system itself would have to be redesigned at a large scale and proven to work prior to testing as any error would cut profits that investors do not like.
Even in the classic problem, there is of course a crucial step of first using a Floyd–Warshall like algorithm to figure out the distances between your destinations.
Or specifically: why don't drivers get a preferred route along with their packages?
Maybe it's like a tech company with a known datacenter footprint and standard load pattern, so normal operations can be done in-house cheaper then in the cloud, but twice a year they have to do 200% traffic and just bite the bullet and scale that out in AWS at a much higher price, but only for those two days, compared to capacity that would sit idle the entire rest of the year.
The reason why that mostly works on AWS is that amazon has someone else to sell some of the peak capacity to the rest of the year. With package delivery, you'd need to figure out something profitable to do with the 'holiday delivery trucks' the rest of the year.
It's pretty hard to fine-tune a system for maximum efficiency most of the time, then make everything go 2X during a spike with the same level of efficiency. Especially when you're dealing with physical space and people who require training.
Most routes (at least here) have business stops which make up the majority of the bulk down the middle. If it's a resi route with a lot of irregulars (70-150lb packages, mattresses, etc) it'll be a mess.
The options to solve this are pretty much more trucks (there are none, and nowhere to put them after the "normal" seasonal increase), more drivers (hiring/training is an issue), making multiple trips (depends on distance from hub), or having parts of the route shuttled out.
I would go so far as to say that if they had invested in efficiency this way they could have developed their ORION project for far less money since they would be crowdsourcing at least the first major part of the solution from their workforce. Study that with sensors and data, and develop your algorithm from there. AFAIK, an experienced taxi driver is every bit as fast as a google maps traffic optimized route.
Can we now add UPS to the growing list of other HN-Commenter-Weekend-Projects? So far I’ve got Facebook, Twitter, Shazam.
Overall it seems the problem is fixed with brute force, taken to the extreme as in the topical article.