Lower Bound of AGV Scheduling Problem with Alternative Pick Up and Delivery Nodes by Benders Decomposition Approach
Article Sidebar
Main Article Content
Abstract
The original single/multi Automated Guided Vehicle (AGV) scheduling problem with a specific pick up and delivery node can be formulated and solved as single/multi traveling salesman problem(TSP/MTSP). When the original AGV problem is modified to capture the special network structure that is the network which has alternative for some node, the problem becomes the AGV scheduling problem with alternative pick up and delivery nodes. TSP/MTSP with alternative nodes will be considered for finding the solution of this kind of AGV scheduling problem with alternative pick up and delivery nodes. The purpose of this paper is to provide the mathematical model of AGV scheduling problem with alternative pick up and delivery nodes which is TSP/MTSP with alternative nodes, the lower bound model which is the assignment problem with alternative nodes, and Benders decomposition approach for solving this model. The Benders decomposition approach is verified and tested by using Excel Solver to determine the lower bound of some simulated example of AGV scheduling problem with alternative pick up and delivery nodes.
Keywords: AGV scheduling problem, Benders decomposition, Traveling salesman problem, Integer linear programming, and Alternative nodes
Corresponding author: E-mail: ocpky@yahoo.com and fengprc@ku.ac.th
Article Details
Copyright Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
Here is the link for download: Copyright transfer form.pdf
References
[2] Orman, A.J. and Williams, H.P. 2004 A Survey of Different Integer Programming Formulations of the Traveling Salesman Problem, Working paper by London school of economics and political science, 1, No. LSEOR 04.67.
[3] Blair, P., Charnsethikul, P. and Vasques, A. 1987 Special issue: Automated Guided Vehicle Systems, Material Flow, 4.
[4] Burkard, R.E. and Derigs, U. 1980 An Assignment and Matching Problem, Lecture Note in Economic and Mathematical System, 184, 56-68.
[5] Chartrand, G. and Oellermann, O.R. 1993 Applied and Algorithmic Graph Theory, McGraw Hill.
[6] Claus, A. 1984 A New Formulations for Traveling Salesman Problem, SIAM Journal of Algebraic and Discrete Methods, 5, 21-25.
[7] Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M. 1954 Solution of a Large Scale Traveling Salesman Problem, Operations Research, 2, 393-410.
[8] Ford, L.R. and Fulkerson, D.R. 1962 Flows in Networks, Princeton University Press.
[9] Bender, J.F. 1962 Partitioning Procedures for Solving Mixed Integer Variable Programming Problems, Numerische Mathematik, 4, 238-252.
[10] Tanchoco, J.M.A. and Moodie, C.L. 1987 Special issue: Automated Guided Vehicle Systems, Material Flow,4.
[11] Laporte, G. 1997 Modeling and Solving Several Classes of Arc Routing Problems As Traveling Salesman Problems, Computers and Operations Research, 24, 1057-1061.
[12] Lawler, E.L., Lenstra, J.K., Rinnooy A.H.G. and Shmoys, D.B. 1995 The Traveling Salesman Problem, Wiley, Chichester.
[13] Miller, C.E., Tucker, A.W. and Zemlin, R.A. 1960 Integer Programming Formulation of Traveling Salesman Problems, Journal of ACM, 3, 326-329.
[14] Padberg, M. and Sung, T.Y. 1991 An Analysis Comparison of Different Formulations of the Traveling Salesman Problems, Mathematical Programming, 52, 315-352.
[15] Lin, S. and Kernighan, B.W. 1973 An Effective Heuristic Algorithm for the Traveling Salesman Problems, Operation Research, 21, 498-516.