Part I

I wrote quickly and was not very clear for people
without good backgrounds in optimization.

> You really wrote the algorithm for FedEx? Thats
amazing!

In the sense of business, it actually was "amazing":
Likely it saved the company from going out of
business. Too many Members of the Board of
Directors were concerned that there could be no
suitable schedule. So, one evening Roger Frock and
I used my software to develop a schedule for all
planned 33 airplanes and all planned 90 US cities.

Printed out, FedEx founder, COB, CEO F. Smith said
at the next senior staff meeting "Amazing document.
Solved the most important problem facing Federal
Express.".

Two guys representing Board Member General Dynamics
went over the schedule and announced "It's a little
tight in a few places, but it's flyable.". Then the
Board was happy. As I recall, $55 million in
funding was enabled, not all equity.

So, the software was "amazing" just as business.
But as applied math, the software was junk! Work
for the real, pressing, short term business problem?
Yes. Really optimization? No!

But I did continue and saw that what I should do was
(1) generate some thousands of 'feasible' trips from
Memphis and back and for each carefully add up the
direct costs, (2) set up a 0-1 integer linear
programming problem with one row for each of the 90
cities and one column for each of the thousands of
feasible trips. Then each row says to serve some
one city. Each variable, 1 or 0, one for each
column, says to use that trip or not. Right: It's
0-1 integer linear programming set covering, yes, in
NP-complete.

So, that's a linear program with only 90 rows. Just
as a linear program, that's promising, likely easy.

Make money? My only competition was a guy with a
map of the US on a sheet of 8 1/2 x 11" paper. He
didn't have a reasonable way even to add the costs
of a candidate schedule or print it out. So, yes,
my work should have saved a bundle.

If nothing else, just solve the LP without the 0-1
constraints (with only 90 rows, that should be
easy), look at the results, and see if have an easy,
not very expensive way to patch up the fractions to
0-1 by hand. Else do a little branch and bound. If
attacking the whole problem for the whole country is
too difficult, then attack it for parts of the
country separately; e.g., what do in the East has
next to nothing to do with what do in the West; the
goal is not to announce that have the 'optimal'
solution down to the last fraction of the last
penny; instead, the goal is to save money. Don't be
embarrassed about not guaranteeing to save the last
$1000 or the last $1,000,000 a month; instead be
just horrified about not saving the first $10
million a month.

Also do a little duality theory to get a bound on
how much more money might be saved. When have saved
the first $10 million and have no more than another
$1,000 to save, take the best feasible solution so
far and quit.

About then I'd gotten on an airplane and run off to
chat about optimization with G. Nemhauser, then
still at Cornell, J. Elzinga, then still at Hopkins,
and J. Pierce, then in Cincinnati, got a stack of
books and papers, etc.

There was also another problem: Our fuel prices and
availabilities varied widely by airport. So, a
question was, how much fuel to buy at each stop?
So, buy extra fuel where it is cheap and available.
This is called 'fuel tankering'. But, yes, will
burn off some of the extra fuel carrying it.

How much extra fuel is burned off is fairly
sensitive to the vertical flight plan used; so also
need to select vertical flight plan in a coordinated
way. The problem is also complicated by the fact
that package pickup loads are not known until the
plane arrives for the pickup, and those loads will
affect the fuel burned for each candidate vertical
flight plan. Then those loads will also affect how
much fuel can be carried. Also relevant is that the
fuel burned and flight time for a vertical flight
plan and a load are affected by essentially random
winds, air traffic control, and flying around summer
thunder storms. Also really get charged not just
for fuel but also time on the engines. So, it was
complicated.

Now, try to find a way in practice to advise the
pilot on what to do? So, right, it's another
optimization problem -- partly discrete, nonlinear,
sequential, stochastic. So, right, stochastic
dynamic programming. Doable? Actually, yes, quite
doable. On a computer today, could solve the
problem for, say, five stops, with weight
discretized at 100 pounds in about the time it takes
to get a finger off the Enter key or the mouse button.

Also for the vertical flight plans, I went to MIT
and chatted with M. Athans about deterministic
optimal control theory.