The mobile edge computing system supported by multiple unmanned aerial vehicles (UAVs) has gained significant interest over the last few decades due to its flexibility and ability to enhance communication coverage. In this system, the UAVs function as edge servers to offer computing services to Internet of Things devices (IoTDs), and if they are located distant from those devices, a significant amount of energy is consumed while data is transmitted. Therefore, optimizing UAVs’ trajectories is an indispensable process to minimize overall energy consumption in this system. This problem is difficult to solve because it requires multiple considerations, including the number and placement of stop points (SPs), their order, and the association between SPs and UAVs. A few studies in the literature have been presented to address all of these aspects; nevertheless, the majority of them suffer from slow convergence speed, stagnation in local optima, and expensive computational costs. Therefore, this study presents a new trajectory optimization algorithm, namely ITPA-GBOKM, based on a newly proposed transfer-based encoding mechanism, gradient-based optimizer, and K-Medoids Clustering algorithm to tackle this problem more accurately. The K-medoid clustering algorithm is used to achieve better association between UAVs and SPs since it is less sensitive to outliers than the K-means clustering algorithm; the transfer function-based encoding mechanism is used to efficiently define this problem’s solutions and manage the number of SPs; and GBO is utilized to search for the best SPs that could minimize overall energy consumption, including that consumed by UAVs and IoTDs. The proposed ITPA-GBOKM is evaluated using 13 instances with several IoTDs ranging from 60 to 700 to show its effectiveness in dealing with the trajectory optimization problem at small, medium, and large scales. Furthermore, it is compared to several rival optimizers using a variety of performance metrics, including average fitness, multiple comparison test, Wilcoxon rank sum test, standard deviation, Friedman mean rank, and convergence speed, to show its superiority. The experimental results indicates that this algorithm is capable of producing significantly different and superior results compared to the rival algorithms.