This work presents a study on a problem faced by a Brazilian fuel distribution company, which aims to develop a decision system to minimize the operational costs of tanker trucks that refuel aircraft at airports. This is called the Aircraft Refueling Problem (ARP). ARP is related to the vehicle routing problem but focuses on the practical aspects of actual operations. The ARP variant discussed allows trucks to make multiple trips, which is called the Multiple Trip Aircraft Refueling Problem (MTARP). A Mixed-Integer Linear Programming Model (MILP) was developed to address the problem. A diverse set of instances was generated based on real-world operational constraints, simulating refueling scenarios at Brazilian airports. The model was solved using the CPLEX solver, and computational experiments were conducted to evaluate solution quality under different time limits. Two key analyzes were performed: (1) identifying instance characteristics that increase problem complexity and (2) assessing solution quality within a 30-min time limit. For smaller instances, CPLEX quickly finds optimal solutions, while for larger, constrained cases, optimality gaps remain significant. These findings offer insights into MTARP’s scalability and demonstrate that even under strict computational limits, CPLEX can provide useful solutions. However, for highly complex instances, hybrid approaches, such as heuristics or decomposition methods, may be necessary. These findings offer valuable guidance for optimizing aircraft refueling operations in real-world applications.