Earthwork cost is one of the major cost items (approximately 25% of the construction costs) in road construction projects. The amount of earthwork volumes therefore earthwork cost, mostly depends on the geometry of the road vertical alignment. We can conclude that an optimized vertical alignment has a profound impact on earthwork costs. In this research paper, we minimize earthwork cost by optimizing vertical alignment with the help of developed linear programming algorithm. Proposed linear programming algorithm is based on simplex method with branch and bound improvement which optimizes vertical alignment in piece-wise manner. After the optimization of vertical alignment, earthwork volumes are calculated in the road design software with average end area volume calculation method. We provide numerical results which include earthwork volumes and cost improvements over preliminary design.