Designing an efficient method for simultaneously determining the loop and the location of the P/D stations using genetic algorithm

There are some issues which have to be addressed when designing an automated guided vehicles system (AGVS) such as flow-path layout, traffic management, the number and the location of pick-up and delivery points, vehicle routing and so on. One of the AGVS guide path configurations discussed in the previous researches includes a single-loop which is the subject of this paper. Many researchers have worked on the subject of finding the shortest single loop in a given block layout. This problem has been already proved to be NP-complete. Finding the location of pick-up/drop-off (P/D) stations on a given loop is what is typically done, but locating the loop and the P/D stations simultaneously is actually more realistic. In this paper, a genetic algorithm (GA) has been developed to determine these two simultaneously. The algorithm only reproduces the feasible solutions. The objective is to minimize the total travelled distance. A from-to chart and a block layout are the inputs and a unidirectional loop including its corresponding direction and along with the locations of the P/D stations on the loop are the outputs. To show the efficiency of the algorithm, the associated results for some sample problems have been compared with the results generated by LINGO for the equivalent mixed integer programming (MIP) problem. Computational results show the efficiency of the algorithm in solving relatively large size problem.