The stochastic inventory routing problem

This dissertation addresses vehicle routing and inventory control in Inventory Routing Problems (IRPs). It closes a gap in the literature by proposing and evalulating exact and heurstic algorithms for the selective delivery and pickup vehicle routing problem (VRP) with the objective of maximizing profit by accepting unscheduled deliveries during a time-limited trip from the vehicle's orgin to it's scheduled destination. The disseration also determines the optimal on-hand inventory level for a manufacturer replenishing supply at a retailer who places orders at random time intervals as a result of random customer arrivals. The VRP includes two important constraints: the time constraint for the entire trip and the capacity constraint of the vehicle. A mixed integer programming (MIP) model is developed for this problem, which is shown to be NP-hard. Two exact methods are proposed to solve the problem: (1) branch-and-cut using CPLEX and (2) an exhaustive search algorithm. The exact methods are compared to a genetic algorithm that decomposes the problem into two parts: finding the feasible routes and generating the optimal delivery schedule on a given route. The first part is implemented in the C language and the optimal delivery schedule on a given route is found by CPLEX via the Callable Library in C. All three approaches are tested on randomly generated instances with up to 30 potential locations for pickup and delivery. The results show that the genetic algorithm is significantly faster than branch-and-cut, and although it is not an exact algorithm it is found to produce good quality solutions compared with the ten best solutions found by exhaustive search. The MIP described above is a node-arc formulation, which has O(n.;4 ) variables andO(n.;3 ) constraints, where n is the number of locations. This requires considerablecomputing resources (time and memory) to solve. The dissertation studies an alternative formulation of the VRP with the introduction of a new, compact representation of multicommodity flow. The new model reduces the number of variables and constraints in the MIP by a factor of n. Furthermore, the new formulation is shown to be stronger in the sense that its linear programming relaxation gives a very tight upper bound on the maximum profit. Computational experiments show that CPLEX can solve the new model significantly faster than the original MIP. Finally, the dissertation considers a production lot-sizing problem consisting of customers, one retailer, and one manufacturer. Demand from customers arrives randomly at the retailer one unit at a time, the retailer replenishes inventory from the manufacturer when its inventory is depleted to zero, and the manufacturer's production rate is assumed to be a constant. A production cycle starts when the manufacturer's inventory falls to or below zero and stops when its on-hand inventory reaches its optimal level. During the uptime in a production cycle, inventory is being built up while randomly arriving orders from the retailer are being fulfilled. The order arrival times from customers are independently and identically distributed. After solving renewal-type equations for the expected holding volume of the manufacturer's inventory in some part of the production cycle and the length of that part of the production cycle, I formulated an analytical model for the problem. However, the inventory processes at both the manufacturer and the retailer are renewal processes that are difficult to solve analytically for a general distribution of order arrival time. The elements that are difficult to solve turn out to have the form of the Volterra equation of the second kind, which does not have a closed-form solution. Therefore, a numerical search procedure is developed to obtain the optimal solution to the problem. Employing this approach, the disseration investigates how optimal solutions in different cases will change over the spectrum of some key parameters of the problem.