Overpopulation in animal shelters contributes to increased disease spread and higher expenses on animal healthcare, leading to fewer adoptions and more shelter deaths. Additionally, one of the greatest challenges that shelters face is the noise level in the dog kennel area, which is physically and physiologically hazardous for both animals and staff. This paper proposes a multi-criteria optimization framework to automatically design cage layouts that maximize shelter capacity, minimize tension in the dog kennel area by reducing the number of cages facing each other, and ensure accessibility for staff and visitors. The proposed framework uses a Genetic Algorithm (GA) to systematically generate and improve layouts. A novel graph theory-based algorithm is introduced to process solutions and calculate fitness values. Additionally, the Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) is used to rank and sort the layouts in each iteration. The graph-based algorithm calculates variables such as cage accessibility and shortest paths to access points. Furthermore, a heuristic algorithm is developed to calculate layout scores based on the number of cages facing each other. This framework provides animal shelter management with a flexible decision-support system that allows for different strategies by assigning various weights to the TOPSIS criteria. Results from cats' and dogs' kennel areas show that the proposed framework can suggest optimal layouts that respect different priorities within acceptable runtimes.