Making decisions in a complex system such as the construction of a highway is a hard task that involves a combinatorial set of possibilities, concerning thousands of interrelated activities and resources over several years. In this paper we describe a decision support system (DSS) developed to assist project managers in decision making for the construction of the Autostrada Pedemontana Lombarda highway, in Italy. The considered problem evaluates the earthwork activities in detail and defines the minimum cost earthwork plan satisfying all constraints. The proposed DSS involves the use of linear programming to solve the earthwork problem in a two-phase approach: in the first phase, an aggregate model determines the feasibility of the overall project, whereas in the second phase, disaggregate models determine the actual flows of each material. The DSS gathers the needed information directly from the master plan commonly used by the company and provides as output a set of visual solutions. The solution are yielded in short times and can be run many times with different data sets supporting a fast evaluation of different decisions. The provided solutions are also optimized and could substitute the previous manual results. The DSS has been proved to be very effective for assisting the project managers of the above highway construction and is currently in use in other projects.