Tabu search algorithm for flexible flow path design of unidirectional automated-guided vehicle systems. (English) Zbl 1144.90471
Summary: The unidirectional flow path design problem is one of the most important but difficult problems for the efficient design of automated-guided vehicle systems. As the problem was first formulated by Gaskins and Tanchoco, many researchers have studied the problem. However, the existing solution methods fail to provide an efficient solution approach. In this paper, a mathematical model for the unidirectional flow path design problem is developed. To obtain a near-to-optimal solution in reasonable computation time, a tabu search algorithm is presented. A fast construction algorithm first obtains a feasible initial solution, and a long-term memory structure and a neighbor solution generation approach are adapted to the problem characteristics and embedded in the proposed tabu search algorithm. Computational experiments show that the developed tabu search algorithm outperforms the K.-C. Ko’s and P. J. Egbelu’s algorithm [Int. J. Prod. Res. 41, No. 10, 2325–2343 (2003; Zbl 1052.90519)].
MSC:
| 90C27 | Combinatorial optimization |
| 90B06 | Transportation, logistics and supply chain management |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Citations:
Zbl 1052.90519References:
| [1] | Ahuja, RK; Magnanti, TL; Orlin, JB, Network flows: theory, algorithms and applications (1993), Englewood Cliffs, NJ: Prentice Hall, Englewood Cliffs, NJ · Zbl 1201.90001 |
| [2] | Benjaafar, S., Modeling and analysis of congestion in the design of facility layouts, Manage Sci, 48, 5, 679-704 (2002) · Zbl 1232.90138 · doi:10.1287/mnsc.48.5.679.7800 |
| [3] | Bozer, YA; Srinivasan, MM, Tandem configurations for automated guided vehicle systems and the analysis of single vehicle loop, J Manuf Syst, 15, 4, 226-236 (1991) |
| [4] | Chang, S-H; Egbelu, PJ, Dynamic relative positioning of AGVs in a loop layout to minimize mean system response time, Int J Prod Res, 34, 6, 1655-1673 (1996) · Zbl 0927.90009 |
| [5] | Chiang, W-C; Kouvelis, P., An improved tabu search heuristic for solving facility layout design problems, Int J Prod Res, 34, 9, 2565-2585 (1996) · Zbl 0929.90019 |
| [6] | De Guzman, MC; Prabhu, N.; Tanchoco, JMA, Complexity of the AGV shortest path and single-loop guide path layout problems, Int J Prod Res, 35, 8, 2083-2092 (1997) · Zbl 0945.90585 · doi:10.1080/002075497194741 |
| [7] | Dijkstra, EW, A note on two problems in connexion with graphs, Numer Math, 1, 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390 |
| [8] | Egbelu, PJ; Tanchoco, JMA, Characterization of automatic guided vehicle dispatching rules, Int J Prod Res, 22, 3, 359-374 (1984) |
| [9] | Farahani, RZ; Laporte, G.; Sharifyazdi, M., A practical exact algorithm for the shortest loop design problem in a block layout, Int J Prod Res, 43, 9, 1879-1887 (2005) · Zbl 1090.90119 |
| [10] | Floyd, RW, Algorithm 97: shortest path, Commun ACM, 5, 345 (1962) · doi:10.1145/367766.368168 |
| [11] | Ganesharajah, T.; Hall, NG; Sriskandarajah, C., Design and operational issues in AGV-served manufacturing systems, Ann Oper Res, 76, 109-154 (1998) · Zbl 0896.90083 · doi:10.1023/A:1018936219150 |
| [12] | Gaskins, RJ; Tanchoco, JMA, Flow path design for automated guided vehicle systems, Int J Prod Res, 25, 667-676 (1987) |
| [13] | Gaskins, RJ; Tanchoco, JMA; Taghaboni, F., Virtual flow paths for free-ranging automated guided vehicle systems, Int J Prod Res, 27, 1, 91-100 (1989) |
| [14] | Glover, F., Heuristics for integer programming using surrogate constraints, Decis Sci, 8, 156-166 (1977) |
| [15] | Glover, F., Tabu search—Part I, ORSA J Comput, 1, 190-206 (1989) · Zbl 0753.90054 |
| [16] | Glover, F., Tabu search—Part II, ORSA J Comput, 2, 4-32 (1990) · Zbl 0771.90084 |
| [17] | Glover, F.; Laguna, M., Tabu search (1997), Boston, MA: Kluwer, Boston, MA · Zbl 0930.90083 |
| [18] | Goetz, WG Jr; Egbelu, PJ, Guide path design and location of load pick-up/drop-off points for an automated guided vehicle system, Int J Prod Res, 28, 927-941 (1990) |
| [19] | Ho, Y-C; Hsieh, P-F, A machine-to-loop assignment and layout design methodology for tandem AGV systems with multiple-load vehicles, Int J Prod Res, 42, 4, 801-832 (2004) · Zbl 1069.90025 · doi:10.1080/00207540310001602874 |
| [20] | Hoff, EB; Sarker, BR, An overview of path design and dispatching methods for automated guided vehicles, Integr Manuf Syst, 9, 5, 296-307 (1998) · doi:10.1108/09576069810230400 |
| [21] | Kaspi, M.; Tanchoco, JMA, Optimal flow design of unidirectional AGV systems, Int J Prod Res, 28, 6, 1023-1030 (1990) |
| [22] | Kaspi, M.; Kesselman, U.; Tanchoco, JMA, Optimal solution for the flow path design problem of a balanced unidirectional AGV system, Int J Prod Res, 40, 2, 389-401 (2002) · Zbl 1060.90518 · doi:10.1080/00207540110079761 |
| [23] | Ko, KC; Egbelu, PJ, Unidirectional AGV guidepath network design: a heuristic algorithm, Int J Prod Res, 41, 2325-2343 (2003) · Zbl 1052.90519 · doi:10.1080/0020754031000087201 |
| [24] | Kouvelis, P.; Kim, MW, Unidirectional loop network layout problem in automated manufacturing systems, Oper Res, 40, 3, 533-550 (1992) · Zbl 0763.90049 |
| [25] | Moon, YM; Kota, S., Design of reconfigurable machine tools, Trans Am Soc Mech Eng, 124, 480-483 (2002) |
| [26] | Seo, Y.; Egbelu, PJ, Flexible guidepath design for automated guided vehicle systems, Int J Prod Res, 33, 1135-1156 (1995) · Zbl 0916.90138 |
| [27] | Sinreich, D.; Tanchoco, JMA, Solution methods for the mathematical models of single-loop AGV systems, Int J Prod Res, 31, 4, 705-725 (1993) |
| [28] | Sinriech, D.; Tanchoco, JMA, An introduction to the segmented flow approach for discrete material flow systems, Int J Prod Res, 33, 12, 3381-3410 (1995) · Zbl 0912.90164 |
| [29] | Skorin-Kapov, J., Tabu search applied to the quadratic assignment problem, ORSA J Comput, 2, 1, 33-45 (1990) · Zbl 0752.90054 |
| [30] | Skorin-Kapov, J., Extension of a tabu search adaptation to the quadratic assignment problem, Comput Oper Res, 21, 8, 855-865 (1994) · Zbl 0812.90098 · doi:10.1016/0305-0548(94)90015-9 |
| [31] | Sun, X-C; Tchernev, N., Impact of empty vehicle flow on optimal flow path design for unidirectional AGV systems, Int J Prod Res, 34, 10, 2827-2852 (1996) · Zbl 0929.90030 |
| [32] | Ventura, JA; Lee, C., A study of the tandem loop with multiple vehicles configuration for automated guided vehicle systems, J Manuf Syst, 20, 3, 153-165 (2001) · doi:10.1016/S0278-6125(01)80037-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
