Design and Simulation Analysis of PDER: A Multiple-Load Automated Guided Vehicle Dispatching Algorithm

by Maojia P. Li and Michael E. Kuhl (Rochester Institute of Technology)

As presented at the 2017 Winter Simulation Conference

Effective control strategies for automated guided vehicles (AGVs) are important to companies that operate flexible manufacturing systems in terms of maximizing productivity. In this paper, we design and analyze Pickup-or-Delivery-En-Route (PDER), a multiple-load AGV dispatching algorithm. PDER is a task-determination rule that enables a partially loaded vehicle traveling to a drop off destination to pickup and/or drop off loads that the vehicle would otherwise pass by en route to the original destination. We conduct a simulation-based experiment to evaluate the effectiveness of the PDER algorithm. The results indicate that PDER can produce significant positive impacts on throughput and time in system in flexible manufacturing systems utilizing multiple-load AGVs.

1 Introduction

With the constant change in the business environment, customer preferences, and technology, firms can no longer expect superior returns by producing standardized products. To address the issues such as product tailoring, expanding in the range of products offered, and diminishing order quantities, many firms try to redevelop their competitive edge by transforming from mass production to flexible manufacturing. Shivanand, Benal, and Koti (2006) define a flexible manufacturing system (FMS) as a group of workstations and storage systems interconnected by an automated material handling system and controlled by an integrated computer control system. Such a system is characterized by several complex features, such as large product variations, random patterns of material flows, and stochastic demand where traditional material handling systems such as conveyors can no longer meet the challenges moving products among workstations throughout the system.

AGVs can significantly increase the flexibility of a material handling system and take efficient paths to deliver work in progress (WIP) based on the product processing sequences. However, slow travel speed, significant loading and unloading time, and limited capacity of AGVs can limit the production capacity of manufacturing systems. Thus, an FMS with high traffic intensity may require a large number of AGVs to achieve efficient material flow and distribution. Furthermore, a large AGV fleet size involves a large capital cost for vehicles, AGV upkeep, traffic congestion issues, and space requirements.

To reduce the number of AGVs required, one alternative is to implement multiple-load AGVs. Multiple-load AGVs can usually help an FMS to achieve a high level of throughput with a smaller fleet size when compared to single-load AGVs (Ozden 1988). Some other benefits of multiple-load AGVs include better utilization of AGVs and improved machine utilizations (Bilge and Tanchoco 1997). The major challenge of managing multiple-load AGVs is that the additional load-space(s) will increase the AGV’s decision-making states. Ho and Chien (2006) observe that a single load AGV only has empty and loaded states, while a multiple-load AGV can be empty, partially loaded, and fully loaded. In addition, they define four major issues related to the management of multiple-load AGVs:

• Task-determination: Determine if the AGV’s next movement should be picking up new loads or dropping off carried loads when the vehicle is partially loaded.
• Delivery-dispatching: Determine which carried load should be dropped off first when the AGV’s next movement is dropping off.
• Pickup-dispatching: Determine which pickup point the AGV should visit next when the AGV’s next movement is picking up.
• Load-selection: Determine which load in the output buffer should be picked up when an AGV reaches a pickup point.

The objective of this research is to develop a task-determination rule that enables multiple-load AGVs to utilize the empty space(s) when it is partially loaded with the goal of maximizing the system throughput and minimize the average time in system of parts in an FMS. In particular, the proposed strategy, which we call Pickup-or-Delivery-En-Route (PDER), enables a partially loaded vehicle traveling to a drop off destination to pickup and/or drop off loads that the vehicle would otherwise pass by en route to the original destination.

The remainder of the paper is organized as follows: a summary of related work is presented in section 2; the details of the proposed PDER rule are explained in section 3; a simulation experiment to compare alternative dispatching rules under two FMS systems configurations is presented in section 4; and finally, our conclusions are discussed in section 5.

2 Summary of Related work

