Lower Bound of AGV Scheduling Problem With Alternative Pick Up and Delivery Nodes by Benders Decomposition Approach

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