Stochastic Local Search : Foundations & Applications

Rating:
Summary: The First Complete Solution
Review: The Travelling Salesman Problem (more politically correctly called the Travelling Salesperson Problem)(How about we call it the TSP?) is a common real world problem. The problem is simplely stated: How do you find the shortest path for a travelling sales_____ to drive as he visits a series of customers.

If you're just running a few errands it's easy enough. If you're going to the supermarket, the post office, the dry cleaners, and the gas station, it's pretty easy to determine the shortest path. But then you add constraints, nearly out of gas, go to gas station first. Buying ice cream at the super market, better make it the last stop.

This is a real world problem. It is faced every day by delivery companies like the post office and air freight companies who spend huge amounts of fuel flying jet freighters around the world -- where do you put a hub, how do you schedule everything to come together.

FedEx solved this problem by running everything through Memphis. This works really well for a package going from New York to LA. It works less well for a package going from Manhattan to the Bronx. And if the package is going from London to Manchester ....

The computation of this and similar problems fall into the general category of Stochastic Local Search. And this book is the first to offer a systematic and unified treatment of SLS. Before this there were a series of technical papers, magazine articles and chapters in more general texts. The book provides the first unified view of the entire field and offers an extensive review of state-of-the-art algorithms and their applications. A companion website offers lecture slides as well as source code and Java applets for exploring and demonstrating the algorithms.