This paper presents a stochastic optimisation model for the long-term expansion planning of the electric vehicle charging infrastructure based on the minimisation of the charging station overall costs subjected to the charging reliability and the requested Quality of Service. In fact, an earlier deterministic optimisation, model is upgraded to a stochastic model due to the stochastic nature of the mobility behaviour of electric vehicle drivers, driving range, disposable charging time and the overall costs for different charging technology types. A probabilistic approach is used to generate numerous stochastic trajectories for electric vehicles followed by the newly proposed scenario reduction procedure that employs the new Trajectory Similarity Index to obtain representative trajectories of the stochastic mobility behaviour of electric vehicle drivers. The K-MEANS reduction procedure is also used to derive stochastic scenarios of the electric vehicle driving range, Quality of Service and overall (installation, maintenance, operation) costs, which are subsequently executed by applying an optimisation algorithm together with representative trajectories. The proposed model is verified on a test road network. Results show the optimal charging locations and their placement probability, which exposes their importance to charging infrastructure planners in terms of prioritisation and robust decision-making. (C) 2017 Elsevier Ltd. All rights reserved.