Nowadays, oil companies have to deal with an increasingly competitive environment. In this sense, the optimization of operational processes to enhance efficiency is crucial. This article addresses the design of a decision support tool for the inland upstream transport logistics in the oil industry based on a case of study in Argentina. This problem is traditionally difficult to solve for managers due to the large number of demand facilities scattered on a large geographic area that have to be served and the consideration of several operational requirements, such as maximum allowable travel times for vehicles, availability of a limited fleet size with a small number of drivers, plus the usual demand constraints as well as those arising from security risks derived from the incompatibility of chemical products. A novel mathematical formulation and a constructive heuristic are proposed in order to address this problem. The results allow to reduce the time that the company spends for obtaining a feasible distribution plan that minimizes the time horizon of the distribution schedule provided to the clients and enhances customer satisfaction.