The next chapter considers the probabilistic analysis of algorithms via the characterization of the average performance of a given heuristic. The analysis is asymptotic with large problem sizes needed. Again, the bin-packing and traveling salesman problems are considered for studying this approach. This is followed by an approach to studying the efficacy of a particular heuristic by using mathematical programming in the next chapter. The strategy here is to cast the (NP-complete) problem as an integer problem, and then relax the constraint of integrality and solve the linear program. The authors showthat tight lower bounds can be found for these integer programs. The authors switch gears somewhat in the next two chapters, where vehicle routing problems are studied. In particular, the single-depot capacitated vehicle routing problem with equal and unequal demands is analyzed via worst-case and probabilistic analysis. The analysis is generalized in chapter 7 for the case where time constraints are present. An analytical solution of this problem, called the vehicle routing problem with time windows, is considered in detail by the authors. They back up their analysis with computational results at the end of the chapter. In chapter 8, a column generation approach is employed to solve the vehicle routing problem. No time constraints are put in, and the authors give in detail the steps behind this technique.
The study of inventory models is begun in chapter 9, with the economic lot size model leading off the discussion. This model illustrates effectively the tradeoffs between ordering and storage costs, and the optimal ordering policy is found. This model is generalized to the case where finite time horizons are included and the optimal policing found. Multi-item inventory models are then studied via worst-case analysis. The Wagner-Whitin model, which is an inventory model with varying demands, is formulated and solved in the next chapter. The techniques used, interestingly, involve dynamic programming. This model is generalized to the case where there is an upper bound on the amount that can be ordered or produced, and then the optimal solution found.
The case where the demand is a random variable is considered in the next chapter on stochastic inventory models. Single period and finite horizon models are considered using a dynamic programming algorithm to determine the optimal policy. The analysis makes heavy use of the properties of convex and quasiconvex functions.
Facility location models are the subject of the next chapter. The p-Median, single-source capacitated facility location (CFLP), and distribution system design problems are analyzed as warehouse location problems, with Lagrangian relaxation techniques used to find the solutions to these problems.
Logistics models that integrate inventory and routing strategies are considered in chapter 13, with the success of Wal-Mart given as an example of a firm whose success was generated by a reliance on an efficient logistical design and planning model called cross docking. Along with analyses of zero inventory ordering policies, the authors give an asymptotic analysis of cross-docking strategies.
The last two chapter of the book consider the implementation of logistic algorithms in practice. Although short, the chapters do give a fairly good overview of how these algorithms are used in the real world. The authors consider the routing and scheduling of New York City school buses and a decision support system for network configuration. Only one exercise is found in these chapters though unfortunately.