A relatively large body of work exists in the area of AGV dispatching algorithms. Two extensive review studies include LeAnh and Koster (2006) that presents a comprehensive study of AGV management challenges and approaches and Fazlollahtabar and SaidiMehrabad (2015) that reviews the existing strategies for AGV scheduling, dispatching, and routing problems. Many authors focus on the pickupdispatching problem for single-load AGVs. Some common pickup-dispatching rules include ShortestTravel-Distance (STD), Modified-First-Come-First-Serve (MFCFS), Maximum-Output-Queue-Size (MOQZ), Unit-Load-Shop-Arrival-Time (ULSAT) rules (Egbelu and Tanchoco, 1984). Other researchers have shown that under certain circumstances multi-attribute dispatching algorithms can outperform single-attribute rules (Jeong and Randhawa 2001; Bilge et al. 2006; Guan and Dai 2009; Caridá, Morandin, and Tuma 2015).

Azimi, Haleh, and Alidoost (2010) develop a fuzzy multi-attribute decision making (MADM) method to evaluate the control strategy for multiple-load AGVs, which takes into account ten performance criterion, such as system throughput, mean flow time of parts, average queue length in pickup and delivery points, among others. Ho and Chien (2006) compare three rules to handle the task-determination problem for multiple-load AGVs, which are Delivery-Task-First (DTF), Pickup-Task-First (PTF), and Load-Ratio (LR) rules. A DTF rule suggests that an AGV should always choose to drop off the remaining load(s) when it is partially loaded. Under a PTF rule, the AGV should always perform pickup tasks first even when delivery and pickup tasks are both available to it. Unlike the DTF or PTF rules that give delivery or pickup tasks higher priorities, the LR rule determines the AGV’s next task based on the load ratio of the vehicle. The results show that the DTF rule generally outperforms the PTF and LR rules in terms of system throughput and mean lateness of parts.

In this work, we build on the insights gained through the studies above, and design a rule (PDER) to address the pickup and drop off strategies employed when the AGV is partially loaded and en route to a destination in attempt to increase system performance.

3 Pickup-or-delivery-en-route ( PDER) rule

The essential goal of the Pickup-or-Delivery-En-Route (PDER) rule is to maximize the utilization of load spaces on multiple-load AGVs. Thus, PDER allows a partially loaded AGV to pickup additional loads on its way moving towards the next destination. After a multiple-load AGV completes all the necessary actions at a pickup or delivery point and becomes partially loaded, the AGV searches for a new assignment among the jobs whose pickup points are geographically located on the shortest path between the AGV’s current location and next destination. These jobs are labeled low-cost jobs because it is very convenient for the AGV to pick them up. If one or more low-cost jobs exist, the AGV will pickup/drop off the jobs while en route to the original destination.

The PDER algorithm works in concert with a specified pickup dispatching rule to control the actions of the multiple-load AGVs. The PDER algorithm is presented in Figure 1 in which the following notation is used:
𝑖    a transportation job (load) in the system.
𝐼    waiting list of all unassigned jobs in the system.
𝑉    an AGV in the system.
𝐷𝑉    list of destinations for AGV, 𝑉, corresponding to its assigned and carried jobs.
𝑃𝑉    list of pickup points located between the AGV’s current location and next
destination. 𝐼𝑉    set of low-cost jobs waiting at pickup points 𝑃𝑉 where 𝐼𝑉 ⊆ 𝐼. The PDER algorithm is initiated in the system upon the occurrence of either a workcenter initiated event or a vehicle initiated event.

A workcenter initiated event occurs when a load generates a new request to be transported to the next workstation based on its processing sequence. As a part is finished at a workstation, a transportation job 𝑖 is generated. If none of the AGVs is idle at the moment, the job 𝑖 will be saved to the waiting list 𝐼. If there is only one idle vehicle 𝑉, job 𝑖 will be assigned to 𝑉. If there are more than one idle AGV, the AGVs will compete for the job 𝑖 based on a workcenter-initiated rule. Some common rules include Nearest-Vehicle (NV), Longest-Idle-Vehicle (LIV), and Least-Utilized-Vehicle (LUV) (Egbelu and Tanchoco 1984).

