Keywords

1 Introduction

Over the past decades, competition among companies around the world has become increasing. To survive in this competition environment, material handling system is one of the most important issue that should be well managed for companies. Some studies have revealed that it can account for 30–75% of the total cost and a well operated material handling system can reduce plant’s operating cost by 15–30% [1]. Moreover, efficient material handling system ensures on time delivery, which is a key factor in the implementation of a lean logistics. It is a logistics application in lean manufacturing environment and provides the delivery of the products at the right time to the right place, effectively [2]. The implementation of lean logistics provides some benefits such as balancing production line, reduction of stock levels and elimination of delays in the logistics process [3].

Lean logistics activities consist of 3 parts such as in-bound, out-bound and in-plant logistics [4]. While in-plant logistics deals with logistics in the factory, in-bound and out-bound logistics deal with obtaining raw materials and delivering goods to the customer, respectively [5]. These three types of logistics affect each other implicitly and one problem in any of them signify that there will be a problem in the others. For this reason, the logistics process should be carried out in a good way at all levels, simultaneously.

There is a correlation between a just in time plan and a good logistics strategy [6]. For in-plant logistics just in time material supply is a vital issue, because early material supply causes inventory holding cost and late material supply causes stopping assembly lines due to the parts shortage [7]. Milk-Run system, cyclic goods taking, is able to reduce these kind of delays in manufacturing especially in assembly lines [8]. Indeed, milk-run system can also be considered as a special kind of Vehicle Routing Problem with Time Windows [9]. Since it is actually a lean logistics method, it is possible to be implemented for all three types of lean logistics. There are two different milk-run systems as supplier milk-run and in-plant milk-run system in the literature [4]. With the supplier milk-run system, goods are collected from external suppliers and delivered to a customer by following a predefined route [10, 11]. On the other hand, in-plant milk-run system helps to deliver materials from warehouse to assembly lines in plants in a cyclic manner. Moreover, implementation of this system to the factory, mass production is made, is appropriate because many different materials should be delivered to the assembly stations at certain periods [12]. Unlike supplier milk-run system, it is not affected by external factors such as weather conditions. Accordingly, schedules of in-plant milk-run system are more reliable and robust [4]. The objective of in-plant milk-run system can be defined as minimizing the total inventory holding and transportation cost to ensure no parts shortage will occur in assembly stations.

In plant Milk-Run systems has some certain advantages listed below [13];

  • Improved performance of the supply chain and logistics because of effective transportation,

  • Lower inventory and reduced maintenance costs,

  • More effective use of buffer stock area,

  • More appropriate and reliable delivery times,

  • Increased capital turnovers,

  • Increased flexibility in supplying the parts,

  • Smooth and well-established logistic operations.

Choosing the right material handling equipment is essential to improve facility utilization, increase efficiency of material flow, reduce waste in plant and provide effective utilization of manpower [5, 14]. There is growing interest using automated material handling vehicles especially with the Industry 4.0 concept. In this sense, in-plant milk-run system can be applied using Autonomous Vehicles (AV). Contrary to Automated Guided Vehicles (AGV), AV navigates autonomously in the environment without any limitations on the paths. Therefore, it is more convenient to use AV in flexible logistics system which should be used in just in time production.

In-plant milk-run system is applied to manage process of in-plant logistics. Operating this system effectively is important not only for minimizing material handling cost, but also for ensuring continuity of production process. Demands of the assembly stations have to be satisfied from warehouse using AV by taking into account paths and time scheduling without causing any parts shortage. Therefore, it is crucial to obtain well designed milk-run routes and periods for each AV. In the meantime, milk-run period affects delivery quantities of the assembly stations and this influences milk-run route construction process because vehicle capacity is fixed [15]. So, the problem of obtaining milk-run period and route should be handled together. In addition, milk-run routes and periods should be determined considering demands of the assembly stations, capacity of buffer stock area, the number of vehicles and their capacities.

This study is set out to explore the design of in-plant milk-run system. Milk-run routes and periods must be obtained simultaneously to operate system, effectively. Although they are common issues, the inherent difficulties make this problem tough. These are the presence of AV capacity, limited buffer stock area and assembly stations requiring multi-commodity goods. Accordingly, related problem can be explained as obtaining milk-run routes and periods for AVs with the minimum total transportation cost to satisfy the demand of assembly stations in a cyclic manner.

