This paper presents an in-depth study on a navigation application that has cloud-based and non-cloud-based versions running on the Android platform. We discovered that the cloud-based Osmand is more energy inefficient than the non-cloud-based Osmand. This is because the tail energy in 3G communications causes extra energy consumption for cloud-based Osmand. Thus, we have designed an Energy Efficient Scheduling Manager (EESManager), which benefits from its awareness of both tail energy and the complexity of the map. As the evaluation results show, cloud-based Osmand with EESManager can reduce overall energy consumption in case of a simple map between the source and destination points.