روش جستجوی محلی برای مشکل مسیریابی موجودی دوره ای

Inventory routing problem considers inventory allocation and routing problems simultaneously, in which the replenishment policies and routing arrangement are determined by the supplier under the vendor managed inventory mode. What we consider here is a periodic inventory routing problem that once the delivery time, quantity and routing are determined, they will remain the same in the following periods. The problem is modeled concisely, and then it is decomposed into two subproblems, inventory problem and vehicle routing problem. The inventory problem is solved by proposing a local search method, which is achieved by four operators on delivery quantity and retailer’s demand. Insertion operator aims to insert a new replenishment point of a retailer while removal operator is to remove a replenishment point. Besides, addition operator is adopted as an assistant tool, and crossover operator is proposed for some special cases. We also propose a tabu search method to solve the routing problem. Finally, the computational results show that the method is efficient and stable.

The inventory routing problem (IRP) considers inventory allocation and routing problems simultaneously in a supply chain system, in order to achieve a better overall performance. Generally, IRP can be described as: in a supply chain system that consists of one supplier and many geographically dispersed retailers each with deterministic demand, products are shipped from the supplier to retailers with some identical vehicles over a given time horizon. Each retailer is served by at most one vehicle each time unit. Under the vendor managed inventory (VMI) mode, the supplier determines the replenishment policy of each retailer as well as the vehicle routes, guaranteeing that no stock out occurs. The objective of IRP is to minimize the total cost, including distribution cost and inventory cost of retailers. In IRP, the problem is not only to find the delivery routes, but also the quantity to deliver as well as the time for delivery. In this paper, we study the periodic IRP in a two-echelon supply chain system over a given time horizon. As the characters of periodic IRP, once the delivery times, quantities and vehicle routes are determined, they remain the same in the following horizons. In the problem, what we should pay the most attention to is that the totally delivered quantity equals the demand over the horizon for each retailer. The initial inventory level of a retailer is omitted, as once the replenishment policy changes, the initial inventory level of the system will change simultaneously. (As is shown in Fig. 1, a periodic IRP with the period of seven time units and the demand rate equals one is illustrated. Under the replenishment policy A, the initial inventory level of each period equals zero; while if the replenishment policy is replaced by B, the initial inventory level of each period will result in one.) Therefore, stock out never occurs in periodic IRP. The objective of our problem is to minimize the total cost, which includes inventory cost and routing cost. Full-size image (20 K) Fig. 1. Initial inventory level varies with the replenishment policy. Figure options Much attention has been paid to IRP in the last 30 years. To our best knowledge, Federgruen and Zipkin (1984) were among the first to integrate inventory allocation problem and routing problem. The efficiency obtained by addressing IRP is considerable. According to Miyamoto and Kubo’s (2001) case study of large soft drink firms, the IRP system could save about 40% of total working hours; In Gaur and Fisher’s (2004) case study in Netherlands, the IRP system saved 4% of distribution costs in the first year; Also, according to Fu and Fu (2010), the IRP outcome could save cost at about 7.3%, compared to their separate optimization. In the following part of this section, we will review literatures that have done some contributes on IRP characteristics. We refer the readers to the articles Moin and Salhi (2007) and Andersson, Hoff, et al. (2010) for more literatures with other contributions. Speranza and Ukovich (1994) considered IRP with multiple products. In the article, several products were shipped on the same link by vehicles with limited capacity, while the vehicles might leave only at some given discrete times. Viswanathan and Mathur (1997) then extended the problem above to as system with multiple retailers. A heuristic method with a stationary nested replenishment policy was proposed. Qu, Bookbinder, et al. (1999) considered the situation of multi-products with a central warehouse and several suppliers of stochastic demands. A heuristic solution method which decomposed the problem into inventory and routing problems was proposed. Sindhuchao, Romeijn, et al. (2005) also studied the problem, and a column generation approach was employed to determine a lower bound of the total costs, while a branch-and-price algorithm was developed to find the optimal assignment of items to vehicles. Bertazzi (2008) considered multiple products in IRP with direct delivery. The worst-case performances of the best single, best double, best triple, best frequency-based, and optimal direct shipping policies were showed in the article. Yu, Chen, et al. (2008) studied IRP with split delivery (IRPSD). Split delivery can increase the flexibility of the routing problem, and it could further reduce the transportation cost. As in IRPSD, deliveries to each customer at each time unit could be performed by multiple vehicles. An approximate approach based on an approximate model and Lagrangian relaxation was proposed. Wan and Zhang (2008) studied a supply chain consists of multiple suppliers, single assembly plant network in IRP with split pick-up. A mixed integer programming model was proposed and the problem was solved by genetic algorithm. Moreover, Li, Chu, et al. (2011) considered the coordination where two split deliveries were realized by direct shipping and multiple-stop shipping, respectively. A non-linear programming model was established, and both policies were showed effective under certain conditions. Giesen, Mahmassani, et al. (2005) considered IRP under real-time information with a supplier and multiple retailers. The system was controlled by a central decision maker who operated with real-time information about the complete state of the system. Giesen, Mahmassani, et al. (2009) then extended the problem to the situation that vehicle delivery routes could be updated using real-time information about current inventory levels and vehicle status. Jarugumilli, Grasman, et al. (2006) also considered the problem. In the article, the information update occurred when a vehicle arrived at a retailer, and then, the decisions on delivery quantity and which retailer was to be visited were made. Lei, Liu, et al. (2006) considered an integrated production problem with IRP (PIRP). The system consisted of a set of plants and retailers, while each plant with its own production capacity, inventory capacity, raw material supply contract, inventory holding cost, and production cost. The objective was to determine the operation schedules to coordinate production, inventory, and transportation routing operations so that the overall cost was minimized. A two-phase solution approach was proposed. Moreover, Forma, Raviv, et al. (2008) involved the pick-up problem in PIRP. The problem was formulated as a mixed integer program with tours enumeration. Bard and Nananukul (2009) considered PIRP in a supply chain with a single production facility and a set of customers. A procedure centering on reactive tabu search was proposed, and a path relinking strategy was applied to improve the results. They studied the same problem in Bard and Nananukul (2010) and a mixed-integer programming model was investigated. Liu and Lee (2003) studied IRP with location problem (LIRP), where number of candidate depots were decided to be built or not. The objective was to minimize the sum of depot establishing cost which depended on whether a depot was open or not, as well as the transportation cost and inventory cost. A two-phase heuristic method was proposed. Shen and Qi (2007) proposed a LIRP in a three-echelon supply chain, which consisted of one supplier, multiple distribution centers (DCs) and multiple customers. DCs were served directly by the supplier and distributed products to customers. The problem was to determine how many DCs to locate, where to locate them, as well as customers’ replenishment policies, so as to minimize total location, shipment, and inventory costs. Bo, Zujun, et al. (2008) involved LIRP and a mixed genetic algorithm was proposed. Javid and Azad (2010) also considered the problem. Firstly, an exact solution method by casting the problem as a mixed integer convex problem was presented, and then, a heuristic method based on a hybridization of tabu search and simulated annealing was established. Shu-Chu and Jyun-Ruei (2011) involved pricing decision in IRP. The objective was to maximize profit of the supply chain instead of minimizing the total cost. A mathematical model was proposed, and a tabu search adopting different neighborhood search approach was used to obtain the optimal solution. Gaur and Fisher (2004) considered a periodic IRP at a leading supermarket chain in Netherlands. The article sought to determine a weekly delivery schedule specifying the times when each store should be replenished as well as the vehicle routes. The demand at each store is random and varies with time. They considered the solution of the problem with fixed partition policies (FPP), and the company realized savings of about 4% of its transportation cost in the first year of implementation. Zachariadis, Tarantilis, et al. (2009) proposed a local search method for periodic IRP. In the paper, a solution approach applying two innovative local search operators which named insertion and removal operators was proposed. And their framework was tested and resulted both in terms of effectiveness and robustness. However, the demand rate was determined and same at each time unit, which is not so realistic. Many supermarkets, i.e. faces a periodic demand rate every week, but varies every day. Also, a model with the replenishment quantity, demand rate and the inventory level at each time unit was formulated. In periodic IRP, the inventory levels that change simultaneously along with the replenishment policy are not thus important. There is no need to calculate them each time when a new policy is obtained (A new method to obtain the inventory cost without involving inventory level is proposed in Section 3.2.1). Moreover, a special case that is not applicable for the two operators proposed by the article is omitted. For instance, we consider a supply chain with one supplier and nine retailers, and the given time horizon is three, while the maximum vehicle capacity is 300. As we can see in Table 1, the same route (0–1–3–6–4–8–7–0) occurs at each time unit of the horizon, while the vehicle loads equal to the maximum capacity. As replenishment point occurs in each time unit, the insertion operation is not applicable to retailers 1, 3, 4, 6, 7, 8; in the meanwhile, the removal operator is also inapplicable because of the vehicle capacity constraint. Table 1. A special case. Table options The main contribution of this paper is twofold: firstly, a new model for a periodic IRP is formulated. Without referring to the inventory levels of retailers, a novel method is proposed to obtain inventory cost in the objective. Secondly, a local search method without referring to the inventory level is proposed and a tabu search algorithm is used to solve the routing problem. The remainder of this paper is outlined as follows: in the next section, a formal definition of our version of the problem is given along with a new mathematical model. In Section 3, the adopted solution approach is provided in detail, followed by the computer results in Section 4. Some conclusions are given in the last section.

In this paper, we focus on the periodic IRP of a distribution system in which the supplier is responsible for the replenishment policy of each retailer, and the demand rate of each retailer varies each time unit. The model of the problem is formulated concisely without referring to the inventory level of retailers. The problem is decomposed to inventory problem and routing problem, firstly, the replenishment policy for each retailer is constructed, and then, the routing problem is solved based on the replenishment policy obtained in the first problem. In the inventory problem, a local search method that is realized by four operators is proposed. In order to reduce the inventory cost, the insertion operator is designed by inserting a new replenishment point; and the removal operator is proposed to lower the routing cost by removing a replenishment point; the addition operator is designed in order to increase the efficiency of the algorithm; some special cases are inapplicable for the operators above and we propose the crossover operator for them, which involved at least two retailers in the operator. In the second step, the tabu search algorithm is used to find the optimal routing. Our algorithm is tested to be efficient and stable by 10 benchmark instances and three special instances are designed to show the importance of the crossover operator. For future work, considering new factors of IRP such as multiple products, different vehicle fleet, etc., the problem can be modeled more realistic and practical. It is also very interesting to develop more effective and elegant heuristic methods to solve the problem.