Abstract
This paper proposes a new algorithm to solve the Multi-period Continuous Network Design Problem (MPCNDP) in a real options framework. The MPCNDP aims to find the long-term optimal highway expansion plan for a road network with stochastic demand. Analytical methods, finite difference methods or Least Square Monte Carlo simulation (LSMC) are not applicable for solving the MPCNDP because of the high dimension of the stochastic demand variables and the complexity of the intrinsic complexity of the network design problem. The authors propose an algorithm, which they call â??Approximate Least Square Monte Carlo simulationâ?? (ALSMC). This algorithm applies least square regression to estimate the value of the termination payoff function without knowing the optimal capacity improvement plan. During each iteration, only a multi-period CNDP with deterministic demand needs to be solved, which dramatically reduces the computing time of each termination payoff function. The authors first test the ALSMC method on a simple example for which the exact solution is known, and show that it converges quickly to the solution. They then test the ALSMC method on a small network with 6 centroids and 16 links, which has been used as a benchmark in dozens of papers. The authors find that the ALSMC method gives quick and reasonably accurate estimates of the termination payoff function.