A vehicle-initiated event occurs when an AGV reaches a pickup or drop off point. The AGV will first perform the pickup or drop off task that is pre-determined for the assigned or carried job, respectively. Once the AGV completes the pre-determined task, it will be in one of the three conditions:

• Case 1: 𝑉 is not carrying any load nor is it assigned to any job. In this case, if the waiting list I is not empty, 𝑉 will use a pickup-dispatching rule to determine the next pickup point and a loadselection rule to decide the next pickup job. Otherwise, 𝑉 will park at the nearest parking area.
• Case 2: 𝑉 is assigned to or carrying one or more loads. The AGV will first define its next destination, which is the closest pickup or drop-off point in its destination list 𝐷𝑉. If the total number of jobs assigned to and carried by 𝑉 is smaller than the vehicle capacity, 𝑉 will define its low-cost-pickup-point list 𝑃𝑉 and low-cost-job list 𝐼𝑉. If 𝐼𝑉 is not empty, 𝑉 will use a pickupdispatching rule to determine the low-cost-pickup point that has the highest priority. A low-cost job waiting at this pickup point will be selected by 𝑉 based on a load-selection rule. If 𝐼𝑉 is empty, 𝑉 will move to the next destination.
• Case 3: 𝑉 is assigned to or carrying loads equal to is capacity. The AGV will define and move to the next destination.

In Case 1 and 2, after job i is assigned to 𝑉 and removed from waiting list I, 𝑉’s subsequent states will follow either Case 2 or Case 3. In other words, 𝑉 will not leave the pickup or drop off point unless the vehicle is fully assigned ( 𝐼 in Case 1 is empty or 𝐼𝑉 in Case 2 is empty.) As the next destination is defined as the closest pickup or drop-off point in 𝑉’s destination list, the delivery-dispatching decisions always follow the STD rule.

Simulation Analysis and Experimentation

In this section, we present a simulation-based experiment to evaluate the effectiveness of the PDER taskdetermination rule together with four alternative pickup-dispatching rules. The PDER is compared against the Delivery-Task-First (DTF) task-determination rule (Ho and Chien 2006) in the context of two FMS system configurations where we vary the number of AGVs in the system as well as the capacities of the AGVs. A simulation-experiment is conducted to compare the performance of the rule combinations under the various system configurations based on performance measures including system throughput and average time in system.

FMS Configurations

We consider two Flexible Manufacturing System configurations, FMS 1 and FMS 2. Both systems operate on a pull concept, so that a new part with a random part type will enter the system when the Entry station’s queue length is smaller than its capacity. In both configurations, an AGV’s loading and unloading times are 15 seconds per part, and its travel speed is 2 miles per hour.

FMS Configuration 1 (FMS 1)

The layout of the first FMS configuration (FMS 1) is shown in Figure 2. FMS 1 has a single-loop floor layout, which consists of 8 workstations connected with unidirectional paths, and produces five part types. The output buffer capacity of the Entry station is 12. After an AGV picks up a part from the output buffer, a new part with a random part type will flow into the system based on the production volume percentages in Table 1. In addition, Table 1 lists the processing sequence for each part type as well as the average processing time. We assume that the processing time of a part at a workstation follows an exponential distribution. A completed part will leave the system from the Exit station.

4.2.1 FMS Configuration 2 (FMS 2)

The layout of the second FMS configuration (FMS 2) is shown in Figure 3 and is based on the a layout used by Ho and Chien (2006). The system consists of 10 workstations and produces six different part types. Table 2 lists the processing sequence and volume percentage (sampled randomly) for each part type. The processing time of different part types at each workstation follows the same normal distribution as shown in Table 3.

4.3 AGV Control Rules

