A practical exact algorithm for the shortest loop design problem in a block layout

Abstract

The problem of determining a shortest loop incident to each cell of a block layout is considered. A compact formulation is developed for this problem and a relatively simple algorithm is presented. It is shown that instances containing up to 60 cells can be solved optimally by using a commercial integer linear programming solver embedded within an iterative scheme.

Keywords:

• AGV
• Block layout
• Single loop
• Integer linear programming

Acknowledgments

This work was partly supported by the Canadian Natural Sciences and Engineering Research Council under grant OGP0039682. This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.