Smart cities have given a significant impetus to manage traffic and use transport networks in an intelligent way. For the above reason, intelligent transportation systems (ITSs) and location-based services (LBSs) have become an interesting research area over the last years. Due to the rapid increase of data volume within the transportation domain, cloud environment is of paramount importance for storing, accessing, handling, and processing such huge amounts of data. A large part of data within the transportation domain is produced in the form of Global Positioning System (GPS) data. Such a kind of data is usually infrequent and noisy and achieving the quality of real-time transport applications based on GPS is a difficult task. The map-matching process, which is responsible for the accurate alignment of observed GPS positions onto a road network, plays a pivotal role in many ITS applications. Regarding accuracy, the performance of a map-matching strategy is based on the shortest path between two con-secutive observed GPS positions. On the other extreme, processing shortest path queries (SPQs) incurs high computational cost. Current map-matching techniques are approached with a fixed number of parameters, i.e., the number of candidate points (NCP) and error circle radius (ECR), which may lead to uncertainty when identifying road segments and either low-accurate results or a large number of SPQs. Moreover, due to the sampling error, GPS data with a high-sampling period (i.e., less than 10 s) typically contains extraneous datum, which also incurs an extra number of SPQs. Due to the high computation cost incurred by SPQs, current map-matching strategies are not suitable for real-time processing. In this paper, we propose real-time map-matching (called RT-MM), which is a fully adaptive map-matching strategy based on cloud to address the key challenge of SPQs in a map-matching process for real-time GPS trajectories. The evaluation of our approach against state-of-the-art approaches is per-formed through simulations based on both synthetic and real-world datasets.