A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> An important factor in the design of automated guided vehicle systems (AGVS) is the flow path design. This paper presents an approach to determining the optimal flow path. The objective is to find the flow path which will minimize total travel of loaded vehicles. The problem is formulated as a zero-one integer program. Examples are presented to demonstrate the approach. <s> BIB001 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> Recent technological development in vehicle design allow vehicles to operate without physical guide paths, i.e. free-ranging automated guided vehicles. This paper addresses the problem of defining flow paths for these vehicles. A model is presented whereby the number of allowable flow paths and the flow directions between nodes (representing pickup/delivery stations and aisle intersections) of the layout network are determined. Examples are presented to demonstrate the approach. <s> BIB002 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> SUMMARY The guide path layout for an automated guided vehicle system (AGVS) is a critical component in the overall design of a flexible manufacturing system (FMS) that utilizes AGVs for materials handling. Not only does it affect the total distance travelled by the vehicles but it also affects vehicle requirements and space utilization. In this study, the problem of selecting the guide path as well as the location of pick-up and drop-off points for outward and inward bound parts to departments is addressed. The problem is modelled and solved as a linear integer program with the objective of minimizing the total distance travelled. <s> BIB003 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> SUMMARY This paper describes an alternative formulation of the AGV flow path layout (FPL) problem which was first formulated by Gaskins and Tanchoco (1987) as a zero-one integer programming problem. A computationally efficient procedure is proposed which is based on the branch-and-bound technique. An algorithm for satisfying the reachability condition for nodes in the AGV flow path network is also presented. A simple illustrative example is discussed to demonstrate the procedure, and a more complex problem is also given. <s> BIB004 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> In this paper, we introduce the Intersection Graph Method for solving the AGV Flow Path Optimization Model developed by Kaspi and Tanchoco (1990). A branch-and-bound procedure is described wherein only a reduced subset of all nodes in the flow path network is considered. Only intersection nodes are used to obtain optimal solutions. Two examples are given to illustrate the proposed method. <s> BIB005 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> We consider the problem of designing a multivehicle automated guided vehicle system AGVS to supplement an existing nonautomated material handling system. The AGVS consists of a pool of vehicles that deliver raw components from a central storage area to workcenters throughout the factor floor. The objective is to determine which workcenters warrant automated component delivery and the number of vehicles required to service those workcenters, to maximize the benefit of the AGVS, subject to a constraint that the average waiting time for material transport in the system not exceed a predefined limit. The pool of vehicles is modeled as an M/G/c queuing system and the design model is formulated as a binary integer program with nonlinear waiting time constraints, which are expressed by approximate queueing formula. We develop two different implicit enumeration algorithms to exactly solve the analytical model. We illustrate our model with an example of an actual AGVS design problem at Hewlett-Packard, and we present computational experience for other example design problems. We show how sensitivity analysis can be used to ensure that the analytical model yields an optimal solution to the design problem. <s> BIB006 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> An optimal flow path layout (FPL) design method is introduced as a handy tool for an automated guided vehicle (AGV) system planing stage. The problem is analysed and formulated by linear mixed-integer programming. A procedure based on the branch-and-bound depth-first search technique is proposed to solve the FPL problem. The procedure is implemented as an efficient computer program and yields an optimal solution in a small number of iterations. Using the transportation model for calculating the required and optimal flow of empty vehicles, system balance is achieved. Finally, two examples are given. A simple illustrative example is discussed to demonstrate the procedure, and a realistic FPL problem with 23 nodes, 66 arcs and nine pick-up/delivery stations is solved. <s> BIB007 </s> A review of design and control of automated guided vehicle systems <s> Unidirectional guide-path system <s> A construction algorithm is suggested to design guide path networks for automated guided vehicle systems (AGVSs). This study uses the total travel time, including waiting and interference time, of vehicles as the decision criteria for determining the direction of path segments on unidirectional guide path layouts. The Q-learning technique is applied to estimate the travel times of vehicles on path segments. Computational experiments were performed to evaluate the performance of the proposed algorithm. The simulation results showed that the proposed algorithm is superior to Kim & Tanchoco's (1993) algorithm in terms of the average travel time, the interference time and the number of deliveries. <s> BIB008
The unidirectional conventional guide-path system is very popular in practice, particularly in warehouses or distribution centers (Figure 1 ). Several authors BIB001 BIB002 BIB003 BIB004 BIB005 formulate the guide-path design problem as a 0-1 integer-programming (IP) model. These models decide the guide-path sections and their directions that minimize the total loaded vehicle travel distance. The size of the guide-path desogn IP model can be huge for practical problems. To speed up the solution procedure, BIB003 focus on only the major flows between departments and Sinriech and Tanchoco (1991) consider only intersection nodes in their branch-and-bound algorithm. Ignoring the empty vehicle travel time is the main drawback of above models. BIB007 propose an improved formulation of the model in BIB004 by incorporating the empty vehicle travel in the objective function and reducing the number of binary variables. Their formulation is illustrated below: 1 , , , , The objective function is to minimize both the loaded and empty vehicle travel distance. The constraint set (1-4) ensures the connectivity of the network-flow. The constraint sets (5-7) and (8-11) ensures the flow feasibility of the network-flow. This is a mixed-integer (0-1) programming model, which is difficult to solve. They solve this model using a branch-and-bound depth-first search algorithm. The empty vehicle flow (W ml ) is computed during the execution of the search algorithm by solving a transportation problem to distribute empty vehicles from the group of delivery stations to the group of pick-up stations to minimize the total distribution flow. Besides empty vehicle travel time, time lost caused by vehicle interference also impacts the quality of solutions. BIB008 consider total vehicle travel, including the empty and loaded vehicle travel time and time lost caused by congestion and vehicle interference in the design model. They estimate the total vehicle travel time using the Q-learning technique (a process of learning how to match states with actions in order to maximize a numerical reward). They show that their results are superior to those of . Obviously, the quality of their solution depends heavily on the accuracy of the travel time computed by the Q-learning process. A more complicated problem is tackled by Brandeau (1993, 1994) ;  . Their models select path configuration and the P/D stations at a same time. Al-Sultan and Bozer (1998) use a simulated annealing heuristic to solve the guide-path design problem. In their paper, they also note that the model of BIB001 may generate infeasible or non-optimal solutions. Brandeau (1993, 1994) use the benefit of AGV systems and fixed cost of setting a pick-up/delivery (P/D) station as the objective function instead of total vehicle travel distances. BIB006 's model also determines the number of vehicles required to warrant a service level (expected time until a workstation is replenished from the central depot). The pool of vehicles is approximated by an M/G/c queuing system. They formulate the problem as a 0-1 IP model and solve it using a branch-and-bound algorithm.