Coordination optimization of directional over current relays (DOCRs) is an important part of an efficient distribution system. This optimization problem involves obtaining the time dial setting (TDS) and pickup current (Ip) values of each DOCR. The optimal results should have the shortest primary relay operating time for all fault lines. Recently, the particle swarm optimization (PSO) algorithm has been considered an effective tool for linear/nonlinear optimization problems with application in the protection and coordination of power systems. Therefore, this study proposes a hybrid Nelder-Mead simplex search method and particle swarm optimization (NM-PSO) algorithm to solve the DOCR coordination optimization problem. PSO is the main optimizer and the Nelder-Mead simplex search method is used to improve the efficiency of PSO due to its potential for rapid convergence. To validate the proposal, this study compared the performance of the proposed algorithm with that of the original PSO. The findings demonstrate the outstanding performance of the proposed NM-PSO in terms of computation speed, rate of convergence, and feasibility.