A small chain of gas stations in Brazil intends to expand to new retail locations. Which factors should it consider when locating new stations, in order to better leverage a combination of product prices and transportation costs? This work develops a Linear Optimization network design model in order to identify the best locations, supply origins and distribution routes that yield optimized profits. Through the Linear Optimization model and Monte-Carlo simulation, we identify that, by modeling the entire network and the route topographies, the model is expected to deliver profits 7% higher than is the case currently. These factors, however, do not seem to be as significant as station-specific factors such as operating costs, sales volume and price policy – factors beyond the scope of this work.