This paper proposes a robust protection coordination scheme of directional overcurrent relays (DOCRs) for multiple network topologies in the presence of on-load tap changers (OLTCs). The robust protection coordination scheme provides single settings of DOCRs which will be valid for all N - 1 contingencies created after outage of a line, transformer or generator. An efficient constraint reduction strategy is introduced to reduce the number of coordination constraints caused by consideration of multiple topologies. The impact of tap positions of the OLTCs has been incorporated in the required steady-state and short-circuit current calculations. The robust protection coordination scheme has been posed as an optimization problem and solved using an interior point method based algorithm. The feasibility and the effectiveness of the proposed formulation and solution algorithm has been demonstrated on the IEEE 14-bus power system network.