For the experiments, we utilize several types of AGV control rules including a workcenter-initiated rule, pickup dispatching rules, a delivery dispatching rule, and a load-selection rule.

A workcenter-intitated rule is applied when a new transportation request is generated and more than one AGVs are idle. The task is to determine which idle vehicle should pickup the load. Based on the results of Egbelu and Tanchoco (1984), we apply the Nearest Vehicle (NV) rule. To select a vehicle, each AGV will find the shortest path to the pickup point of the job. The AGV that has the smallest travel distance to the pickup point will be assigned the job.

Four pickup-dispatching rules are used in conjunction with the task-determination. A pickupdispatching rule is used to determine which pickup point the AGV should visit. The four rules under consideration are Longest-Time-In-System (LTIS), Longest-Waiting-Time-at-Pickup-poinT (LWTPT), Shortest-Travel-Distance (STD), and Greatest-Queue-Length (GQL). For additional details on these rules please refer to Ho and Liu (2006).

A delivery-dispatching rule is used to determine which load should be delivered first when an AGV carries more than one load. In this study, a Shortest-Distance (SD) rule is employed for delivery dispatching – see, Ho and Chien (2006). A load-selection rule is used to determine which load should be picked up from a pickup point. In this study we utilize the First-In-Queue-First-Out (FIQFO) rule where a part with a greater waiting time in the queue will have a higher priority (Ho and Liu, 2006). With a DTF task-determination rule, the loadselection rule will be invoked when the AGV reaches the pickup point that it decided to visit. The AGV will continue to load parts based on the load-selection rule until it becomes fully loaded or the output queue becomes empty. With a PDER task-determination rule, the load-selection rule will be will be invoked during the job assigning process and determines to which low-cost-job the AGV should be assigned.

4.4 Simulation Experimental Setup

A simulation model of the two FMS systems under consideration were constructed using Simio simulation software (Simio 2017). Several relatively significant modifications/additions to the standard Simio vehicle routing logic have been made to enable the implementation and execution of the various vehicle control rules including the PDER task-determination rule -for details, see Li (2017).

The simulation-based experiments compare the performance of the PDER and DTF taskdetermination rules paired with four alternative pickup-dispatching rules in two FMS configurations. The other factors under consideration include the AGV fleet size ranging from 1 to 4 vehicles, and the vehicle types include dual- and triple-load AGVs resulting in a total of 128 test scenarios. The experimental factors and their levels are presented in Table 4. The primary performance measures considered for this experiment are average throughput and average time in system.

The simulation experiments are set up to run 20 replication of each factor combination consisting of 500 hours of continuous operations which includes a warm-up period of 6 and 12 hours for FMS 1 and FMS 2, respectively.

4.5 Analysis of Results of the Simulation Experiments

For each treatment combination of the simulation experiments, statistics on throughput and time in system are recorded. The average throughput for FMS 1 and FMS 2 are shown in Figures 4 and 5, respectively.

As a reference point, a simulation configuration that assumes instantaneous material handling has been run to establish an upper bound for throughput. The upper bound is 6,000 parts for FMS 1 and 9,800 parts for FMS 2. Given the results presented in Figures 4 and 5, we observe several cases where the system is under capacitated (FMS 1 with one AGV regardless of AGV capacity; and FMS 2 with one or two dual-load AGVs, and one triple-load AGV.) In addition, in FMS 1 when four AGVs are utilized and in FMS 2 when four dual-load or three or four triple-load AGVs are used, the system becomes over capacitated in terms of AGVs. That is, there is sufficient vehicle capacity that AGV control rules do not have a significant impact (at 𝛼 ≤ 0.05) on throughput. Therefore, we focus our analysis on the scenarios in Table 5.

Tables 6 and 7 show the throughput mean and standard deviation of the selected scenarios in FMS 1 and FMS 2, respectively. For each scenario, a Tukey multiple-means comparison test is conducted at a significance level of 0.05 to compare the mean throughput under each pair of AGV control rules. The shaded throughput values indicate that the corresponding combination of rules yields the highest throughput in the scenario. Where multiple values are shaded for a particular scenario, the means are in the highest group of mean throughput, but the means are not significantly different than one another.

