9 ms·

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.

by kjrose 9y ago

FabHK 9y ago
The Traveling Salesman problem is very well known. What other problem do you have in mind? https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem
- kccqzy 9y ago
  The travelling salesman problem in its classic formulation simply wants the shortest path. But there can be other optimization goals like minimum fuel consumption, which might favor dropping off heavier packages first. Or perhaps minimum total time spent, which entails considering the dynamic traffic conditions like Google Maps or Waze does. 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.
elliotec 9y ago
I’m sure UPS will be hiring for holiday shifts next year, you can put it to good use!
- make3 9y ago
  I'm not sure what you're implying, this would actually be extremely worth while for UPS
  - nagVenkat 9y ago
    He is being sardonic. UPS employs some of the best minds in optimization. The case you mentioned is probably not that complicated for UPS.
viraptor 9y ago
Looking at truck size, this doesn't even look like a very hard problem. You can essentially solve it per neighbourhood / post code and then inside each of those sections separately for a good approximation. The interesting question is: why doesn't UPS think that's worth doing? Or are there some fun constraints we're not aware of? Or specifically: why don't drivers get a preferred route along with their packages?
- majormajor 9y ago
  It sounds like they do, but that it breaks down when the trucks get overfull. I wonder if there's a breaking point where the projection of just how full the trucks will be, which packages will get to be thrown as overfill in which trucks, and how many will fit in each, is outside the operating bounds of their system and they know it's only a handful of days a year so they just brute force it instead of investing a lot (more trucks or more drivers would be the non-algorithmic sort of investment) for a recurring-but-tiny edge case. 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.
  - lsc 9y ago
    >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.
    - c22 9y ago
      Sounds like the rest of the year they handle the accounting...
coderdude 9y ago
Isn't it this problem? https://en.m.wikipedia.org/wiki/Bin_packing_problem https://en.m.wikipedia.org/wiki/Bin_packing_problem One which seems intuitively like you could easily solve it but cannot?
JurgenKlein 9y ago
Isn't this the traveling salesman problem?
stephenboyd 9y ago
I worked at UPS for a season loading their delivery trucks. Each shift was like a really intense game of 3D Tetris, trying to use the space efficiently as more heavy packages of various shapes rapidly arrived from the conveyor belt. So you're not just optimizing the path-finding. You've also got to do optimal bin-packing at the same time.
- posterboy 9y ago
  To squeeze every last dollar out of the available space becomes a quite literal meaning in this context. The ammount of the packages ariving damaged from the sheer load of each on top on another in the containers is really impressive, too.
bardworx 9y ago
I’ve diacussed this with a buddy of mine a few years ago. For validation: he is a senior manager at FedEx in Ohio region, dealing with standard delivery (non-rush, overnight, or freight). 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.
froindt 9y ago
They're working on it. They've substantially increased their data collection on the vehicles and their delivery routes in the last decade. Their drivers union stipulates nobody will be fired solely because of sensor data, and that as the efficiency grows, the pay will grow proportionally. A driver delivers many more packages per day now than 10 years ago. 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-with-jack-levis https://blogs.oracle.com/database/big-data-at-ups-interview-... https://youtu.be/CsJRsToDI8w https://youtu.be/CsJRsToDI8w https://www.google.com/amp/s/www.wired.com/2013/06/ups-astronomical-math/amp https://www.google.com/amp/s/www.wired.com/2013/06/ups-astro...
- LMYahooTFY 9y ago
  Interesting to see how much they've invested into Orion. I've been working as a seasonal driver, and where I am it's universally ignored, every driver simply uses the "regular delivery order". I think it's plausible many haven't tried it. I'd like to try using it before I finish.
c3534l 9y ago
Are you talking about the packing problem or the traveling salesmen problem? Both are NP. Though so is k-means and we can still do a good job with stochastic search.

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.

by kjrose 9y ago

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.

FabHK 9y ago

The Traveling Salesman problem is very well known. What other problem do you have in mind? https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem

kccqzy 9y ago
The travelling salesman problem in its classic formulation simply wants the shortest path. But there can be other optimization goals like minimum fuel consumption, which might favor dropping off heavier packages first. Or perhaps minimum total time spent, which entails considering the dynamic traffic conditions like Google Maps or Waze does. 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.

elliotec 9y ago

I’m sure UPS will be hiring for holiday shifts next year, you can put it to good use!

make3 9y ago
I'm not sure what you're implying, this would actually be extremely worth while for UPS
- nagVenkat 9y ago
  He is being sardonic. UPS employs some of the best minds in optimization. The case you mentioned is probably not that complicated for UPS.

viraptor 9y ago

Looking at truck size, this doesn't even look like a very hard problem. You can essentially solve it per neighbourhood / post code and then inside each of those sections separately for a good approximation. The interesting question is: why doesn't UPS think that's worth doing? Or are there some fun constraints we're not aware of? Or specifically: why don't drivers get a preferred route along with their packages?

majormajor 9y ago
It sounds like they do, but that it breaks down when the trucks get overfull. I wonder if there's a breaking point where the projection of just how full the trucks will be, which packages will get to be thrown as overfill in which trucks, and how many will fit in each, is outside the operating bounds of their system and they know it's only a handful of days a year so they just brute force it instead of investing a lot (more trucks or more drivers would be the non-algorithmic sort of investment) for a recurring-but-tiny edge case. 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.
- lsc 9y ago
  >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.
  - c22 9y ago
    Sounds like the rest of the year they handle the accounting...

coderdude 9y ago

Isn't it this problem? https://en.m.wikipedia.org/wiki/Bin_packing_problem https://en.m.wikipedia.org/wiki/Bin_packing_problem One which seems intuitively like you could easily solve it but cannot?

JurgenKlein 9y ago

Isn't this the traveling salesman problem?

stephenboyd 9y ago

I worked at UPS for a season loading their delivery trucks. Each shift was like a really intense game of 3D Tetris, trying to use the space efficiently as more heavy packages of various shapes rapidly arrived from the conveyor belt. So you're not just optimizing the path-finding. You've also got to do optimal bin-packing at the same time.

posterboy 9y ago
To squeeze every last dollar out of the available space becomes a quite literal meaning in this context. The ammount of the packages ariving damaged from the sheer load of each on top on another in the containers is really impressive, too.

bardworx 9y ago

I’ve diacussed this with a buddy of mine a few years ago. For validation: he is a senior manager at FedEx in Ohio region, dealing with standard delivery (non-rush, overnight, or freight). 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.

froindt 9y ago

They're working on it. They've substantially increased their data collection on the vehicles and their delivery routes in the last decade. Their drivers union stipulates nobody will be fired solely because of sensor data, and that as the efficiency grows, the pay will grow proportionally. A driver delivers many more packages per day now than 10 years ago. 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-with-jack-levis https://blogs.oracle.com/database/big-data-at-ups-interview-... https://youtu.be/CsJRsToDI8w https://youtu.be/CsJRsToDI8w https://www.google.com/amp/s/www.wired.com/2013/06/ups-astronomical-math/amp https://www.google.com/amp/s/www.wired.com/2013/06/ups-astro...

LMYahooTFY 9y ago
Interesting to see how much they've invested into Orion. I've been working as a seasonal driver, and where I am it's universally ignored, every driver simply uses the "regular delivery order". I think it's plausible many haven't tried it. I'd like to try using it before I finish.

c3534l 9y ago

Are you talking about the packing problem or the traveling salesmen problem? Both are NP. Though so is k-means and we can still do a good job with stochastic search.