This paper presents a fuzzy maximal covering location problem (FMCLP) in which travel time between any pair of nodes is considered to be a fuzzy variable. A fuzzy expected value maximization model is designed for such a problem. Moreover, a hybrid algorithm of fuzzy simulation and simulated annealing (SA) is used to solve FMCLP. Some numerical examples are presented, solved and analyzed to show the performance of the proposed algorithm. The results show that the proposed SA finds solutions with objective values no worse than 1.35% below the optimal solution. Furthermore, the simulation-embedded simulated annealing is robust in finding solutions.