Abstract
This paper considers the shortest path design problem (SPDP) on bidirectional path topology as one of the best known types of network configurations for automated guided vehicles. An integer linear programming model has been developed to solve the problem. The model intends to minimize the length of the path, which needs to cover all cells at least in one edge. Due to the NP-hardness of the problem, which has been proved previously, this model is only able to solve problems with a small number of cells. So we develop an ant colony system (ACS) algorithm to solve the problem. Comparisons of the designed algorithm with a cutting-plane algorithm show the efficiency of the proposed ACS algorithm for this SPDP.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Afentakis P (1989) A loop layout design problem for flexible manufacturing systems. International Journal of Flexible Manufacturing Systems 1:175–196
Apple JM (1977) Plant layout and material handling. Wiley, New York
Asef-Vaziri A, Goetschalckx M (2008) Dual track and segmented single track bidirectional loop guide path layout for AGV systems. European Journal of Operational Research 186:972–989
Asef-Vaziri A, Laporte G (2005) Loop based facility planning and material handling. European Journal of Operational Research 164:1–11
Asef-Vaziri A, Laporte G, Sriskandarajah C (2000) The block layout shortest loop design problem. IIE Transactions 32:727–734
Asef-Vaziri A, Dessouky M, Sriskandarajah C (2001) A loop material flow system design for automated guided vehicles. International Journal of Flexible Manufacturing Systems 13:33–48
Asef-Vaziri A, Laporte G, Ortiz R (2007) Exact and heuristic procedures for the material handling circular flow path design problem. European Journal of Operational Research 176:707–726
Banerjee P, Zhou Y (1995) Facilities layout design optimization with single loop material flow path configuration. International Journal of Production Research 33:183–203
Barad M, Sinriech D (1998) A Petri net model for the operational design and analysis of segmented flow topology (SFT) AGV systems. International Journal of Production Research 36:1401–1425
Bozer YA, Srinivasan MM (1991) Tandem configurations for automated guided vehicle systems and the analysis of single vehicle loops. IIE Transactions 23:72–82
Bozer YA, Srinivasan MM (1992) Tandem AGV systems: a partitioning algorithm and performance comparison with conventional AGV systems. European Journal of Operational Research 63:173–191
Chhajed D, Montreuil B, Lowe TJ (1992) Flow network design for manufacturing systems layout. European Journal of Operational Research 57:145–161
Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1:53–66
Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge
Dorigo M, Maniezzo V, Colorni A (1991) Positive feedback as a search strategy. Technical Report, University of Milan, Italy
Egbelu PJ, Tanchoco JMA (1986) Potentials for bi-directional guide-path for automated guided vehicle based systems. International Journal of Production Research 24:1075–1097
Eshghi K, Kazemi M (2006) Ant colony algorithm for the shortest loop design problem. Computers & Industrial Engineering 50:358–366
Farahani RZ, Laporte G (2004) Two formulations for designing optimal single loop and the location of P/D stations. 3rd International Industrial Engineering Conference, Amirkabir University of Technology, Tehran, Iran, 1–14
Farahani RZ, Tari FG (2001) Optimal flow path designing of unidirectional AGV systems. International Journal of Engineering Science 12:31–44
Farahani RZ, Laporte G, Sharifyazdi M (2005) A practical exact algorithm for the shortest loop design problem in a block layout. International Journal of Production Research 43:1879–1887
Farahani RZ, Karimi B, Tamadon S (2007) Designing an efficient method for simultaneously determining the loop and the location of the P/D stations using genetic algorithm. International Journal of Production Research 45:1405–1427
Farahani RZ, Pourakbar M, Miandoabchi E (2007) Developing exact and Tabu search algorithms for simultaneously determining AGV loop and P/D stations in single loop systems. International Journal of Production Research 45:5199–5222
Farahani RZ, Laporte G, Miandoabchi E, Bina S (2008) Designing efficient methods for the tandem AGV network design problem using tabu search and genetic algorithm. Int J Adv Manuf Technol 36:996–1009
Fazlollahtabar H, Rezaie B, Kalantari H (2010) Mathematical programming approach to optimize material flow in an AGV-based flexible job shop manufacturing system with performance analysis. Int J Adv Manuf Technol 51:1149–1158
Gaskins RJ, Tanchoco JMA (1987) Flow path design for automated guided vehicle systems. International Journal of Production Research 25:667–676
Gaskins RJ, Tanchoco JMA, Taghaboni F (1989) Virtual flow paths for free-ranging automated guided vehicle systems. International Journal of Production Research 27:91–100
Guan X, Dai X (2009) Deadlock-free multi-attribute dispatching method for AGV systems. Int J Adv Manuf Technol 45:603–615
Hamzeei M, Farahani RZ (2007) Two optimal algorithms for finding bi-directional shortest path design problem in a block layout. Journal of Industrial Engineering International 3:24–34
Hsueh C (2010) A simulation study of a bi-directional load-exchangeable automated guided vehicle system. Computers & Industrial Engineering 58:594–601
Kaspi M, Tanchoco JMA (1990) Optimal flow path design of unidirectional AGV systems. International Journal of Production Research 28:1023–1030
Kaspi M, Kesselman U, Tanchoco JMA (2002) Optimal solution for the flow path design problem of a balanced unidirectional AGV system. International Journal of Production Research 40:389–401
Kim KS, Chung BD (2007) Design for a tandem AGV system with two-load AGVs. Computers & Industrial Engineering 53:247–251
Kim CW, Tanchoco JMA (1991) Conflict-free shortest-time bidirectional AGV routing. International Journal of Production Research 29:2377–2391
Kim CW, Tanchoco JMA (1993) Operational control of a bidirectional automated guided vehicle system. International Journal of Production Research 31:2123–2138
Kim K, Chung B, Jae M (2003) A design for a tandem AGVS with multi-load AGVs. Int J Adv Manuf Technol 22:744–752
Ko KC, Egbelu PJ (2003) Unidirectional AGV guide path network design: a heuristic algorithm. International Journal of Production Research 41:2325–2343
Kouvelis PW, Kim M (1992) Unidirectional loop network layout problem in automated manufacturing systems. Operation Research 40:533–550
Krishnamurthy NN, Batta R, Karwan MH (1993) Developing conflict-free routes for automated guided vehicles. Oper Res 41:1077–1090
Laporte G, Asef-Vaziri A, Sriskandarajah C (1996) Some applications of the generalized travelling salesman problem. J Oper Res Soc 47:1461–1467
Laporte G, Farahani RZ, Miandoabchi E (2006) Designing an efficient method for tandem AGV network design problem using tabu search. Applied Mathematics and Computation 183:1410–1421
Le-Anh T, De Koster MBM (2006) A review of design and control of automated guided vehicle systems. European Journal of Operational Research 171:1–23
Lin JT, Chang CCK, Liu W (1994) A load-routing problem in a tandem-configuration automated guided-vehicle system. International Journal of Production Research 32:411–427
Liu SN (2011) Modeling and optimization of integrated scheduling of automated warehouse system. Advanced Materials Research 230–232:35–39
Maxwell WL, Muckstadt JA (1982) Design of automatic guided vehicle systems. IIE Transactions 14:114–124
Maza S, Castagna P (2005) A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles. Computers in Industry 56:719–733
Mohan BC, Baskaran R (2012) A survey: ant colony optimization based recent research and implementation on several engineering domain. Expert Systems with Applications 39:4618–4627
Qiu L, Hsu W (2001) A bi-directional path layout for conflict-free routing of AGVs. International Journal of Production Research 39:2177–2195
Rajagopalan S, Heragu SS, Don Taylor G (2004) A Lagrangian relaxation approach to solving the integrated pick-up/drop-off point and AGV flow path design problem. Applied Mathematical Modeling 28:735–750
Rajotia S, Shanker K, Batra JL (1998) An heuristic for configuring a mixed uni/bidirectional flow path for an AGV system. International Journal of Production Research 36:1779–1799
Ren XL, Wen HY, Li H (2008) Routing algorithm for multiple AGVs with the undirected Petri net. Journal of Xidian University 35:517–522
Rezapour S, Zanjirani-Farahani R, Miandoabchi E (2011) A machine-to-loop assignment and layout design methodology for tandem AGV systems with single-load vehicles. International Journal of Production Research 49:3605–3633
Roe A (1997) User's guide for LINDO and LINGO, Windows version, Belmont, CA
Sarker BR, Gurav SS (2005) Route planning for automated guided vehicles in a manufacturing facility. International Journal of Production Research 43:4659–4683
Sedehi MS, Farahani RZ (2009) An integrated approach to determine the block layout, AGV flow path and the location of pick-up/delivery points in single-loop systems. International Journal of Production Research 47:3041–3061
Seo Y, Egbelu PJ (1995) Flexible guide path design for automated guided vehicle systems. International Journal of Production Research 33:1135–1156
Sinriech D, Tanchoco JMA (1992) The centroid projection method for locating pick-up and delivery stations in single-loop AGV systems. Journal of Manufacturing Systems 11:297–307
Sinriech D, Tanchoco JMA (1993) Solution methods for the mathematical models of single-loop AGV systems. International Journal of Production Research 31:705–725
Sinriech D, Tanchoco JMA (1994) SFT—segmented flow topology. In: Tanchoco JMA (ed) Material flow systems in manufacturing. Chapman & Hall, London, pp 219–238
Srivastava S, Choudhary A, Kumar S, Tiwari M (2008) Development of an intelligent agent-based AGV controller for a flexible manufacturing system. Int J Adv Manuf Technol 36:780–797
Sun XC, Tchernev N (1996) Impact of empty vehicle flow on optimal flow path design for unidirectional AGV systems. International Journal of Production Research 34:2827–2852
Tanchoco JMA, Sinriech D (1992) OSL-optimal single-loop guide paths for AGVS. International Journal of Production Research 30:665–681
Tompkins JA, White JA, Bozer YA, Tanchoco JMA (2010) Facilities planning, 4th edn. Wiley, New York
Venkataramanan MA, Wilson KA (1991) A branch-and-bound algorithm for flow-path design of automated guided vehicle systems. Naval Research Logistics 38:431–445
Ventura JA, Lee C (2003) Optimally locating multiple dwell points in a single loop guide path system. IIE Transactions 35:727–737
Wu N, Zhou M (2004) Modeling and deadlock control of automated guided vehicle systems. IEEE/ASME Transactions on Mechatronics 9:50–57
Wu N, Zhou M (2007) Shortest routing of bidirectional automated guided vehicles avoiding deadlock and blocking. IEEE/ASME Transactions on Mechatronics 12:63–72
Yahyaei M, Jam J, Hosnavi R (2010) Controlling the navigation of automatic guided vehicle (AGV) using integrated fuzzy logic controller with programmable logic controller (IFLPLC)—stage 1. Int J Adv Manuf Technol 47:795–807
Author information
Authors and Affiliations
Corresponding author
Appendix: Basic algorithm
Appendix: Basic algorithm
In our “Computational results” section, we compared the result of our ACS algorithm with that of Hamzeei and Farahani [28]. Here, we briefly outline their algorithm.
First, the sets and indices of their algorithm are shown. Afterwards, the variables and parameters are introduced. Finally, their ILP model and branch-and-cut algorithm will be described.
1.1 Sets and indices
-
\( C = \left\{ {1,2, \ldots, n} \right\} \): The set of cells in a block layout graph (p ∈ C)
-
S ⊂ C: The subset of C
-
\( \bar{S}\; \subset \;C/S \): The complement set of set S
-
\( V = \left\{ {1,2, \ldots, v} \right\} \): The set of nodes in block layout graph (i, j, k, l ∈ V)
-
\( {V_p} = \left\{ {1,2, \ldots, {v_p}} \right\} \): The set of nodes of cell p in block layout graph, \( \left( {\forall p\; \in \;C,\;\;\bigcup {_{{p \in C}}\;{V_p} = V} } \right) \)
-
\( E = \left\{ {1,2, \ldots, e} \right\} \): The set of nodes in block layout graph, which is defined as \( E = \left\{ {\left( {i,j} \right) \in \;V\left| {i,j\; \in \;V\;{\text{are}}\;{\text{adjacent}}\;{\text{nodes}}} \right.} \right\} \)
-
\( {E_p} = \left\{ {1,2, \ldots, {e_p}} \right\} \): The set of edges of cell p in block layout graph, \( \left( {\forall p\; \in \;C,\;\;\bigcup {_{{p \in C}}\;{E_p} = E} } \right) \)
-
\( E(S) = \left\{ {\left( {i,j} \right) \in \;E\left| {a\; \in \;S:\;\left( {i,j} \right) \in \;a} \right.} \right\} \): The set of all edges belonging to subset S in block layout graph
Now, we define an equation as follows:
This equation defines a set which includes the common edges between two subsets of S. According to Eq. 1, the following subsets are defined:
-
\( {S_A} = \left\{ {S \subset C\left| {\forall a\; \in \;S:\sum\nolimits_{{b \in S}} {\left| {{A_{{ab}}}\left| { \geqslant 1} \right.} \right.} } \right.} \right\} \): The set of all subsets of adjacent cells in block layout graph
-
\( {S_{{{A_m}}}} \): A member of S A
-
\( B\left( {{S_A}} \right) = \left\{ {\left( {i,j} \right) \in \;E\left( {{S_A}} \right)\left| {\exists b \in {{\bar{S}}_A}:\left( {i,j} \right) \in {E_b}} \right.} \right\} \): The set of edges on boundary of S A
1.2 Variables and parameters
-
C kl : The length of edge (k, l), \( {C_{{kl}}} = \left\{ {\left( {k,l} \right) \in E\left| {k,l \in V\;{\text{are}}\;{\text{adjacent}}\;{\text{nodes}}} \right.} \right\} \).
-
x ij : The binary variable which is equal to 1 if and only if (i, j) is adjacent to the path; otherwise, x ij = 0
-
y k : The binary variable which is equal to 1 if and only if node k is adjacent to the path; otherwise, y k = 0
-
v k : The binary variable which is equal to 1 if and only if node k is at the start or finish node of the path; otherwise, v k = 0
1.3 Mathematical model
The mathematical model supposed for solving SPDP could be found below:
subject to
Equation 10 is the objective function, which minimizes the total length of the path. Equation 11 is the degree constraint. This equation is very similar to the one used by Asef-Vaziri et al. [5] for degree constraint. This means that if a node is in the middle of the path, two adjacent edges of it must be in the path. If a node is the start or finish node of the path, then only one of its adjacent edges are in the path. If a node is not in the path, then none of its adjacent edges could be in the path.
Equation 12 is covering constraint. This relation is similar to the covering constraint in Asef-Vaziri et al. [5]. However, if SPDP assumes a path is feasible if it is adjacent in at least one node, we can use another constraint as follows:
Equation 13 is tour eliminator constraint. This equation has a similar role as connectivity constraint in Asef-Vaziri et al. [5].
Equation 14 states that the path should only have exactly two nodes as the start and finish nodes.
Equation 15 is integrality constraint.
1.4 Algorithm
The difficulty of solving this model is in Eq. 13 because its number will increase exponentially as the number of cells increases. Therefore, for solving this model, a branch-and-cut approach is used, and Eq. 13 is selected for cutting. The algorithm is as follows:
-
Step 1.
Set c = 1 as the iteration counter. Initialize a linear problem in which constraints (11), (12), (14), and (15) are introduced.
-
Step 2.
Solve the model with LINGO 10.00. If the solution is feasible, stop.
-
Step 3.
Find members of set S A for violated constraints (13). Apply constraints (13) for these members. Set c = c + 1. Go to step 2.
Rights and permissions
About this article
Cite this article
Hamzheei, M., Farahani, R.Z. & Rashidi-Bajgan, H. An ant colony-based algorithm for finding the shortest bidirectional path for automated guided vehicles in a block layout. Int J Adv Manuf Technol 64, 399–409 (2013). https://doi.org/10.1007/s00170-012-3999-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-012-3999-1