Non-additive shortest paths

被引：0

作者：

Tsaggouris, G

Zaroliagis, C

机构：

[1] Comp Technol Inst, Patras 26110, Greece

[2] Univ Patras, Dept Comp Engn & Informat, Patras 26500, Greece

来源：

ALGORITHMS ESA 2004, PROCEEDINGS | 2004年 / 3221卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The non-additive shortest path (NASP) problem asks for finding an optimal path that minimizes a certain multi-attribute nonlinear cost function. In this paper, we consider the case of a non-linear convex and non-decreasing function on two attributes. We present an efficient polynomial algorithm for solving a Lagrangian relaxation of NASP. We also present an exact algorithm that is based on new heuristics we introduce here, and conduct a comparative experimental study with synthetic and real-world data that demonstrates the quality of our approach.

引用

页码：822 / 834

页数：13

共 14 条

[1]

AHUJA RK, 1993, NETWORKS FLOWS

[2]

[Anonymous], EUROPEAN J OPERATION

[3] AN ALGORITHM FOR THE RESOURCE CONSTRAINED SHORTEST-PATH PROBLEM [J].

BEASLEY, JE ;

CHRISTOFIDES, N .

NETWORKS, 1989, 19 (04) :379-394

[4]

Cheney EW., 1966, INTRO APPROXIMATION

[5]

GABRIEL S, 2000, COMP MATH ORG THEORY, V6

[6] The traffic equilibrium problem with nonadditive path costs [J].

Gabriel, SA ;

Bernstein, D .

TRANSPORTATION SCIENCE, 1997, 31 (04) :337-348

[7] A DUAL ALGORITHM FOR THE CONSTRAINED SHORTEST-PATH PROBLEM [J].

HANDLER, GY ;

ZANG, I .

NETWORKS, 1980, 10 (04) :293-310

[8]

Hensher D.A., 1985, J. Transp. Econ. Policy, V19, P237

[9]

MEHLHORN K, 2000, LNCS, V1879, P326

[10] ROUTING WITH NONLINEAR MULTIATTRIBUTE COST-FUNCTIONS [J].

MIRCHANDANI, PB ;

WIECEK, MM .

APPLIED MATHEMATICS AND COMPUTATION, 1993, 54 (2-3) :215-239

← 1 2 →