An Assignment Based Modelling Approach for the Inventory Routing Problem of Material Supply Systems

Abstract

Keywords: Inventory routing problem; logistics; material supply; assembly line; assignment model; mixed integer programming.

1. Introduction

Inventory Routing Problem (IRP) is comprised of the vehicle routing problem and inventory management decisions in which the supplier has to deliver the required quantities of goods to its customers. This problem aims at optimizing inventory management, vehicle routing and delivery scheduling problems, simultaneously [14]. It is associated with the Vendor-Managed Inventory (VMI) practice where the supplier, not the customer, decides when and how much to deliver at each of its customers, as long as the customers do not run out of stock [17]. Both the supplier and the customers benefit from this application, such that the customers do not spend its resources for inventory management; and the supplier can save distribution and/or production costs by planning and possibly consolidating deliveries to its several customers [14]. IRP can be solved for periodic material supply from a central warehouse to the stations of the assembly lines. In this context, the milk-run is an in-plant lean logistics application where from a *

Corresponding Author: e-mail: onbaslis@itu.edu.tr, tel: (212) 293 13 00 / 2073 161

Ş.I. Satoğlu, A. Sipahioğlu / Sigma J Eng & Nat Sci 36 (1), 161-177, 2018

central warehouse; con tainers of components are supplied to the line-side buffer stock areas of the assembly stations, on a just-in time basis, and in a cyclic manner, so that the stations do not run out of stock [10]. Just-in time material supply to the assembly lines is a vital issue, because the assembly lines must not stop due to the parts shortage. Besides, the buffer stock areas usually have a limited space, and a tight coordination of parts supply is strongly needed, in accordance with the final assembly schedule. If excess material is delivered to the buffers to decrease the material handling, inventory quantities and holding costs increase. However, if frequent deliveries in very small quantities are made, total inventory holding cost decreases but the transportation costs increase. So, an in-plant milk-run system must be designed so that the total inventory holding and transportation costs must be minimized, and no parts shortage occur. Design of this cyclic material supply system requires route construction and service period decisions that are coupled to each other. This is due to the fact that each station of the line has a constant and continuous demand rate, and longer service period results in larger delivery quantity for each of the stations in one cycle of a route. However, each vehicle’s capacity is constant and this affects the route construction [28]. Satoglu and Sahin [26] attempted to model this type of IRP where routes are constructed and service period of each route is determined, simultaneously, for the assembly line material supply systems. However, their proposed model belongs to a non-convex minimization problem and thus it could not be solved optimally. The authors proposed a heuristic where for each of the feasible period values, the routes are constructed and their costs are computed. The least cost solution is then selected, within a given number of iterations. However, the optimality is not guaranteed. In order to enhance the solution of this problem, this study aims at proposing an assignment based linear mathematical model where a certain array of service period values are considered and the stations are assigned to the routes and the service period thus the daily frequency of each route are decided simultaneously, by minimizing the total material handling, inventory holding and milk-run trailer usage costs. Although, there exists several mathematical models for the cyclic IRP where the service period (or cycle time) of the routes are real valued, the models could not be solved to optimality [32], [33]. However, by means of predetermining feasible service period values and using them in an assignment based model, the solution of the problem is enhanced. Besides, in the past IRP literature, several decomposition-based approaches exist for simplification purposes where first when to deliver the goods to the customers are decided and then the routing is performed for either the single product case [11] or the multiple product case of the IRP [16], [23]. So, in this study, single product-multiple vehicle IRP is decomposed into sub-problems to reach at a coherent approach and to solve it more effectively. A two-stage approach is developed where at the first stage an assignment-based mathematical model is solved and the stations are assigned to the routes, and each route’s service period is determined, but the sequence of stations at each route is not determined. At the second stage, a travelling salesman problem should be solved to find the right sequence of stations. On the other hand, in this study, an alternative assignment-based mathematical model of the IRP is also developed where the stations are assigned to the routes and they are sequenced, and the service period of each route is determined, simultaneously. Both the former and the latter models are assignment based linear mathematical models. To the best of the authors’ knowledge, there exists no past paper that formulated the IRP as an assignment based model that considerably reduces the computational times. This reduction in computational times is revealed based on a medium size problem. This is the novel aspect of our study. Moreover, the past IRP studies formulated the problem by using the delivery quantity and inventory variables. However, in our study, instead of defining these variables, the demand of each station in a given service period is computed by the product of demand rate and the service period that shows the exact requirement of the station in a given period. In the proposed 162

