The hospital is a health service unit that is responsible for public health problems. Hospitals certainly need blood to carry out service activities to the community which include the interests of organ transplant operations, cancer treatment, and other diseases to heal patients. Because the more levels of blood needs, of course, the need for an optimal blood distribution system to maximize blood quality. One of the most recent optimization techniques is the Symbiotic Organisms Search algorithm, also known as the SOS method. but the obstacles encountered in previous research this algorithm is not optimal in solving cases on a large scale. This paper aims to modify the Symbiotic Organisms Search algorithm in order to solve combinatorial problems on a large scale. Modifications were made by replacing the parasitism phase with the mutation phase and adding a local search as a guide for the initial solution. SOS modification algorithm will be compared with the original SOS algorithm and Particle Swarm Optimization (PSO) algorithm. The results of the experiment found that the SOS Modification Algorithm was able to find the smallest distance compared to its two competing algorithms. So that it can be said that the modification of the algorithm is successful for solving large-scale combinatorial problems as for the case used is the data set of the number of blood banks in Pekanbaru City, Indonesia.