The Logic of Logistics

1 Introduction.- 1.1 What Is Logistics Management?.- 1.2 Examples.- 1.3 Modeling Logistics Problems.- 1.4 Logistics in Practice.- 1.5 Evaluation of Solution Techniques.- 1.6 Additional Topics.- 1.7 Book Overview.- I Performance Analysis Techniques.- 2 Worst-Case Analysis.- 2.1 Introduction.- 2.2 The Bin-Packing Problem.- 2.2.1 First-Fit and Best-Fit.- 2.2.2 First-Fit Decreasing and Best-Fit Decreasing.- 2.3 The Traveling Salesman Problem.- 2.3.1 A Minimum Spanning Tree Based Heuristic.- 2.3.2 The Nearest Insertion Heuristic.- 2.3.3 Christofides' Heuristic.- 2.3.4 Local Search Heuristics.- 2.4 Exercises.- 3 Average-Case Analysis.- 3.1 Introduction.- 3.2 The Bin-Packing Problem.- 3.3 The Traveling Salesman Problem.- 3.4 Exercises.- 4 Mathematical Programming Based Bounds.- 4.1 Introduction.- 4.2 An Asymptotically Tight Linear Program.- 4.3 Lagrangian Relaxation.- 4.4 Lagrangian Relaxation and the Traveling Salesman Problem.- 4.4.1 The 1-Tree Lower Bound.- 4.4.2 The 1-Tree Lower Bound and Lagrangian Relaxation.- 4.5 The Worst-Case Effectiveness of the 1-tree Lower Bound.- 4.6 Exercises.- II Vehicle Routing Models.- 5 The Capacitated VRP with Equal Demands.- 5.1 Introduction.- 5.2 Worst-Case Analysis of Heuristics.- 5.3 The Asymptotic Optimal Solution Value.- 5.4 Asymptotically Optimal Heuristics.- 5.5 Exercises.- 6 The Capacitated VRP with Unequal Demands.- 6.1 Introduction.- 6.2 Heuristics for the CVRP.- 6.3 Worst-Case Analysis of Heuristics.- 6.4 The Asymptotic Optimal Solution Value.- 6.4.1 A Lower Bound.- 6.4.2 An Upper Bound.- 6.5 Probabilistic Analysis of Classical Heuristics.- 6.5.1 A Lower Bound.- 6.5.2 The UOP(?) Heuristic.- 6.6 The Uniform Model.- 6.7 The Location-Based Heuristic.- 6.8 Rate of Convergence to the Asymptotic Value.- 6.9 Exercises.- 7 The VRP with Time Window Constraints.- 7.1 Introduction.- 7.2 The Model.- 7.3 The Asymptotic Optimal Solution Value.- 7.4 An Asymptotically Optimal Heuristic.- 7.4.1 The Location-Based Heuristic.- 7.4.2 A Solution Method for CVLPTW.- 7.4.3 Implementation.- 7.4.4 Numerical Study.- 7.5 Exercises.- 8 Solving the VRP Using a Column Generation Approach.- 8.1 Introduction.- 8.2 Solving a Relaxation of the Set-Partitioning Formulation.- 8.3 Solving the Set-Partitioning Problem.- 8.3.1 Identifying Violated Clique Constraints.- 8.3.2 Identifying Violated Odd Hole Constraints.- 8.4 The Effectiveness of the Set-Partitioning Formulation.- 8.4.1 Motivation.- 8.4.2 Proof of Theorem 841.- 8.5 Exercises.- III Inventory Models.- 9 Economic Lot Size Models with Constant Demands.- 9.1 Introduction.- 9.1.1 The Economic Lot Size Model.- 9.1.2 The Finite Horizon Model.- 9.1.3 Power of Two Policies.- 9.2 Multi-Item Inventory Models.- 9.2.1 Introduction.- 9.2.2 Notation and Assumptions.- 9.2.3 Worst-Case Analyses.- 9.3 A Single Warehouse Multi-Retailer Model.- 9.3.1 Introduction.- 9.3.2 Notation and Assumptions.- 9.4 Exercises.- 10 Economic Lot Size Models with Varying Demands.- 10.1 The Wagner-Whitin Model.- 10.2 Models with Capacity Constraints.- 10.3 Multi-Item Inventory Models.- 10.4 Exercises.- 11 Stochastic Inventory Models.- 11.1 Introduction.- 11.2 Single Period Models.- 11.3 Finite Horizon Models.- 11.4 Quasiconvex Loss Functions.- 11.5 Infinite Horizon Models.- 11.6 Multi-Echelon Systems.- 11.7 Exercises.- IV Hierarchical Models.- 12 Facility Location Models.- 12.1 Introduction.- 12.2 An Algorithm for the p -Median Problem.- 12.3 An Algorithm for the Single-Source Capacitated Facility Location Problem.- 12.4 A Distribution System Design Problem.- 12.5 The Structure of the Asymptotic Optimal Solution.- 12.6 Exercises.- 13 Integrated Logistics Models.- 13.1 Introduction.- 13.2 Single Warehouse Models.- 13.3 Worst-Case Analysis of Direct Shipping Strategies.- 13.3.1 A Lower Bound.- 13.3.2 The Effectiveness of Direct Shipping.- 13.4 Asymptotic Analysis of ZIO Policies.- 13.4.1 A Lower Bound on the Cost of Any Policy.- 13.4.2 An Efficient Fixed Partition Policy.- 13.5 Asymptotic Analysis of Cross-Docking Strategies.- 13.6 An Algorithm for Multi-Echelon Distribution Systems.- 13.7 Exercises.- V Logistics Algorithms in Practice.- 14 A Case Study: School Bus Routing.- 14.1 Introduction.- 14.2 The Setting.- 14.3 Literature Review.- 14.4 The Problem in New York City.- 14.5 Distance and Time Estimation.- 14.6 The Routing Algorithm.- 14.7 Additional Constraints and Features.- 14.8 The Interactive Mode.- 14.9 Data, Implementation and Results.- 15 A Decision Support System for Network Configuration.- 15.1 Introduction.- 15.2 Data Collection.- 15.3 The Baseline Feature.- 15.4 Flexibility and Robustness.- 15.5 Exercises.- References.