mathematical models, this requirement is multiplied by the decision variable for the assignment of the station to a route. In this manner, the delivery quantities are expressed mathematically. Thus, the delivery quantity and the inventory variables are eliminated. This kind of modelling requires less number of variables, and therefore, this mathematical formulation is a better way of formulating the IRP. This is also another significant contribution of our study to the IRP literature. Besides, the two stage approach may solve the IRP in less computational time, at the expense of the optimality. However, if the global optimum solution is desired, the proposed alternative model can be employed. By means of a medium-size data set, these two formulations were compared to each other in terms of the computational time. It was shown that by using the twostage approach, near-optimum solutions can be found, in very little time. Besides, the alternative formulation could be solved in reasonable computational times. So, both of the models are useful. Finally, in the proposed two mathematical models, the capacity of the milk-run routes can be adjusted by increasing or decreasing the number of trailers of the milk-run train that is a decision variable. This provides some flexibility to reach the full vehicle-load, while solving the problem. This is also a novel aspect of this study. The paper is organized as follows: The relevant IRP literature is reviewed in Section 2. Then, the proposed Two-Stage Approach is explained in Section 3. At the fourth section, the Alternative Mathematical Model is presented. In Section 5, both of the models are solved for a medium-size test instance. In addition, a Sensitivity analysis is performed where fourteen experiments are designed based on varying values of cost and capacity parameters. These are solved to investigate the most significant parameters, and the results are discussed. Finally, the Conclusion and future work are presented.

2. Literature Review

IRP studies dates back to thirty years ago. Although there has been a long time since the introduction of this problem, the number of studies tended to increase rapidly only after 2000’s. Coelho et. al [14] classified the types of IRP problem and reviewed the past studies within this thirty years period. According to this survey, IRP studies can be classified based on seven criteria, namely, planning horizon, structure, routing, inventory policy, inventory decisions, fleet composition and fleet size. Most of the past studies assumed that the planning period is finite. However, if a long term planning approach is followed, the problem is called the cyclic IRP. Besides, the majority of the papers examined single supplier-multiple customer case. There are also a limited number of studies that consider either single supplier-single customer or multiple supplier-multiple customer cases. In terms of routing, direct shipment to a single customer can be beneficial especially when the delivery quantity is close to the vehicle capacity [20]. Besides, several customers can be served within a single route, and in this manner multiple routes can be constructed. In today’s market conditions, the delivery quantity to each of the customer is usually much smaller than the vehicle capacity, which stipulates merger of several customers’ requirements to a single route and delivery by the same vehicle. In terms of the inventory policy, order-up-to policy or maximum level policy can be followed. In the former one, the supplier must deliver as much as needed to reach the maximum inventory level [4]. However, in the latter one, the supplier does not have to reach to the maximum level, after the delivery. Later, a hybrid heuristic was developed for the IRP with the maximum level policy, in a case of one product- one vehicle [5]. In terms of inventory decisions criterion, the problem can allow lost sales, back-order or nonnegative inventory. When the vendor-managed inventory policy is accepted, the inventory of the customers must be non-negative.

Ş.I. Satoğlu, A. Sipahioğlu / Sigma J Eng & Nat Sci 36 (1), 161-177, 2018

