This is not the optimum solution,
but a solution obtained with a 2-change procedure starting from
a greedy solution.
One might say that this Excel approach has reached a level
of competence obtained 50 years ago by Dantzig and his famous
co-authors. The commenter should remember, however, that this
solution was obtained with a computer that is similar to those
on millions of desktops, with a spreadsheet program used daily
by a great number of many all over the world, with an add-in
that is freely distributed on the web. This solution was found
in 21 seconds and certainly running the program longer will
improve it. Moreover, the source code is open to all to modify
for specific applications and add new heuristics. Our purpose
was to make the solution of this and other combinatorial problems
easily accessible to a wide audience, and these add-ins are
a good start.
The problem of finding the optimum sequence
of jobs through a flow shop has a solution that may be represented
by a tour. The *Combinatorics *add-in has a model that
incorporates lateness penalties, setup times and time windows.
The objective value depends on a complex series of Excel calculations,
some involving logical IF expressions. It would be very difficult
to write this function in a closed form algebraic expression.
The solution is found using the same heuristics as used for
the traditional TSP.
The routing
problem addressed by the *Combinatorics* add-in is
also similar to the TSP, but here we are dealing with a vehicle
that starts at a depot, visit several sites and returns to the
depot. The objective is to minimize the travel cost plus a cost
that depends on the times of deliveries to the cities. |