Optimal coordination of directional overcurrent relays (DOCRs) in interconnected power systems is a highly constrained, non-convex and non-linear optimisation problem. In this study, use of a series of linear programming (LP) problems in a variable neighbourhood search (VNS) framework is proposed, in which pickup current settings can be considered either as continuous or discrete variables. Therefore, the proposed hybrid algorithm (VNS–LP) is suitable for coordination problem-solving in a network with different types of DOCRs. Furthermore, two versions of the VNS algorithm are proposed, the first of which is very easy to implement, while, the other is somewhat more sophisticated, and at the same time much faster and possibly suitable for online coordination in smart grids applications. One advantage of the second algorithm is that it relies only on elementary arithmetic and requires low RAM, which makes it implementable in any low-level programming environment. This, in turn, can increase the interoperability, which is of crucial importance when automating tasks. The efficiency of the proposed algorithm was investigated in several test systems. Numerical results indicate that the two proposed approaches outperform the previous methods. Moreover, the coordination problem is solved in a reasonably short time using a faster approach.