The significance of deterministic empty vehicle trips in the design of a unidirectional loop flow path

摘要

We consider the problem of designing an optimal unidirectional loop to serve manufacturing cells in an automated guided vehicle system. The layout is fixed, the edges on the boundaries of the manufacturing cells are candidates for the loop flow path. The nodes formed by the intersection of the edges on the boundaries of the cells are candidates for selection as pickup and delivery stations. The decisions to be made include which edges to select for the loop flow path, the orientation of flow on the loop, and where on the loop to locate the pickup and delivery stations for each cell. The objective of the previous models for this problem is minimization of loaded trip distances. The objective of our model is to minimize the total loaded and deterministic empty vehicle trip distances, i.e., to minimize the intensity of both loaded and empty trips on the loop times the length of the loop. This objective function is the main determinant of the fleet size of the vehicles, which in turn is the major driver of the total investment and operational costs of the system. The empty vehicle dispatching policy underlying our model is the shortest trip distance first. By creating a tight LP-relaxation, the optimal solution to the model that includes both empty and loaded trips is quickly found using general purpose optimization software. Our optimization results demonstrate that large cost savings often result from considering empty vehicle trips when designing a unidirectional loop flow path. By examining a large set of scenarios, we show that the total loaded and stochastic empty trips in a simulation environment is closely estimated by the objective function of our deterministic model. Furthermore, the stochastic trips in the simulation model for our optimal design never reaches the deterministic trips required by the loaded trip optimal design.