A connectivity graph generation approach for Manhattan path calculation in detailed facility layout

摘要

The main aim of the detailed facility layout is to calculate the obstacle-avoiding Manhattan shortest path (OAMSP) between facilities. We propose a connectivity graph generation approach for OAMSP calculation. The proposed approach makes full use of the characteristics of Manhattan distance, which are different from Euclidean distance. The proposed connectivity graph contains O(N log N) vertices and edges, where N is the total number of all facilities vertices. We give two examples to compare the proposed approach and two classical graph theoretic approaches. The results showed that the proposed connectivity graph possessed less vertices and edges, and the generation time of the proposed approach is also shorter than other two methods. Thus, the proposed approach can shorten the time of shortest distance calculation in detailed layout. Furthermore, the proposed graph can be valuable reference to the transport routing planning.