HEURISTIC GLOBAL OPTIMIZATION METHOD FOR CONTINUOUS NETWORK DESIGN PROBLEM

This paper proposes a heuristic global optimization algorithm for solving a continuous network design problem (CNDP). The CNDP determines the optimal additional link capacities taking account of the network user equilibrium (UE) condition. The UE condition is represented by a variational inequality (VI) to allow for the link-based formulation of the CNDP. The VI expression is then reformulated as a set of inequality constraints, which is defined against a set of extreme points of the link-flow feasible region. The paper tackles the lack of global optimality of the CNDP by applying the piecewise linear function to approximate the CNDP and transform it to a mixed-integer linear program (MILP). The paper then proposes an algorithm using the cutting-constraint approach and a standard solver for solving the MILP. The paper finally tests the proposed formulation and algorithm with a hypothetical network and compares the results with other algorithms found in the literature.