期刊
NETWORKS
卷 52, 期 4, 页码 256-270出版社
WILEY
DOI: 10.1002/net.20247
关键词
constrained shortest paths; near-shortest paths; Lagrangian relaxation; path enumeration; label-setting algorithm
The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian function, identifies a feasible solution, and then closes any optimality gap by enumerating near-shortest paths, measured with respect to the Lagrangianized length. Near-shortest implies epsilon-optimal, with a varying c that equals the current optimality gap. The algorithm exploits a variety of techniques: a new path-enumeration method; aggregated constraints; preprocessing to eliminate edges that cannot form part of an optimal solution; reprocessing that reapplies preprocessing steps as improved solutions are found; and, when needed, a phase-I procedure to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state-of-the-art label-setting algorithm on singly constrained randomly generated grid networks. On multiconstrained grid networks, road networks, and networks for aircraft routing the advantage varies but, overall, the new algorithm is competitive with the label-setting algorithm. 0 2008 Wiley Periodicals, Inc.* NETWORKS, Vol. 52(4), 256-270 2008
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据