In terms of fleet composition, most of the papers assumed that the vehicles are homogenous in terms of capacity. However, authors believe that adjusting the capacity of the vehicles can provide some flexibility to reach the full vehicle-load, especially when the delivery quantities to the customers are very low compared to the vehicle capacity. There is some opportunity to improve the IRP solutions by adjusting the vehicle capacities [27]. In addition, most of the IRP studies assume that multiple vehicles are utilized. An extensive literature survey about the IRP was also performed with a special focus the industrial requirements and aspects [3]. It was concluded that most of the IRP papers have generic setting and assumptions, but more real world problems must be considered within the IRP studies. Moreover, the authors concluded that there was little work about the exact methods for the solution of the IRP. Besides, Archetti et. al. [4] developed a branch-and-cut algorithm for solving the vendormanaged IRP, for single product and single vehicle case. The greatest problem size that could be solved was 30 customers with a planning horizon of six time units. Later, Solyali and Sural (2011) developed a superior mathematical model and a branch-and-cut algorithm for the same problem, and they were able to solve greater problem sizes. However, the problem sizes that could be solved to optimality are still limited. Moreover, Coelho and Laporte [15] developed different mixed-integer models of single product-multi vehicle IRP assuming that vehicles have equal or different capacities. In addition, they developed branch-and-cut algorithms where LPrelaxation was solved and then the improvement algorithms were employed. Bard and Nananukul [7] developed a branch-and-price algorithm that combines exact and heuristic approaches to solve the single product-multi vehicle IRP. They were able to solve up to cases of 50 customers with an eight time units horizon within one hour computation time. Besides, Archetti et al. [6] reviewed the mathematical models and the solution techniques for single product IRP, and concluded that optimum solution of the medium and large sizes of IRP is still a challenging task. Due to the complexity of the IRP, many heuristic approaches were developed. Campbell and Savelsbergh [11] proposed a two phased approach for the single product-multiple vehicle vendormanaged IRP where at the first stage, the customers are assigned into days for delivery, and at the second stage, the routes are constructed. This kind of decomposition simplifies the solution process. However, the delivery frequency and the delivery quantity for each customer are correlated, and fixing the delivery frequency at the first stage may eliminate the better solutions. In addition, Raa and Aghezzaf [25] expressed the most economic delivery period for a certain customer and developed a column-generation based approach where insertion and savings heuristics were employed to solve single product-multiple vehicle cyclic IRP. Li et. al. [23] considered a three level supply chain comprised of a vendor, a warehouse and many retailers. In order to solve the associated IRP, the authors decomposed the problem into sub-problems. Besides, Gaur and Fisher [21] considered a time varying demand of a real supermarket chain, assigned the retailers into the clusters and for these clusters they attempted to solve this periodic IRP. Adulyasak et. al. [1] reviewed the formulations and solution approaches for the production routing problem (PRP) and suggested that lot-sizing part of the PRP should be studied more extensively. To sum up, the papers that attempted to reach the optimum solution commonly employed branch-and-cut algorithm. Besides, since the IRP is an NP-hard problem [8], it was frequently decomposed into stages, to reach at a good solution. Only a few studies intended to design a just-in time (JIT) part supply system. Ohlman et. al. [24] modeled the part distribution system from a network of suppliers to a JIT production system, through the routing and scheduling phases. Similarly, Chuah and Yingling [13] considered highfrequency and small-quantity deliveries from several suppliers to a JIT assembly plant. Besides, Yildiz, Ravi and Fairey [29] explained milk-run applications of an automotive supplier that merge customers and suppliers on the same route.

