×
Schäfer, Luca E.; Dietz, Tobias; Fröhlich, Nicolas; Ruzika, Stefan; Figueira, José R.

Shortest paths with ordinal weights. (English) Zbl 1430.90171

Eur. J. Oper. Res. 280, No. 3, 1160-1170 (2020).
Summary: 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.

Cited in 3 Documents

MSC:

90B10 Deterministic network models in operations research
05C22 Signed and weighted graphs
90C35 Programming involving graphs or networks

Keywords:

networks; ordinal scale; ordinal shortest path problem; preorder; non-dominance
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Abdulkadiroglu, A.; Sönmez, T., Ordinal efficiency and dominated sets of assignments, Journal of Economic Theory, 112, 1, 157-172 (2003) · Zbl 1076.91023
[2] Alonso, S.; Domínguez-Ríos, M.Á.; Colebrook, M.; Sedeño-Noda, A., Optimality conditions in preference-based spanning tree problems, European Journal of Operational Research, 198, 1, 232-240 (2009) · Zbl 1163.90791
[3] Bossong, U.; Schweigert, D., Minimal paths on ordered graphs, Mathematica Slovaca, 56, 1, 23-31 (2006) · Zbl 1164.05388
[4] Cherkassky, B. V.; Goldberg, A. V.; Radzik, T., Shortest paths algorithms: Theory and experimental evaluation, Mathematical Programming, 73, 2, 129-174 (1996) · Zbl 0853.90111
[5] Conde, E.; Leal, M.; Puerto, J., A minmax regret version of the time-dependent shortest path problem, European Journal of Operational Research, 270, 3, 968-981 (2018) · Zbl 1403.90634
[6] Duque, D.; Lozano, L.; Medaglia, A. L., An exact method for the biobjective shortest path problem for large-scale road networks, European Journal of Operational Research, 242, 3, 788-797 (2015) · Zbl 1341.90023
[7] Ehrgott, M., Multicriteria optimization, 491 (2013), Springer Science & Business Media
[8] Gallo, G.; Pallottino, S., Shortest path algorithms, Annals of Operations Research, 13, 1, 1-79 (1988)
[9] Garfinkel, R.; Fernández, E.; Lowe, T. J., The k-centrum shortest path problem, TOP, 14, 2, 279-292 (2006) · Zbl 1278.90062
[13] Martins, E. Q.V., On a multicriteria shortest path problem, European Journal of Operational Research, 16, 2, 236-245 (1984) · Zbl 0533.90090
[14] Monnot, J.; Spanjaard, O., Bottleneck shortest paths on a partially ordered scale, Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1, 3, 225-241 (2003) · Zbl 1039.05061
[15] Nesterov, A. S., Fairness and efficiency in strategy-proof object allocation mechanisms, Journal of Economic Theory, 170, 145-168 (2017) · Zbl 1400.91261
[16] O’Mahony, C.; Wilson, N., Sorted-pareto dominance and qualitative notions of optimality, Proceedings of the European conference on symbolic and quantitative approaches to reasoning and uncertainty, 449-460 (2013), Springer · Zbl 1390.91114
[17] Perny, P.; Spanjaard, O., A preference-based approach to spanning trees and shortest paths problems, European Journal of Operational Research, 162, 3, 584-601 (2005) · Zbl 1065.90064
[18] Quercia, D.; Schifanella, R.; Aiello, L. M., The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city, Proceedings of the 25th ACM conference on hypertext and social media, 116-125 (2014), ACM
[20] Schrijver, A., Combinatorial optimization: polyhedra and efficiency, 24 (2003), Springer Science & Business Media · Zbl 1041.90001
[21] Sedeño-noda, A.; Colebrook, M., A biobjective Dijkstra algorithm, European Journal of Operational Research, 276, 1, 106-118 (2019) · Zbl 1430.90517
[22] Taccari, L., Integer programming formulations for the elementary shortest path problem, European Journal of Operational Research, 252, 1, 122-130 (2016) · Zbl 1346.90793
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.