Blockchain serves as the cornerstone of decentralized trust and distributed data management in the Web3 era. Its applications have expanded from decentralized finance (DeFi) to various industrial and societal sectors. As one of the most recognized foundations behind those blockchain systems, the proof-of-work (PoW) consensus mechanism suffers from excessive computational and energy consumption. Encountering this challenge, a number of projects such as Quilibrium, Qubic, and TIG have pioneered several initiatives, including proof-of-stake (PoS) and useful proof-of-work (UPoW), to lower blockchain’s reliance on hard and intensive hash trails. However, these initiatives still encounter challenges related to wasted computation resources, procedural complexity, incentive fairness, and centralization concerns. In this work, we propose a route-planning-based consensus mechanism that transforms the route-planning works into useful mining puzzles of the blockchain consensus procedure. We conduct a comprehensive analysis of the mining puzzle, design a problem-solving algorithm as the fair and efficient consensus mining process. We employ a series of experiments to evaluate the performance of the proposed mining puzzle and the problem-solving algorithm and demonstrate their effectiveness in converting the majority of computational effort into useful work.