So far, the IRP studies that concentrate on distribution between supplier and customer companies were discussed. However, in the context of assembly line material supply systems, the studies are rare. Satoglu and Sahin [26] formulated a non-linear mathematical model and a heuristic are developed for these kind of material supply systems where the service period of each route is determined and the routes are constructed while minimizing the total inventory holding and material handling cost. The heuristic was exemplified by a case of a TV assembly plant. Boysen et al. [9] surveyed parts logistics decision problems within the automotive industry, and expressed that the number of vehicles, or the total line-side buffer stock or both of them can be minimized while designing the milk-run systems. Emde and Boysen [19] developed an exact solution procedure for the routing and scheduling of the milk-run tow-trains serving the assembly lines. Alnahhal and Noche [2] developed a framework including dynamic programming and mixed-integer programming to solve milk-run train routing, scheduling, and loading problems, for feeding the mixed model assembly lines. Besides, Caputo et al. [12] developed analytical models to compare different material supply models for the assembly lines. An extensive literature review was performed by Kilic and Durmusoglu [22] for assembly line feeding systems. Moreover, Zammori et. al. [31] proposed that in cases of highly-constrained facility layouts, the assembly lines must be separated into segments and each segment must be supplied by a decentralized mini depot on the basis of Kanban production control system. Besides, Alnahhal and Noche [30] designed a milk-run material supply system integrated with an electronic-kanban, and considered the machines failures, line stoppages, defective parts and re-sequencing within the mixed-model assembly lines. Hanson and Finnsgard [34] analyzed the impact of size of the unit loads (box capacity) on the performance of efficiency of in-plant materials supply. They concluded that this performance is not directly proportional to the size of the unit loads, and more frequent deliveries in smaller boxes does not always increase the man-hour requirement. Besides, Alnahhal and Noche [35] proposed an analytical methodology for usage of mini depots beside the central warehouse, and mix use of push and pull (e-Kanban) production control in order to solve train routing, scheduling, and loading problems. In addition, Klenk et al. [36] proposed practical strategies to cope with the variations in the production program while managing an in-plant milk-run systems, and applied them to two automotive factory cases. Besides, Satoglu and Ucan [37] proposed usage of Kanban and POLCA for coordinating parts supply of an automotive supplier that produces both parts with regular demand and others with changing demand pattern based on make-to order. Based on the literature review, it can be concluded that several IRP studies decomposed the problem into stages to solve it more effectively. In addition, coherent approaches that simplify the solution of the IRP are needed, since this is an NP-hard problem. Therefore, in our study, an assignment based modelling approach is followed to simplify the solution of the IRP.

System

In this two stage approach, first an assignment based mathematical model is solved, where the stations are assigned to the routes and the service period of each route are determined. However, the sequence of station in each route is not determined yet, at this stage. At the second stage, in order to find the sequence of the stations assigned to a route, a travelling salesman problem should be solved so as to minimize the total distance travelled. Before presenting the two-stage approach, the assumptions are explained below:  Each of the station has a constant demand rate for the parts/products, and it is deterministic.  The capacity of each trailer tied to the vehicle is fixed, and multiple trailers can be pulled by the vehicle. 165

Ş.I. Satoğlu, A. Sipahioğlu / Sigma J Eng & Nat Sci 36 (1), 161-177, 2018

There are a limited K-number of trailers on hand. All parts are supplied from a single central depot. The durations of the feasible service periods are predetermined. Unit inventory holding and material handling costs are pre-determined.

4. Proposed Alternative Mathematical Model

Instead of using a two-stage approach to solve the IRP as explained above, one can formulate the problem by using a single mathematical model that intends to construct the routes and determine the service period of each route, simultaneously. The same assumptions mentioned above are valid for this model, as well. This is an assignment-based model, as well. However, the solution of this model takes so much time because of the sub-tour elimination constraints. 167

Ş.I. Satoğlu, A. Sipahioğlu / Sigma J Eng & Nat Sci 36 (1), 161-177, 2018

Therefore, the decision maker should choose the former two-stage approach to obtain a good (but not optimal) solution in a reasonable time. On the other hand, if the global optimum is targeted, this proposed alternative model must be employed. The mathematical model is presented below: Sets: j={1,…,n} denotes stations k={1,…,n} denotes stations t={1,…p} denotes periods Decision Variables: 1 0 Ut: Number of milk-run trailers to be used at period-t. Parameters: Cap: Capacity of a milk-run trailer M: Maximum number of trailers that can be pulled by a vehicle of a route. UMHC: Material handling cost per time unit. UIHC: Unit inventory holding cost. Bjt: Demand of station-j at period-t djk: Distance between the stations j and k. f: Fixed cost of using one trailer. Tj: Loading-unloading time at each station-j. Periodt: Length of the period-t Mathematical Model: 2

