A Scatter Search algorithm for solving the road network design problem

In this paper we focus on the road network design problem in regional contexts; in this case a planner may have financial resources to be invested for improving performances of an existing network. In the literature many optimisation models for solving this problem exist; we propose a model that considers also the evaluation of environmental external costs in the objective function. Then, the paper will focus on the solution algorithm: we will propose a Scatter Search algorithm that will be able to solve the problem for real-scale networks in acceptable computing times.