In Table 6 we observe that the highest throughput is always achieved using the STD with PDER rules. When there are 3 dual-load AGVs and 2 triple-load AGVs, any pickup-dispatching rule can reach the highest throughput as long as it is coupled with a PDER task-determination rule. If using the same pickup-dispatching rule, PDER outperforms DTF in terms of throughput. Similarly, in Table 7 when using 3 dual-load or 2 triple-load AGVs, the highest throughput is always achieved with a PDER rule. When using the same pickup-dispatching rule in these two scenarios, the PDER rule yields a higher throughput.

In addition to throughput, we analyze the performance of the AGV control rules with respect to the average time parts spend in the system. Tables 8 and 9 summarize the mean and standard deviation of the average time in system for each of the selected scenario in FMS 1 and FMS 2, respectively. We conducted an analogous multiple-means comparison test on these means and shade the highest performing group for each scenario. In Table 8 we observe that the smallest average time in system is achieved with a STD with PDER rule. When using the same pickup-dispatching rule, the PDER outperforms the DTF rules in most scenarios. The only exception is when employing the LTIS with DTF rule on 2 dual-load AGVs. In Table 9 smallest average time is system is achieved with a STD with PDER rule. When using the STD, LWTPT, and GQL pickup-dispatching rules, the PDER rule outperforms the STD rule.

4.6 Discussion of Results

In general, the PDER rule outperforms the DTF rule in terms of system throughput. When using the same pickup-dispatching rule, the PDER usually yields a higher throughput. The only exception is when using 2 dual-load AGVs in the second FMS, the GQL with PDER and GQL with DTF tied for first place. It is found that the PDER rule has a smaller impact on throughput in FMS 2. As the PDER rule allows an AGV to pick up additional jobs on its way towards the next destination, the odds to have an empty AGV becomes very small. Thus, rather than being assigned for the job with the highest priority in the system, an AGV with the PDER rule usually selects a low-cost job that only has the highest priority on the AGVs current route to the next destination. In other words, instead of assigning to the job with the highest priority in the system, an AGV usually choose the job that is relatively important and more convenient to pick up. Such a problem is mitigated in FMS 1, as there is only one route connecting all workstations so that the number of time it passes each workstation is more evenly distributed.

The PDER rule also has outstanding performances in terms of the average time parts spend in the system. When using the same pickup dispatching rule, the PDER rule outperforms the DTF rule except for the LTIS case. The essential goal of the LTIS rule is to minimize the time in system of parts. A part waiting at the pickup point of the Entry station always has a smaller time in system than those parts in the output buffers of workstations. Thus, the AGVs will drive the manufacturing system to focus on completing the parts that already left the Entry station. This effect ensures the minimizing time in system but reduces the number of parts pulled into the system, thus limiting throughput.

Finally, we find that the PDER rule performs very well in both throughput and time in system when paired with the STD rule. Since STD focuses on minimizing the deadhead travel and the fact that PDER rule reduces the issue of the AGV to picking up parts from the upstream workstations while passing by downstream parts that are ready to move further downstream. As a result, the PDER rule has the potential to significantly increase the productivity of FMS systems utilizing multiple-load AGVs.

5 Conclusion

In this paper, a Pickup-or-Delivery-En-Route task-determination rule is presented for multiple-load AGVs. A simulation based experiment is conducted to compare the PDER rule and the DTF rule in two system configurations with varying fleet sizes and AGV types. Through this study, we have shown the strong potential of utilizing the PDER rule to significantly enhance the productivity that can be achieved in an FMS utilizing multiple capacity AGVs. Based on this initial work, we plan to execute a more indepth analysis to determine the characteristics of an FMS under which the use of the PDER rule will be most advantageous.