The vehicle routing problem is one of the vibrant research problems for half a century. Many studies have extensively studied the vehicle routing problem in order to deal with practical decision-making issues in logistics. However, developments of new logistics strategies have inevitably required investigations on solution methods for solving the problem because of computational complexity and inherent constraints in the problem. For this reason, this paper suggests a simulated annealing (SA) algorithm for a variant of vehicle routing problem introduced by a previous study. The vehicle routing problem is a multi-depot and multi-trip vehicle routing problem with multiple heterogeneous vehicles restricted by the maximum permitted weight and the number of compartments. The SA algorithm generates an initial solution through a greedy-type algorithm and improves it using an enhanced SA procedure with three local search methods. A series of computational experiments are performed to evaluate the performance of the heuristic and several managerial findings are further discussed through scenario analyses. Experiment results show that the proposed SA algorithm can obtain good solutions within a reasonable computation time and scenario analyses show that a transportation system visiting non-dedicated factories shows better performance in truck management in terms of the numbers of vehicles used and trips for serving customer orders than another system visiting only dedicated factories.