| Doing logistics well can be a competitive advantage in today's business environment. Improving the logistics productivity of the distribution system is particularly important because distribution is often the sole interface between the firm and its customers. The objective of the distribution system design problem is to specify the number, sizes and locations of the warehouses or distribution centers and to determine the transportation flows between the facilities and the customers in such a way that total facility, inventory and transportation casts are minimized and customer service requirements are satisfied. Because the distribution systems we study are characterized by multiple-stop delivery routes, the facility location and the vehicle routing decisions are interdependent. Hence, the distribution system design problem is an NP-hard location-routing problem.;We present two new set-partitioning-based formulations of a location-routing problem (LRP) with distance constraints. We demonstrate why the initial model, an intuitive formulation, is ineffective. We identify an alternative set of side constraints, which results in a stronger model with fewer total constraints. We develop and implement a column generation heuristic and a partial branch-and-price algorithm for the model. Computational results are reported for instances constructed from geographic data and randomly generated data. Instances as large as 25 candidate facilities and 150 customers are solved to optimality.;We provide analytical results for the distance-constrained location-routing problem defined on special network structures. We show that we can solve the LRP in polynomial time by transforming it into an equivalent shortest path problem. We prove that the LP relaxation of the formulation of the LRP on paths has integral optimal solutions. For the LRP on trees, we develop a polynomial-time algorithm and show that the LP relaxation has fractional optimal solutions. We make progress towards identifying a set of inequalities that in conjunction with the LP relaxation is sufficient to describe the convex hull of the integral solutions for a specially structured tree. We explore a number of model extensions and conclude with ideas for future research. |