In this model the objective function aims to minimize the total material handling, inventory holding and trailer usage costs. Minimization of the total trailers used stipulates utilization of the trailers only when needed. Therefore, the capacities of the vehicles can be adjusted. Constraints (1) and (2) respectively ensures at least one vehicle depart and enter to the warehouse for each period. Constraints (3) and (4) stipulate that one and only one vehicle must enter and depart from each station. Constraint (5) stipulates that the number of vehicles that enter and depart to a station-j at any period must be equal to each other. Constraint (6) is the capacity constraint where the total amount of components distributed in a given period is limited to the capacity of the vehicle that can be adjusted based on the required number of trailers by a vehicle, in period-t (Ut). However, the number of trailers that can be pulled by a tow-train vehicle is limited to D, and this is reflected by the Constraint (7). This is due to the fact that right, left or Uturns cannot be made, if the trains are too long. Constraint (8) stipulates that the total loadingunlading time spent at the stations that are assigned to a route is limited to the service period of that route. Constraint (9) is the sub-tour elimination constraints given by Desrochers and Laporte [18]. Finally, the sign constraints are defined in (10). By solving this model, the stations’ sequence at each route and the service period of each route are determined.

5. Computational Results For A TEST Instance

In order to test the performance of the proposed models, a randomly generated test instance comprised of 30 stations and 10 periods was used. This means n=30 and p=10. A visual presentation of the assembly system is shown in Figure 1.

Ş.I. Satoğlu, A. Sipahioğlu / Sigma J Eng & Nat Sci 36 (1), 161-177, 2018

In the test instance firstly, demand of each station at each period-t (bjt) was calculated by multiplying demand rate of each station and the predetermined period values. For simplification purposes, the demand rate of the stations between 2 & 20 and that of stations between 21 & 30 are assumed to be equal. The demand rate of the depot (node-1) is always zero. These demand values are denoted in Table 1, in terms of the number of full containers. Table 1. The Demand of Each Station at Period-t (bjt) in Terms of Number of Containers Stations 1 (Depot) 2-20 21-30

Ten period values vary between 1 and 10 hours. These service periods are presented in Table 2. Table 2. Period Values Considered in the Test Instance Periods 1 2 3 4 5 6 7 8 9 10

The travelling times among the stations, including the depot, are denoted in Table 3. Authors note that this matrix is symmetric. Loading-unloading time is assumed as 1 minute, for all stations and the depot. Besides, the material handling cost per time unit (UMHC) is 2 $/hour, and the unit inventory holding cost (UIHC) is 2$/piece/hour. Besides, fixed cost of using one trailer (f) is 1 $. The milk-run vehicle capacity is assumed as 18 containers, and at most 6 trailers can be pulled by a vehicle where each trailer can hold at most three containers. The above-mentioned parameters are common for both of the models.

Ş.I. Satoğlu, A. Sipahioğlu / Sigma J Eng & Nat Sci 36 (1), 161-177, 2018

6. Conclusion

In this study, two new assignment based models are proposed to design a JIT material supply system that serves the assembly lines. The first one is a Two-Stage Approach. At the first stage of this approach, the model determines which stations of the assembly lines must be served by which 174

route and at which period. Then, the TSP problem must be solved to find the sequence of stations within each route. However, if the stations are aligned as a straight line and the flow is unidirectional, there is no need to solve the TSP. The stations must be sequenced in parallel with the direction of material flow. When this two-stage approach is employed, the global optimum of the problem may be missed. On the other hand, the second proposed model guarantees the global optimum. However, in this model, the solution process takes longer time due to the fact that the model includes m-TSP and sub-tour elimination constraints. After all, the decision maker should choose either the first model if he/she intends to obtain a solution in a reasonable time or the second model if he/she wishes to reach the global optimum. The utility of designing the JIT material supply (milk-run) system by using either of the two mathematical models is that average inventory holding costs will be decreased, parts delivery will be more systematically coordinated and thus parts shortages will be prevented. Besides, compared to direct deliveries to the stations by forklifts etc., the milk-run material supply may reduce total material handling time, energy consumption for transportations and all associated costs. In future studies, the large test instances in the literature can be solved to compare the performance of the assignment-based models to that of the well-known IRP models. Besides, the model can be extended such that the exact number of vehicles needed is determined. Besides, using the proposed assignment based model to design a milk-run system that will serve a real automobile assembly line will reveal its utility in solving big real life problems. Finally, heuristics and meta-heuristics can be developed to solve the cyclic IRP.

Share and Cite