A global optimization method for continuous network design problems
A global optimization method for continuous network design problems
复制标题
DOI：
10.1016/j.trb.2012.05.003
复制
发表时间：
2012-11-01
影响因子：
6.8
通讯作者：
Meng, Qiang
中科院分区：
文献类型：
--
作者：
Li, Changmin;Yang, Hai;Meng, Qiang
连续网络设计问题(CNDP)一般被描述为具有平衡约束的数学规划(MPEC)。它的目标是通过扩展现有链路来优化网络性能，满足Wardrop用户均衡约束。作为交通研究领域极具挑战性的问题之一，已有多种求解方法被提出。然而，由于MPEC固有的非凸性，目前大多数算法只能找到局部最优解。本文提出了一种可行的CNDP全局优化方法。基于间隙函数和惩罚的概念，将CNDP转化为一系列易于全局求解的单层凹规划。证明了凹规划序列解的任何累加都是原CNDP的全局最优解。由于凹规划的特殊结构，所有的凹规划都可以用多割平面法求解。内部子问题每一步的惩罚项可以通过简单地执行全有或全无分配来计算。(C)2012爱思唯尔有限公司。保留所有权利。
The continuous network design problem (CNDP) is generally formulated as a mathematical program with equilibrium constraints (MPEC). It aims to optimize the network performance via expansion of existing links subject to the Wardrop user equilibrium constraint. As one of the extremely challenging problems in the transportation research field, various solution methods have been proposed for solving the CNDP. However, most of the algorithms developed up to date can only find a local optimum due to inherent nonconvexity of the MPEC. This paper proposes a viable global optimization method for the CNDP. Based on the concepts of gap function and penalty, the CNDP is transferred into a sequence of single level concave programs, which is amenable to a global solution. It is proved that any accumulation of the solutions to the sequence of concave programs is a globally optimal solution to the original CNDP. Owing to their special structure, all concave programs can be solved by a multicutting plane method. The penalty term in each step of the inner sub-problem can be calculated by simply executing an all-or-nothing assignment. (C) 2012 Elsevier Ltd. All rights reserved.