The increasing penetration of electric vehicles brings a consequent increase in charging facilities in the low-voltage electricity network. Serving all charging requests on-demand can endanger the safety of the electrical power distribution network. This creates the issue of fairly allocating the charging energy among electric vehicles while maintaining the system within safe operational margins. However, calculating efficient charging schedules for the charging stations bears a high computational burden due to the non-convexities of charging stations’ models. In this paper, we consider a tri-level system with electric vehicles, charging stations, and a power distribution system operator. The objective of each station is formulated as a max-min fairness, mixed-integer linear optimisation problem, while the network constraints are modelled using a second-order conic formulation. In order to tackle the computational complexity of the problem, we decompose it and use a novel approximation method tailored to this problem. We compare the performance of the proposed method with that of the popular alternating direction method of multipliers. Our simulation results indicate that the proposed method achieves a near-optimal solution along with promising scalability properties.