Petroleum is one of the industries that has a massive impact on living conditions of the population. Petroleum distribution network plays an increasingly important function in delivering value to the end user. The objective of this research is to study the current petroleum distribution network in Sri Lanka, identify the inefficiencies and causing critical factors and propose an optimization model to overcome these inefficiencies. A conceptual framework has been developed based on the findings observed from critical review of literature and further data was collected from Sri Lankan petroleum industry domain experts using in-depth interviews. It has been identified that Sri Lankan petroleum distribution network is not taken in to account for the optimization. Hence, it is performed by developing a mathematical model in this research. The proposed model is validated with complex and real data extracted from research findings. VBA (Visual Basic Application) is used to gain exact mathematical optimization. It is concluded from the study that distribution network overall cost can be minimized when causing critical factors are optimized. Thus, this study depicts an optimization model, with the purpose of minimizing the cost, based on inefficiencies and causing critical factors which are specific for Sri Lankan petroleum industry.