Further study on "an extended shortest path problem A data envelopment analysis approach"

Document Type : Short notes


1 Birjand university of technology

2 Full professor in Applied Mathematics & Operations Research, Islamic Azad University of Rasht, Iran.


Amirteimoori proposed an approach based on data envelopment analysis (DEA) for  multi-objective path problems on networks whose arcs contain multiple positive and negative attributes [A. Amirteimoori, An extended shortest path problem: A data envelopment analysis approach, Applied Mathematics Letters 25 (2012) 1839-1843]. The approach is to define a relative efficiency for each arcs using DEA models, and then to solve a longest path problem for obtaining a path with maximum efficiency. In this note, we focus on two drawbacks of the approach and illustrate them using examples. Then, we propose remedies to eliminate them.


Main Subjects

[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, PHI Englewood Cliffs NJ, 1993.
[2] A. Amirteimoori, An extended shortest path problem: A data envelopment analysis approach, Applied Math. Lett. 25 (2012), no. 11, 1839–1843.
[3] F. Ghandi, Solving multi-objective shortest path problem using data envelopment analysis, Journal of Operational Research and its Applications ( Applied Mathematics ) - Lahijan Azad University 18 (2021), no. 1, 21–38.
[4] F. Keshavarz-Kohjerdi, A. Bagheri, and A. Asgharian-Sardroud, A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math. 160 (2012), no. 3, 210–217.
[5] S. Kordrostami and M.J.S. Noveiri, Solving a fuzzy shortest path problem with multiple inputs and outputs by using data envelopment analysis, 2013 13th Iranian Conference on Fuzzy Systems (IFSC), IEEE, 2013, pp. 1–4.
[6] G.H. Shirdel and S. Ramezani-Tarkhorani, A DEA-based approach for finding a favorable multi-objective shortest path, Croat. Oper. Res. Rev. 9 (2018), no. 2, 149.

[7] Y. Wang, X. Li, and R. Ruiz, A fast algorithm for finding the bi-objective shortest path in complicated networks, 2018 IEEE 22nd International Conference on Computer Supported Cooperative Work in Design ((CSCWD)), IEEE, 2018, pp. 104–