Re:The Dual Optimization of Air Freight: How Many iPhones Fi...
by millstone on Thursday April 30, 2015 @02:06AM
(#9463556)
It's not the knapsack problem. The task is similar: maximize (some relation between) the carried volume and weight. But instead of a finite collection of different items, you have an essentially infinite set of a few items. Also, the weight and volume of each individual item is negligible, so you don't have to worry about the integer nature of the problem, i.e. it's sufficient to give a fractional answer and round down. (That's what makes the knapsack hard - the fact that you can't add fractional items.) This seems like a straightforward linear programming problem, solvable via the simplex method.
Re:The Dual Optimization of Air Freight: How Many iPhones Fi...
by MrBuddyCasino on Thursday April 30, 2015 @04:35AM
(#9463916)
Yeah linear programming was my first thought, too. How is that "one of the best kept secrets in the air cargo industry"?
Re:The Dual Optimization of Air Freight: How Many iPhones Fi...
by raverbashing on Thursday April 30, 2015 @05:53AM
(#9464114)
> How is that "one of the best kept secrets in the air cargo industry"?
I guess it's only part of the problem, solving for one plane.
In practice you would want to solve for varying demand, for multiple customers, for planes that eventually are delayed, crews that get sick/delayed, for different planes, for routes that pick/drop different cargo at different places.
And of course, you want to price all of that in a way that makes you money.
Re:The Dual Optimization of Air Freight: How Many iPhones Fi...
by rs232 on Thursday April 30, 2015 @07:21AM
(#9464350)
It is not a secret. It is a basic day to day task to optimize this. If you didn't you'd be out of business very quikcly.
Re:The Dual Optimization of Air Freight: How Many iPhones Fi...
by ojbyrne on Thursday April 30, 2015 @12:09AM
(#9463301)
Actually that's not quite correct. The knapsack problem has 2 constraints: weight and (traditionally) "utility." This problem has 3 constraints - weight, volume and utility. That probably makes the problem more tractable.
Re:The Dual Optimization of Air Freight: How Many iPhones Fi...
by Dylan16807 on Thursday April 30, 2015 @03:26AM
(#9463721)
In addition to the other comments, keep in mind that this is such an enormous knapsack that dumping in items at random is just as efficient as any other method.
It's proven to be NP-Hard, but with a well known "good enough" approximation ("the knapsack problem has a fully polynomial time approximation scheme (FPTAS)")