Our research aims at developing effective solution method for obtaining milk-run routes and periods simultaneously for AVs in-plant. With this aim in mind, a novel method which is based on Simulated Annealing algorithm has been designed to solve this challenging problem in reasonable computation times. The structure of the generic Simulated Annealing algorithm is enriched by various neighbor search procedures used in probabilistic manner. To evaluate the performance of the proposed method, we carry out experiments using generated test problems. The key contribution of this work is solution representation that provides all information about milk-run routes, periods and it enables exploring the solution space effectively. Another contribution is that proposed approach gets high quality solutions at reasonable computation times even for large-scale problems.

The rest of the papers is organized as follows. The relevant literature is reviewed in Sect. 2. Section 3 describes the related problem and gives detailed information about the proposed method. Test problems and computational results are presented in Sect. 4. Finally, Sect. 5 concludes the paper and provides future researches.

2 Literature Review

There is an increased attention to in-plant milk-run system area. So, a significant variety of designs of this system is found in the literature. Here we will discuss the literature which is relevant to our approach.

The problem that has arisen in obtaining milk-run routes and periods in-plant has been handled by researchers in different ways. Some researchers suggested exact solution methods, others developed heuristic methods. Besides, good overviews of earlier works in milk-run logistics and in-plant milk-run system is presented by [11, 12].

First of all, studies proposing the exact solution method has been examined. Akillioglu et al. [16] proposed a mixed integer mathematical model to obtain route and cycle time for in-plant milk-run system. The objectives of this model is to minimize total inventory and distribution costs. The results of the mathematical model are evaluated by using a simulation model. Kilic et al. [5] classified the milk-run distribution system and developed a mathematical model for each case. The objective function of proposed mathematical models is to minimize the number of vehicles and the total travelled distance in-plant milk-run system. The most important finding in this study is that using multiple routed milk-run trains are more advantageous than one routed milk-run trains. Similar work has also been pursued by Kilic and Durmusoglu [17] in which they focus on periodic material delivery in lean production environment. They proposed a mixed integer linear programming model to minimize transportation costs. Volling et al. [18] developed a combined inventory-transportation system with multi-product, multi-vehicle and stochastic demand. They proposed an exact decomposition approach to handle the related problem and reported that substantial gains are achieved by this approach. Emde and Gendreau [19] explored scheduling tow-train with predefined routes to feed parts to automotive assembly lines. They developed a mixed-integer mathematical model to minimize in-process inventory cost. A more efficient implementation for in-plant milk-run system has been proposed relatively recently by Satoglu and Sipahioglu [7]. Because, they proposed two different assignment based mathematical model for just in time material supply system of the assembly lines. One of the models doesn’t guarantee obtaining the global optimum solution, but this model performs better performance with regard to computation time. Mao et al. [20] introduced “Milk-run routing problem with progress lane (MRPPL)” to the literature. This problem is about to collecting automobile parts by integrating the progress-lane into the corresponding vehicle routing problem. They proposed a mixed integer linear programming model for small scale problems. Buyukozkan et al. [21] focused on in-plant milk-run system application in white goods industry. To maintain the assembly lines’ operations, they proposed a mathematical model for single-vehicle case milk-run system with predetermined periods. Buyukozkan and Satoglu [22] also proposed a mathematical model for multi-vehicle case milk-run system with predetermined cycle times. Sipahioglu and Altin [23] dealt with in-plant milk-run system with predetermined periods. They developed a new mixed integer mathematical model to obtain milk-run routes and periods for AGVs. This model allows split deliveries for stations and increase vehicle capacity by adding trailers. Besides, the proposed model has less number of constraints comparing the others and quite short computational time to obtain the optimal solution.

Studies proposing the heuristic methods has been reported as follows. Golz et al. [24] explored just in time part supply system with predefined routes to minimize the required number of shuttle drivers. They developed a heuristic solution procedure consisting of two stage. Gyulai et al. [9] proposed an initial solution generation heuristics and a local search method to solve the vehicle routing problem to obtain routes for in-plant milk-run planning problem. Kilic and Durmusoglu [17] tackled periodic material delivery in lean production environment with a predefined route in equal cycle times. They proposed a heuristic method since the optimal solution could not be obtained when scale of the problem gets bigger. Fathi et al. [25] discussed the assembly line part feeding problem with predefined tours. They suggested a modified particle swarm optimization algorithm to solve two sub-problems which are tour scheduling and tow-train loading problems. Emde and Gendreau [19] also offered a decomposition heuristic to solve instances of realistic size in acceptable computation time for scheduling tow-train with predefined routes. Mao et al. [20] also proposed genetic algorithm to obtain trip routes to collect automobile parts within a reasonable computation time for large size instances. Buyukozkan et al. [21] focused on in-plant milk-run system with predetermined period, multi product and limited buffer stock area. They proposed matheuristic algorithm that solve the proposed single vehicle milk-run model iteratively for multi vehicle case. Buyukozkan and Satoglu [22] proposed artificial bee colony algorithm to solve large scale in-plant milk-run instances with predetermined cycle time, multi product, multi vehicle and limited buffer stock area.

