A simulated annealing approach to the network design problem with variational inequality constraints. (English) Zbl 0764.90084

Summary: The equilibrium network design problem can be formulated as a mathematical program with variational inequality constraints. We know this problem is nonconvex; hence, it is difficult to solve for a globally optimal solution. We propose a simulated annealing algorithm for the equilibrium network design problem. We demonstrate the ability of this algorithm to determine a globally optimal solution for two different networks. One of these describes an actual city in the midwestern United States.


90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
49J40 Variational inequalities
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C26 Nonconvex programming, global optimization
Full Text: DOI