Inventory routing problem with satellite facilities

This dissertation studies an inventory routing problem with satellite facilities (IRPSF). The major contributions are: (1) A cost analysis procedure to reduce a long term optimization problem into a short term problem. (2) A rolling horizon scheme for solving the IRPSF, and heuristics for the vehicle routing problem with satellite facilities (VRPSF). (3) A branch and cut procedure to obtain optimal solution of the VRPSF.; The inventory routing problem (IRP) is a distribution problem in which customers rely on a central supplier for a certain commodity and keep inventory in a storage tank. The objective is to minimize the annual delivery costs while attempting to insure no stockout for each customer. A procedure for reducing a long term problem into a short term problem is proposed. An important aspect of the accompanying analysis is the derivation of the incremental cost function which reflects the long term cost. Customer selection and assignment rules are also presented. After the reduction, an IRP can be attacked by solving a series of routing problems.; A comprehensive decomposition scheme for solving the IRPSF is developed. A unique aspect of the short-term subproblem is the presence of satellite facilities where vehicles can be reloaded and customer deliveries continued until the closing time of the route is reached.; Three heuristics have been developed to solve the VRP with satellite facilities (randomized Clarke-Wright, GRASP, modified sweep). After the daily tours are derived, a parametric analysis is conducted to investigate the trade-off between distance and annual costs. This leads to the development of the efficient frontier from which the decision maker is free to choose the most attractive alternative. The proposed procedures are tested on data sets generated from field experience with a national liquid propane distributor.; A branch and cut methodology for solving the VRP with satellite facilities subject to capacity and route time constraints has been studied and implemented. We begin with a mixed-integer linear programming formulation and then describe a series of valid inequalities that can be used to cut off solutions to the linear programming relaxation without eliminating any feasible integer points. Several separation heuristics are then outlined that are used to generate the cuts. Embedded in the methodology is a VRP heuristic for finding good feasible solutions at each stage of the computation. Results are presented for a set of problems derived from our experience with a leading propane distributor.