It is clear that, previous works are aimed at obtaining milk-run routes and periods for vehicles to minimize total cost of in-plant logistics. It is understood from these studies that the related problem can be extended in terms of the problem size and computation times. On the other hand, a solution approach that enables obtaining milk-run routes and periods simultaneously for large scale problems will contribute to the literature. In this sense, we proposed Simulated Annealing algorithm for in-plant milk-run system with multi commodity, multi vehicle and limited buffer stock area.

3 Problem Definition and Proposed Method

Companies take care not to stop assembly stations due to the parts shortage and make an effort to ensure continuity of production in plant. Therefore, it is vital to satisfy demands of the assembly stations on time. Since different operations are carried out at each assembly stations, the material types and quantities required by the stations may differ from each other. Accordingly, assembly stations must be fed periodically by AVs to minimize total transportation costs. In this feeding process, routes and periods for AVs should be obtained in accordance with the following conditions and assumptions:

  • Each route starts and ends at the depot.

  • Each AV is operated at most only one route.

  • Each station is visited only once.

  • AVs are homogenous.

  • Each assembly stations have only delivery demands.

  • Demands of each station are known but varies with regard to milk-run period.

  • Distances between assembly stations are known and used as a distance matrix.

  • Unloading time at each station is limited to 0.5 min.

  • Speed of each vehicle is 10 m per minute.

  • There are limited and known buffer stock area for each station.

  • Stations require different types of goods.

Taking into account all of these, it is necessary to determine milk-run routes and periods for each AGV in order to operate in-plant milk-run system. However, a challenging problem arises in determining milk-run routes and periods simultaneously. This problem is difficult to handle by exact solution method in reasonable computation times. Therefore, we have developed Simulated Annealing (SA) algorithm.

SA algorithm was proposed by Kirkpatrick et al. [26] and Černý [27] as a single solution based metaheuristic approach. SA is a stochastic neighborhood search method that imitates the physical annealing process where a solid is slowly cooled until the minimum energy state is achieved. Therefore, not only improving solutions are always accepted, but also non-improving (inferior) solutions can be accepted by acceptance probability of the Metropolis criterion. This acceptance probability function is the main mechanism of SA algorithm and prevents getting stuck into local optima [28]. Thus, this algorithm provides obtaining high quality solution in a reasonable computation time. Because of its simplicity and efficiency, SA algorithm has widely been applied to solve most of the combinatorial optimization problems.

In order to apply metaheuristic algorithm effectively, an appropriate solution representation structure should be used. It should be easy to generate new and feasible solutions from a current solution. Proposed solution representation is shown in Fig. 1. It consists of positive and zero numbers. Positive numbers represent delivery customers and zero numbers indicate vehicles. So, this solution representation length is related to the number of customers and vehicles.

Fig. 1.
figure 1

An example of solution representation.

Full size image

The main advantage of suggested method is the suggested solution representation. This representation provides all information about milk-run routes and periods that are vital to operate in-plant milk-run system, efficiently. Referring to Fig. 1, it is clear that there are 9 customers and 3 vehicles. Milk-run routes for each vehicle are as follows; first route is 0-8-2-5-0, second route is 0-1-9-7-0 and third route is 0-6-4-3-0. On the other hand, milk-run periods are calculated taking into account trip time of route and unloading time at each station.

SA algorithm was modified to achieve high quality solutions by using different neighbor search operators. Four different search operators have been used such as swap, insert, 3-change and reverse. These operators have been used probabilistically with regard to the scale of the problem. For small scale problems (number of customer ≤ 45), only swap, insert and 3-change operators have been used with equal probability. On the other hand, for medium (number of customer ϵ [55, 95]) and large scale problems (number of customer ≥ 150), all operators have been used with equal probability. Moreover, the number of iteration has been used as a stopping criteria and geometric cooling schedule has been used in this algorithm.

