One of the most important factors in the design of automated guided vehicle system (AGVS) is the flow path design. The unidirectional/ conventional flow path design in automated guided vehicle (AGV) routing problem considers aisles to be undirected so that each pair of cells could be reached mutually. Regarding the flow between cells, this chapter presents a novel algorithm to minimize the total distance traveled by the loaded vehicles on the block layout graph. The algorithm is an efficient branch-and-band method with branches on the feasible solutions to solve the strongly connected graph layout. To find the feasible and efficient flow path, the authors use the Revised-DFS based on testing connectivity of the graph.
TopIntroduction
An AGV is a driverless vehicle used for transferring goods and materials on the guide-path of the floor (Hodgson et al., 1987). Since, successfully utilizing an AGVS is depended on efficient material flow, designing guide-path layout is among the most important factors in this problem. Choosing appropriate vehicle type(s) is another important factor. Muckstadt (1982) faced with the issues of vehicle routing problem with minimum number of vehicles. They considered the number of trips over each route and the vehicles routs to design the material handling system simultaneously. This work was followed by Leung, et al. (1987), who supposed dynamic mode for the capacity and speed of the vehicles. Shelton and Jones (1987) developed a model to meet the requirements of the system by providing a set of AGVs. Some other algorithms assumed the predetermined number of vehicles and the flow path. For example, in assuming a given number of vehicles and the flow path, Blair, et al. (1987) proposed a heuristic algorithm to organize material movement with selecting the minimum of maximum tour lengths. Another efficient factor to design material flow could be dispatching. Egbelu and Tanchoco (1984) presented and evaluated the effectiveness of a number of heuristic rules for dispatching AGVS in different job shop environments by using simulation. A system controller could regulate traffic when more than one vehicle is in the system.
The AGVS guide path configurations discussed in previous researches include: Conventional (Gaskin & Tanchoco, 1987; Kaspi & Tanchoco, 1990; Venkatararnanan & Wilson, 1991; Sinriech & Tanchoco, 1991; Farahani & Tari 2001), Single loop (Tanchoco & Sinriech, 1992; Sinriech & Tanchoco, 1993; Laporte, et al., 1996; Asef-Vaziri, et al., 2000; Asef-Vaziri, et al., 2001; Farahani, et al., 2003; Laporte & Farahani, 2004a; Laporte & Farahani, 2004b; Farahani, et al., 2007; Asef-Vaziri, et al., 2008; Sedehi & Farahani, 2009), Tandem (Bozer & Srinivasan 1991, Lin, et a1. 1994, Ho & Hsieh 2004, Laporte, et al. 2006, ElMekkawy & Liu 2009, Miandoabchi & Farahani 2009, Rezapour, et al. 2010), Segmented flow topology (Sinriech & Tanchoco 1994, Barad & Sinriech, 1998; Asef-Vaziri & Goetschalckx, 2008), and Bi-directional shortest path (Kim & Tanchoco, 1991; Chhajed, et al., 1992; Qui & Hsu, 2001; Maza & Castagna, 2005; Hsueh, 2010).