Smart cities can manage assets and resources efficiently by using different types of electronic data collection sensors, devices and vehicles. However, growing complexity of systems and heterogeneous networking also enlarge the destructive effect of compromised or malicious sensor nodes. In this paper, we introduce electric vehicles to conduct trust evaluation for heterogeneous vehicle network in smart cities. Compared with traditional trust evaluation mechanism, mobility-based trust evaluation owns the advantages of low energy consumption and high evaluation accuracy. Meanwhile, we investigate the problem of minimizing transmission hops of trust evaluation and refers to this as the mobile trust evaluation problem (MTEP). We first formalize the MTEP into an optimization problem and present a heuristic moving strategy of single electric vehicle. Then, we consider the MTEP with multiple electric vehicles. By scheduling the electric vehicles to access the nodes on spanning tree with maximum neighbor distance ratio, the algorithm can improve the efficiency of trust evaluation. In experiments, we compare moving strategy of single electric vehicle and multiple electric vehicles with existing methods respectively. The results demonstrate that the proposed algorithms are able to effectively reduce the entire transmission hops of trust evaluation and thus prolong the life of the network. © 2000-2011 IEEE.