یک الگوریتم ژنتیک ترکیبی کارآمد برای مشکل مسیریابی موجودی چندمحصولی چند دوره ای

The inventory routing problem (IRP) addressed in this study is a many-to-one distribution network consisting of an assembly plant and many distinct suppliers where each supplies a distinct product. We consider a finite horizon, multi-periods, multi-suppliers and multi-products where a fleet of capacitated homogeneous vehicles, housed at a depot, transport products from the suppliers to meet the demand specified by the assembly plant in each period. The demand for each product is deterministic and time varying. A mathematical formulation of the problem is given and CPLEX 9.1 is run for a finite amount of time to obtain lower and upper bounds. A hybrid genetic algorithm, which is based on the allocation first route second strategy and which considers both the inventory and the transportation costs, is proposed. In addition to a new set of crossover and mutation operators, we also introduce two new chromosome representations. Several medium and small sized problems are also constructed and added to the existing data sets to show the effectiveness of the proposed approach.

The need for the integration and coordination of various components in a Supply Chain Management (SCM) has been recognized as an important factor for most companies to remain competitive. Most of the activities in the SCM are inter-related and changes in one part of the SCM are likely to affect the performance of other processes. Inventory management and transportation are two of the key logistical drivers of the SCM. Other components include production, location, marketing and purchasing (see Moin and Salhi (2007) for an overview). The coordination of these two drivers, often known as the inventory routing problems (IRP), is critical in improving the SCM. The IRP seeks to determine simultaneously an optimal inventory and distribution strategy that minimizes the total cost. The resulting inventory and transportation policies usually assign suppliers to routes and then determine the replenishment intervals and collection sizes for each supplier. The implementation of IRP is critical especially in a Vendor Managed Inventory (VMI) replenishment system where the supplier or manufacturer observes and controls the inventory levels of its customers or retailers. One of the most important benefits of VMI is that it permits a more uniform utilization of transportation resources. This leads to a higher level of efficiency and a much lower distribution cost that often constitutes the largest part of the overall cost. IRP can be broadly categorized according to the following criteria: planning horizon, single or multi-periods and whether the demand is deterministic or stochastic. Several other variants of IRP can also be found depending on the underlying assumptions in the models. We will first present a brief review emphasizing those studies that consider finite horizon, multi-period and deterministic demand as these are closely related to the proposed research. Most of the earlier works in IRP focus on a single period model, which is actually the classical vehicle routing problem (VRP). Federgruen and Zipkin (1984) are amongst the first to study the inventory routing problem. The problem was treated as a single day problem with a limited amount of inventory and the customers’ demands were assumed to be a random variable. They have extended and modified some well-known VRP heuristics to handle the problem that was formulated as a nonlinear integer program. The problem is decomposed into a nonlinear inventory allocation problem that aims to determine both the inventory and the shortage costs, and a traveling salesman problem (TSP) for each vehicle to find the least transportation cost. Federgruen et al. (1986) expand the idea for the case of perishable products. The solution has been adopted from their earlier work (Federgruen and Zipkin, 1984) with a variation that the inventory allocation subproblems account for two product classes instead. Chien et al. (1989) are among the first to simulate a multiple period planning model based on a single period approach. This is achieved by passing some information from one period to the next through inter-period inventory flow. In their problem, there is one central depot with all customers assigned to it. The capacity of the depot and the demand of the customers are fixed. An integer program is modeled using a Lagrangian dual ascent method to handle the allocation of the limited inventory available at the plant to the customers, the customer to vehicle assignments and the routing of the vehicles. A similar approach has been adopted by Fisher et al. (1982) to solve a real-life problem of inventory routing at Air Products, an industrial gases producer. The objective is to maximize the profit from product distribution over several days. The demand is given by the upper and lower bounds on the amount to be delivered to each customer for every period in the planning horizon. The effect of the short-term planning period in subsequent decisions has also been studied by Dror and Ball (1987) and Dror et al. (1985). They proposed an integer program where consequences of present decisions on later periods are accounted for using penalty and incentive factors. In this problem, the single period models are used as subproblems. A multi-period model with two types of customers, namely the vendor-managed inventory (VMI) customers and the customer managed inventory (CMI) customers, is proposed in Ribeiro and Laurenço (2002). The VMI customers face stochastic demands while the demands for the CMI customers are deterministic. In addition, the demand of all the CMI customers must be satisfied. On the one hand, the deliveries of products for the VMI customers are determined by the distributor who is also responsible for both the inventory holding cost and the stock-out cost at these customers. On the other hand, the CMI customers determine the amount to be delivered and the day in which the products need to be delivered; thus, the distributor is not liable to any inventory holding cost at these customers. The authors propose an iterated local search heuristic to determine the delivery routes (for both the VMI and the CMI customers) and the amount to be delivered for the VMI customers. The results show that this integrated model yields a better performance than its counterpart, the nonintegrated one. Recently, Yu et al. (2008) propose a hybrid approach to solve a large scale IRP. An approximate model was developed for a single product multi-period IRP with deterministic demands. The model incorporates a split delivery where deliveries to customers can be made by more than one vehicle. The split delivery was first introduced by Dror and Trudeau (1989) for the VRP by relaxing a constraint of the VRP that every customer is served by only one vehicle. This allows for a better utilization of the vehicles, thus reducing the transportation cost, especially if the mean of customers demand is not too small compared to the vehicle capacity (10% or more). However, it is worth noting that such flexibility obviously adds to the complexity of the problem. The authors design a Lagrangian relaxation method to generate a good solution that is then used to construct a near optimal solution of the IRP by solving a series of assignment problems. Bertazzi et al. (1997) propose a set of decomposition heuristics for the transportation of multi-product in multi-period with constant demand. Starting from a link by link solution of the problem (i.e. direct shipping), a local search is performed looking for improvement through consolidation. The second phase aggregates customers visited at the same frequency on the same route. The authors introduce the concept of split deliveries where the quantity of a product required at a destination may be split between different shipments, possibly with different frequencies. For simplicity, most multi-product models assume that each retailer requires only one type of product. We note that the same assumption is adopted in our model where each supplier is assumed to supply a distinct product to the assembly plant. Bertazzi et al. (2002) consider a multi-period model with deterministic demand in which a set of products is shipped from a supplier to several retailers. They adopted the order up to a level management inventory (S,s), where the maximum (S) and the minimum (s) levels of inventory are specified by each retailer and the products have to be replenished before the minimum level is attained. The quantity of the product delivered is the amount such that the maximum level is reached at the retailer. The authors proposed a two stage heuristic algorithm whereby the first stage focuses on route construction algorithms whilst the second stage attempts to improve the existing solution by performing simple swap operators that aim to remove or insert customers at different positions of the route used by the vehicle. This solution procedure is implemented for a single product and a single vehicle case only though the authors suggested that their approach can easily be modified to cater for the multi-product case. Lee et al. (2003) tackle a class of IRP where there are multiple suppliers and an assembly plant in an automotive part supply chain. They address the problem as a finite horizon, multi-period, multi-supplier, single assembly plant part-supply network. Each supplier supplies a distinct product and the objective of their study is to minimize the total transportation and inventory cost over the planning horizon. The problem is divided into two subproblems, namely the vehicle routing and the inventory control. The problem is formulated as a mixed integer programming model. They put forward a simulated annealing heuristic to generate and evaluate alternative sets of vehicle routes. Once the routes are determined, the model reduces to a linear programming model (LP) which is solved to obtain the optimum inventory level for each product. The authors also report that the optimal solution is mainly dominated by the transportation cost and is not sensitive to the unit inventory carrying cost. Our work is based on this interesting logistic problem for which some data sets exist (http://www.mie.utoronto.ca/labs/ilr/IRP/). Several models for the case of an infinite horizon have also been developed. These models attempt to minimize the long-run average, or mean average, cost where the lower bound for this cost can be derived. Several IRP with stochastic demands have also been studied, see for example (Campbell et al., 1998 and Trudeau and Dror, 1992). For a comprehensive review on IRP, we refer the reader to Moin and Salhi (2007). An interesting recent survey that focuses on the distribution of a single product over a finite planning horizon is given by Bertazzi et al. (2002). This paper is organized as follows: Section 2 provides an illustrative example of our IRP, followed by a mathematical formulation. The genetic algorithms are introduced in Section 3. An enhancement to the proposed algorithms is described in Section 4, followed by the presentation of our results in Section 5 and our conclusion is given in Section 6.

Both transportation and inventory costs ought to be considered concurrently in the logistic planning functions as these two areas might lead to significant gains and more competitive distribution strategies. In this paper, we present two representations using GA for the inventory routing problem on a finite horizon, multi-period and multi-product problem. We presented two types of modifications for the binary representations in order to overcome some of the limitations which we encountered. The binary representation and the modified binary representations outperformed the real representation in 13 out of 14 instances studied. With the increase of problem size especially for the problems with 98 suppliers, the performance of the GA based algorithms increases and the results were obtained in significantly less computational times. In these particular instances, the suppliers are closely located which is most appropriate for consolidated transportation strategy. The current algorithms do not incorporate powerful route improvement procedures though a simple 2-opt procedure is implemented at the end. The current algorithms give more emphasis on the benefit of consolidating the transportation to reduce the overall transportation cost and the inventory cost. However, reducing the routing cost can significantly reduce the total cost as it constitutes a large part of the total cost. It may therefore be interesting to dynamically use post-optimization at various generations and on specific chromosomes. This adaptive strategy is worth exploring further. The studied problem and the developed GA based heuristics can also provide interesting insights for solving other problems, especially in an outbound logistics where the demand pattern from one period to the other changes significantly.