The P-graph framework is proven to be highly effective in solving Process Network Synthesis. In the present work, the P-graph framework has been adopted for solving the routing and scheduling of evacuees, facing a life-threatening situation. First the building evacuation problem is represented by means of a P-graph model, which is then transformed into a time-expanded process network synthesis (PNST) problem that can be algorithmically handled by the P-graph framework. In the proposed method, each location in the building and their passages are given by a set of attributes to be taken in the evacuation route planning. In addition to the globally optimal solution of the building evacuation problem, the P-graph framework provides the n-best suboptimal solutions, when computational possible. The viability of the proposed model is illustrated by an example.