Map matching is a fundamental component for location-based services (LBSs), such as vehicle mobility analysis, navigation services, traffic scheduling, etc. In this paper, we investigate federated learning augmented map matching based on heterogeneous cellular moving trajectories from different operator systems, the goal of which is to improve matching accuracy without violating the user privacy. First, we develop a data collection platform with one Android-based application, and conduct rigorous data collection campaigns. Second, we perform systematic data analytics to reveal the data-driven technical challenges, including the impact of sampling rate, high location error of cellular moving data, and poor heterogeneous matching performance. Third, we propose an augmented map matching model, named FL-AMM, i.e., Federated Learning Augmented Map Matching, in which we i) adopt the vertical federated learning framework to achieve data collaboration and privacy protection for heterogeneous operators; ii) devise a data augmentation component to enhance the capability of representing the raw cellular data; and iii) design a map matching model to further learn the mapping function from cellular trajectory points to road segments. Finally, we conduct extensive data-driven experiments to corroborate the efficiency and robustness of the proposed FL-AMM.