Due to the high potential of digital media to support learning processes and outcomes, educational games have gained wide acceptance over the years. The combination of mobile devices with location-based technologies offers new options and possibilities for the development of educational games in consideration of learners’ environment with the positive side effect to promote learner’s physical activities. This paper introduces a mobile educational game for promoting a better understanding of concepts related to route problems and route optimization on the basis of real world examples in a playful manner. The game combines problem-solving tasks with a quiz to teach concepts related to the Traveling Salesman Problem (TSP) by using the Global Positioning System (GPS) technology.