Shortest paths with ordinal weights

被引：6

作者：

Schaefer, Luca E. ^{[1
]}

Dietz, Tobias ^{[1
]}

Froehlich, Nicolas ^{[1
]}

Ruzika, Stefan ^{[1
]}

Figueira, Jose R. ^{[2
]}

机构：

[1] Tech Univ Kaiserslautern, Dept Math, D-67663 Kaiserslautern, Germany

[2] Univ Lisbon, Inst Super Tecn, CEG IST, P-1049001 Lisbon, Portugal

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2020年 / 280卷 / 03期

关键词：

Networks; Ordinal scale; Ordinal shortest path problem; Preorder; Non-dominance; EFFICIENCY;

D O I：

10.1016/j.ejor.2019.08.008

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We investigate the single-source-single-destination "shortest" path problem in directed, acyclic graphs with ordinal weighted arc costs. We define the concepts of ordinal dominance and efficiency for paths and their associated ordinal levels, respectively. Further, we show that the number of ordinally non-dominated path vectors from the source node to every other node in the graph is polynomially bounded and we propose a polynomial time labeling algorithm for solving the problem of finding the set of ordinally non-dominated path vectors from source to sink. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：1160 / 1170

页数：11

共 22 条

[1] Ordinal efficiency and dominated sets of assignments [J].

Abdulkadiroglu, A ;

Sönmez, T .

JOURNAL OF ECONOMIC THEORY, 2003, 112 (01) :157-172

[2] Optimality conditions in preference-based spanning tree problems [J].

Alonso, Sergio ;

Angel Dominguez-Rios, Miguel ;

Colebrook, Marcos ;

Sedeno-Noda, Antonio .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 198 (01) :232-240

[3]

[Anonymous], 2003, Combinatorial Optimization-Polyhedra and Efficiency

[4]

Bossong U., 2006, Mathematica Slovaca, V56, P23

[5] Shortest paths algorithms: Theory and experimental evaluation [J].

Cherkassky, BV ;

Goldberg, AV ;

Radzik, T .

MATHEMATICAL PROGRAMMING, 1996, 73 (02) :129-174

[6] A minmax regret version of the time-dependent shortest path problem [J].

Conde, Eduardo ;

Leal, Marina ;

Puerto, Justo .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 270 (03) :968-981

[7] An exact method for the biobjective shortest path problem for large-scale road networks [J].

Duque, Daniel ;

Lozano, Leonardo ;

Medaglia, Andres L. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (03) :788-797

[8]

Ehrgott Matthias., 2013, Multicriteria optimization, V491

[9]

Gallo Giorgio, 1988, ANN OPER RES, V13, P1, DOI DOI 10.1007/BF02288320

[10] The k-Centrum Shortest Path Problem [J].

Garfinkel, Robert ;

Fernandez, Elena ;

Lowe, Timothy J. .

TOP, 2006, 14 (02) :279-292

← 1 2 3 →