Euler is standing in line dial-a-ride problems with precedence-constraints

被引：13

作者：

Hauptmeier, D

Krumke, SO

Rambau, J

Wirth, HC

机构：

[1] Konrad Zuse Zentrum Informat Techn Berlin, Dept Optimizat, D-14195 Berlin, Germany

[2] Univ Wurzburg, Dept Comp Sci, D-97074 Wurzburg, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2001年 / 113卷 / 01期

关键词：

vehicle routing; elevator system; eulerian cycle; approximation algorithms;

D O I：

10.1016/S0166-218X(00)00390-5

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we study algorithms for "Dial-a-Ride" transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and approximation algorithms for general graphs and trees with performances of 9/4 and 5/3, respectively. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：87 / 107

页数：21

共 10 条

[1] Ascheuer N, 2000, LECT NOTES COMPUT SC, V1770, P639
[2] ASCHEUER N, 1998, P INT C OP RES OR 98, P21
[3] EFFICIENT SOLUTIONS TO SOME TRANSPORTATION PROBLEMS WITH APPLICATIONS TO MINIMIZING ROBOT ARM TRAVEL
ATALLAH, MJ
KOSARAJU, SR
[J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (05) : 849 - 869
[4] POSTMAN TOUR ON A GRAPH WITH PRECEDENCE RELATION ON ARCS
DROR, M
STERN, H
TRUDEAU, P
[J]. NETWORKS, 1987, 17 (03) : 283 - 294
[5] APPROXIMATION ALGORITHMS FOR SOME ROUTING PROBLEMS
FREDERICKSON, GN
HECHT, MS
KIM, CE
[J]. SIAM JOURNAL ON COMPUTING, 1978, 7 (02) : 178 - 193
[6] NONPREEMPTIVE ENSEMBLE MOTION PLANNING ON A TREE
FREDERICKSON, GN
GUAN, DJ
[J]. JOURNAL OF ALGORITHMS, 1993, 15 (01) : 29 - 60
[7] Routing a vehicle of capacity greater than one
Guan, DJ
[J]. DISCRETE APPLIED MATHEMATICS, 1998, 81 (1-3) : 41 - 57
[8] FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS
HAREL, D
TARJAN, RE
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (02) : 338 - 355
[9] ON FINDING LOWEST COMMON ANCESTORS - SIMPLIFICATION AND PARALLELIZATION
SCHIEBER, B
VISHKIN, U
[J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (06) : 1253 - 1262
[10] FINDING OPTIMUM BRANCHINGS
TARJAN, RE
[J]. NETWORKS, 1977, 7 (01) : 25 - 35

← 1 →