These neighbor search operators are robust and ensure obtaining milk-run routes and periods in any case. For example, route and period information is obtained from the customer numbers that are among zero values in the neighbor solution obtained by swap operator. On the other hand, if there is no customer number among the zero values, then it is understood that one of the vehicles is not used. So, the presented method is capable of generating feasible neighbor solution at each iteration when capacity of AVs and buffer stock areas is ignored.

Capacity of AVs and buffer stock areas is allowed to be exceeded in order to take advantage of the information about different solutions. A penalty function has been proposed to prevent the capacity to be exceeded in the final obtained solution and it also makes exploring the solution space, extensively. Pseudo code of the developed algorithm is given below.

figure a

The success of the algorithm is discussed in following section on generated test problems.

4 Computational Results

Here we evaluate the performance of our approach by using test instances. Firstly, environment features and parameter values of the problem are explained in detail over a small size test instance. Afterwards, this problem was solved for different scenarios and the obtained results are presented. Finally, parameter values used in generating test problems, the proposed algorithm parameters and the obtained results are mentioned.

A visual representation of generated test instance having 15 assembly stations and 1 warehouse is shown in Fig. 2. Different types of materials are available in the warehouse and homogenous Autonomous Vehicles operated to transport these materials to assembly stations are ready for use. Besides, vehicle roads in the facility are shown with dashed lines. It is important to note that material transfer is carried out without exceeding vehicle capacities and buffer stock capacities of assembly stations.

Fig. 2.
figure 2

Representation of facility layout.

Full size image

There are 10 homogenous AVs available in this instance. Capacity of AVs is expressed on volume based. Therefore, the volumes of the materials to be transported should not be larger than the volume of the vehicle capacity. In addition, there is a fixed usage cost of AVs and unit material handling cost per distance covered. Capacity, fixed usage cost and unit material handling cost of these AVs are denoted in Table 1.

Table 1. Autonomous vehicle properties.
Full size table

Assembly stations demand three different types of materials in this instance. Inventory holding cost that will occur if these materials are kept in buffer stock area and volume values of these materials are presented in Table 2. Additionally, the total inventory holding cost for each assembly station is calculated by multiplying half the amount of materials in the buffer stock area by the unit inventory holding cost.

Table 2. Material properties.
Full size table

In this system, the demands of assembly stations must be satisfied on time and these stations must continue to operate by efficient transportation method. However, each assembly stations have a certain number of material demands in different periods based on their material consumption rates. Expressing station requests in different periods with this manner will cause complication. For this reason, 10 min’ material demands of the assembly stations are calculated based on the original requests and standardization is provided in the feeding process with this way. Demands of assembly station for 10 min and capacity of buffer stock area for each station are shown in Table 3. It can be understood that the 3rd station requests 4 boxes of material-1, 7 boxes of material-2 and 3 boxes of material-3 every 10 min. These amounts are known but varies with regard to the obtained milk-run period. To illustrate, if the AV serving 3rd station has a period of 15 min, so 3rd station will demand 6 boxes of material-1, 10.5 boxes of material-2 and 4.5 boxes of material-3 every 15 min.

Table 3. Assembly station properties.
Full size table

The proposed algorithm was run for the test problem (scenario-1) whose characteristic is given above. In addition, 2 different scenarios have been created since it is worth testing how well the proposed algorithm performs in different conditions. These scenarios were generated by using different capacity values for AVs and buffer stock areas. Capacity of AV and capacity of buffer stock area were determined as 500 (\( {\text{cm}}^{3} \)), 375 (\( {\text{cm}}^{3} \)) in scenario-2 and as 250 (\( {\text{cm}}^{3} \)), 150 (\( {\text{cm}}^{3} \)) in scenario-3. So, it will be observed how the proposed algorithm will handle tight capacity constraints. The proposed SA algorithm has run 5 times for this problem and the best obtained results have denoted in Table 4. The parameters of the algorithm (initial temperature, final temperature, number of iteration at each temperature and cooling rate) were specified as \( \left( {{\text{T}}_{0} , {\text{T}}_{\text{f}} , {\text{I}}, \propto } \right) = \left( {75, 0.1, 100, 0.99} \right) \).

Table 4. Results of the test problem.
Full size table

Table 4 provides the computational results of the related test problem in terms of 3 scenarios. In order to minimize total transportation costs in each scenario, milk-run routes and periods for AVs were obtained simultaneously. Column 2 and column 3 gives information about the number of assembly stations and the number of AVs operated in each scenario. The milk-run routes obtained for AVs are demonstrated in column 4. In this column, while the warehouse is denoted by 0, the assembly stations are shown by their numbers. The 5th and 6th columns show the travel times and the total unloading times for the relevant route, respectively. In the 7th column, milk-run periods obtained for AVs are specified. Each milk-run period is achieved by summing travel time and unloading time of the relevant route. The obtained total cost values for each scenario are shown in column 8 and the last column contains computation times which are given in seconds.

