The petrol truck routing problem is an important part of the petrol supply chain. This study focuses on determining routes for distributing petrol products from a depot to petrol stations with the objective of minimizing the total travel cost and the fixed cost required to use the trucks. We propose a mathematical model that considers petrol trucks returning to a depot multiple times and develop a heuristic algorithm based on a local branch-and-bound search with a tabu list and the Metropolis acceptance criterion. In addition, an approach that accelerates the solution process by adding several valid inequalities is presented. In this study, the trucks are homogeneous and have two compartments, and each truck can execute at most three tasks daily. The sales company arranges the transfer amount and the time windows for each station. The performance of the proposed algorithm is evaluated by comparing its results with the optimal results. In addition, a real-world case of routing petrol trucks in Beijing is studied to demonstrate the effectiveness of the proposed approach.