Complexity analysis and optimization of the shortest path tour problem

被引：16

作者：

Festa, Paola ^{[1
]}

机构：

[1] Univ Napoli FEDERICO II Compl MSA, Dept Math & Applicat, I-80126 Naples, Italy

来源：

OPTIMIZATION LETTERS | 2012年 / 6卷 / 01期

关键词：

Shortest path problems; Network flowproblems; Network optimization; Combinatorial optimization; ROUTE METHODS; ALGORITHMS; BUCKETS;

D O I：

10.1007/s11590-010-0258-y

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The shortest path tour problem (SPTP) consists in finding a shortest path from a given origination node s to a given destination node d in a directed graph with nonnegative arc lengths with the constraint that the optimal path P should successively and sequentially pass through at least one node from given node subsets T (1), T (2), . . . , T (N) , where T(i)boolean AND T(j)=empty set, (sic) i, j = 1, ..., N, i not equal j. In this paper, it will proved that the SPTP belongs to the complexity class P and several alternative techniques will be presented to solve it.

引用

页码：163 / 175

页数：13

共 20 条

[1] Ahuja R., 1993, NETWORK FLOWS THEORY
[2] CONSTRAINED SHORTEST PATH PROBLEM
ANEJA, YP
NAIR, KPK
[J]. NAVAL RESEARCH LOGISTICS, 1978, 25 (03) : 549 - 555
[3] [Anonymous], 2002, Handbook of Applied Optimization
[4] Bertsekas D. P., 1995, Computational Optimization and Applications, V4, P99, DOI 10.1007/BF01302891
[5] Bertsekas D. P., 2005, DYNAMIC PROGRAMMING, V1
[6] AN AUCTION ALGORITHM FOR SHORTEST PATHS
Bertsekas, Dimitri P.
[J]. SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (04) : 425 - 447
[7] Shortest paths algorithms: Theory and experimental evaluation
Cherkassky, BV
Goldberg, AV
Radzik, T
[J]. MATHEMATICAL PROGRAMMING, 1996, 73 (02) : 129 - 174
[8] Negative-cycle detection algorithms
Cherkassky, BV
Goldberg, AV
[J]. MATHEMATICAL PROGRAMMING, 1999, 85 (02) : 277 - 311
[9] Buckets, heaps, lists, and monotone priority queues
Cherkassky, BV
Goldberg, AV
Silverstein, C
[J]. SIAM JOURNAL ON COMPUTING, 1999, 28 (04) : 1326 - 1346
[10] SHORTEST-ROUTE METHODS .1. REACHING, PRUNING, AND BUCKETS
DENARDO, EV
FOX, BL
[J]. OPERATIONS RESEARCH, 1979, 27 (01) : 161 - 186

← 1 2 →