From Table 4, it can be understood that there are 3 AVs to satisfy demands of 15 assembly stations in cyclic manner for scenario-1. First AV supplies material 10, 12, 3, 13, 15, 4, 9th stations every 21.4 min, second AV supplies material 2, 8, 1st stations every 16.3 min and third AV supplies material 6, 11, 7, 5, 14th stations every 21.5 min. Thus, considering all cost items, the total cost was obtained as 1940.5 for scenario-1.

There are several points to note concerning the computational results. While 3 AVs were used in scenario-1, 4 AVs in scenario-2 and 7 AVs in scenario-3 were used. Besides, when these three scenarios are compared, the minimum total cost value was obtained in scenario-1, on the other hand the maximum total cost value was obtained in scenario-3. These implications represent the impact of tight capacity constraints. That is to say, as the capacity of AVs and buffer stock areas is decreased, the number of AV needed and the total cost values increase. Moreover, it is observed that the duration of milk-run periods is shortened with tight capacity constraints. In addition, it is seen that there is no significant difference between 3 different scenarios with regard to computation times.

Different scale of test problems was generated to demonstrate the effectiveness of the developed approach. 15 different test problems were generated and classified as small, medium and large scale. All the parameter values of these test problems were expressed in Table 5. Besides, the parameter values used in the SA algorithm are shown in Table 6.

Table 5. Test problem parameter values.
Full size table
Table 6. SA parameter values.
Full size table

The proposed algorithm was coded in Python 3.7 and run on an Intel Core i5 1.8 GHz PC with 8 GB memory. This algorithm has run 5 times for each test problem and the best obtained computational results have been presented in Table 7.

Table 7. Numerical results of the proposed algorithm on the test problems.
Full size table

Numerical results of the different scale instances are summarized in Table 7 in terms of the number of assembly stations, the number of AVs operated, total cost and computation times. The first two columns of Table 7 contain information about test problems, such as instance name and the number of assembly stations. Third column shows the number of AVs used in test problems. Next column indicates the obtained total cost value and the last column includes computation times given in seconds. In these test problems, different milk-run routes and periods for AVs were obtained simultaneously in order to minimize total cost for in-plant milk-run system. So, the demands of the assembly stations have been satisfied by AVs in cyclic manner without violating capacity constraint for AVs and buffer stock areas. There is a significant positive correlation between problem size and the number of AVs and computation times needed. In other words, as the size of the problem increases, the number of AVs used and the computation times increases. However, even the L-15 problem which includes 500 assembly stations, 50 AVs and 20 different types of materials was solved in about 1 h by our proposed algorithm. Therefore, it is seen that the proposed algorithm is able to produce good solutions for even large scale problems at reasonable computation times.

5 Conclusions

This study is set out to explore in-plant milk-run system with regard to material feeding process. The main problem encountered here is obtaining milk-run routes and periods simultaneously for AVs with the minimum total cost to satisfy the demand of assembly stations in a cyclic manner. Besides, this problem is quite difficult taking into account capacity of AV, limited buffer stock area and assembly stations demanding different types of materials. Simulated Annealing algorithm has been proposed to solve this challenging problem. Different neighbor search operators and penalty function have been used the structure of the SA algorithm. In addition, a well-designed solution representation, provides all information about milk-run routes and periods as well as it enables exploring the solution space effectively, has been proposed for SA algorithm. Computational experiment has been carried out for a range of the generated test problems. Computational results show that the proposed approach gets different milk-run routes and periods for AVs simultaneously at reasonable computation times even for large-scale problems. The proposed algorithm can handle even the L-15 test problem including 500 assembly stations, 50 AVs and 20 different types of materials in about 1 h. Thus, it is seen that the proposed algorithm is a successful approach for in-plant milk-run system with multi commodity, multi vehicle and limited buffer stock area.

The key contributions of this work are the solution representation and obtaining high quality results at reasonable computation times. To the best of our knowledge, this is the first study to propose a metaheuristic algorithm for in-plant milk-run system with multi commodity, multi vehicle, limited buffer stock area and not using predetermined route and period.

In future work, it may be useful to study on a metaheuristic approach that allows split deliveries for assembly stations in-plant milk-run system and different metaheuristics can be used.