An acceptability index based approach for solving shortest path problem on a network with interval weights
RAIRO. Operations Research, Tome 55 (2021), pp. S1767-S1787

Based on the acceptability index for comparison of any two imprecise values, efficient algorithms have been proposed in the literature for solving shortest path (SP) problem when the weights of connected arcs in a transportation network are represented as interval numbers. In this study, a generalized Dijkstra algorithm is proposed to handle the SP problem with interval weights. Here it is shown that once the acceptability index is chosen, the interval SP problem is converted into crisp one, which is easily solved by the standard SP algorithms. The main contribution here is the reduction of the computational complexity of the existing algorithm for solving interval SP problem. To show the advantages of the proposed algorithm over existing algorithm the numerical example presented in literature is solved using the proposed algorithm and the obtained results are discussed. Moreover, an small sized telecommunication network is provided to illustrate the potential application of the proposed method. Finally, the practical relevance of the proposed algorithm is evaluated by means of a large scale pilot case where a pharmaceutical shipment between the cities in Iran should be transported.

DOI : 10.1051/ro/2020033
Classification : 90Bxx, 90B18, 90C70
Keywords: Shortest path problem, interval numbers, acceptability index 
@article{RO_2021__55_S1_S1767_0,
     author = {Ebrahimnejad, Ali},
     title = {An acceptability index based approach for solving shortest path problem on a network with interval weights},
     journal = {RAIRO. Operations Research},
     pages = {S1767--S1787},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020033},
     mrnumber = {4223109},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020033/}
}
TY  - JOUR
AU  - Ebrahimnejad, Ali
TI  - An acceptability index based approach for solving shortest path problem on a network with interval weights
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S1767
EP  - S1787
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020033/
DO  - 10.1051/ro/2020033
LA  - en
ID  - RO_2021__55_S1_S1767_0
ER  - 
%0 Journal Article
%A Ebrahimnejad, Ali
%T An acceptability index based approach for solving shortest path problem on a network with interval weights
%J RAIRO. Operations Research
%D 2021
%P S1767-S1787
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020033/
%R 10.1051/ro/2020033
%G en
%F RO_2021__55_S1_S1767_0
Ebrahimnejad, Ali. An acceptability index based approach for solving shortest path problem on a network with interval weights. RAIRO. Operations Research, Tome 55 (2021), pp. S1767-S1787. doi: 10.1051/ro/2020033

A. Abbaszadeh Sori, A. Ebrahimnejad and H. Motameni, Elite artificial bees’ colony algorithm to solve robot’s fuzzy constrained routing problem. Comput. Intell. 36 (2019) 659–681. | MR | DOI

A. Abbaszadeh Sori, A. Ebrahimnejad and H. Motameni, The fuzzy inference approach to solve multi-objective constrained shortest path problem. J. Intell. Fuzzy Syst. 38 (4) (2019) 1–10.

E. Ahmadi, G. A. Süer and F. Al-Ogaili, Solving stochastic shortest distance path problem by using genetic algorithms. Proc. Comput. Sci. 140 (2018) 79–86. | DOI

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Englewood Cliffs, NJ (1993). | MR | Zbl

C. Alexopoulos, State space partitioning methods for stochastic shortest path problems. Networks 30 (1997) 9–21. | MR | Zbl | DOI

J. L. Bander and C. C. White, A heuristic search approach for a nonstationary stochastic shortest path problem with terminal cost. Trans. Sci. 36 (2002) 218–230. | Zbl | DOI

H. Beigy and M. R. Meybodi, Utilizing distributed learning automata to solve stochastic shortest path problems. Int. J. Uncertainty Fuzziness Knowledge Based Syst. 14 (2006) 591–616. | MR | Zbl | DOI

B. Bosek, D. Leniowski, P. Sankowski and A. Zych-Pawlewicz, Shortest augmenting paths for online matchings on trees. Theory Comput. Syst. 62 (2018) 337–348. | MR | DOI

S. Broumi, A. Dey, M. Talea, A. Bakali, F. Smarandache, D. Nagarajan, M. Lathamaheswari and R. Kumar, Shortest path problem using Bellman algorithm under neutrosophic environment. Complex Intell. Syst. 5 (2019) 409–416. | DOI

R. K. Cheung, Iterative methods for dynamic stochastic shortest path problems. Nav. Res. Logist. 45 (1998) 769–789. | Zbl | DOI

T. N. Chuang and J. Y. Kung, The fuzzy shortest path length and the corresponding shortest path in a network, Comput. Oper. Res. 32 (2005) 1409–1428. | MR | Zbl | DOI

T. N. Chuang and J. Y. Kung, A new algorithm for the discrete fuzzy shortest path problem in a network. Appl. Math. Comput. 174 (2006) 660–668. | MR | Zbl

J. S. Croucher, A note on the stochastic shortest-route problem. Nav. Res. Logist. 25 (1978) 729–732. | Zbl | DOI

Y. Deng, Y. Chen, Y. Zhang and S. Mahadevan, Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl. Soft Comput. 12 (2012) 1231–1237. | DOI

A. Dey, R. Pradhan, A. Pal and T. Pal, A genetic algorithm for solving fuzzy shortest path problems with interval type-2 fuzzy arc lengths. Malaysian J. Comput. Sci. 31 (2018) 255–270. | DOI

Y. Dou, L. Zhu and H. S. Wang, Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure. Appl. Soft Comput. 12 (2012) 1621–1631. | DOI

D. Dubois and H. Prade, Fuzzy Sets and Systems: Theory and Applications. Academic Press, New York, NY (1980). | MR | Zbl

A. Ebrahimnejad, Z. Karimnejad and H. Alrezaamiri, Particle swarm optimization algorithm for solving shortest path problems with mixed fuzzy arc weights. Int. J. Appl. Decis. Sci. 8 (2015) 203–222.

A. Ebrahimnejad, M. Tavana and H. Alrezaamiri, A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights. Measurement 93 (2016) 48–56. | DOI

M. Enayattabar, A. Ebrahimnejad and H. Motameni, Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment. Complex Intell. Syst. 5 (2019) 93–10. | DOI

M. Enayattabar, A. Ebrahimnejad, H. Motameni and H. Garg, A novel approach for solving all-pairs shortest path problem in an interval-valued fuzzy network. J. Intell. Fuzzy Syst. 37 (2019) 6865–6877. | DOI

M. Eshaghnezhad, F. Rahbarnia, S. Effati and A. Mansoori, An artificial neural network model to solve the fuzzy shortest path problem. Neural Proc. Lett. 50 (2019) 1527–1548. | DOI

Y. Gao, Shortest path problem with uncertain arc lengths. Comput. Math. App. 62 (2011) 2591–2600. | MR | Zbl

M. Ghiyasvand, A new approach for solving the minimum cost flow problem with interval and fuzzy data. Int. J. Uncertainty Fuzziness Knowledge Based Syst. 19 (2011) 71–88. | MR | Zbl | DOI

M. Ghiyasvand, Solving the minimum flow problem with interval bounds and flows. Sadhana 37 (2012) 665–674. | MR | DOI

M. Guillot and G. Stauffer, The stochastic shortest path problem: a polyhedral combinatorics perspective. Eur. J. Oper. Res. 285 (1) (2018) 148–158. | MR | DOI

Y. Guo, S. Li, W. Jiang, B. Zhang and Y. Ma, Learning automata-based algorithms for solving the stochastic shortest path routing problems in 5G wireless communication. Phys. Commun. 25 (2017) 376–385. | DOI

T. Hagerup, Simpler computation of single-source shortest paths in linear average time. Theory Comput. Syst. 39 (2006) 113–120. | MR | Zbl | DOI

S. M. Hashemi, M. Ghatee and E. Nasrabadi, Combinatorial algorithms for the minimum interval cost flow problem. Appl. Math. Comput. 175 (2006) 1200–1216. | MR | Zbl

R. Hassanzadeh, I. Mahdavi, N. Mahdavi-Amiri and A. Tajdin, A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Math. Comput. Model. 57 (2013) 84–99. | MR | Zbl | DOI

F. Hernandes, M. T. Lamata, J.-L. Verdegay and A. Yamakami, The shortest path problem on networks with fuzzy parameters. Fuzzy Sets Syst. 158 (2007) 1561–1570. | MR | Zbl | DOI

C. Horoba, Ant colony optimization for stochastic shortest path problems. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery, New York, NY (2010) 1465–1472. | DOI

K. R. Hutson and D. R. Shier, Extended dominance and a stochastic shortest path problem. Comput. Oper. Res. 36 (2009) 584–596. | MR | Zbl | DOI

X. Ji, Models and algorithm for shortest path problem. Appl. Math. Comput. 170 (2005) 503–514. | MR | Zbl

X. Ji, K. Iwamura and Z. Shao, New models for shortest path problem with problem with fuzzy arc lengths. Appl. Math. Model. 31 (2007) 259–269. | Zbl | DOI

J. Kamburowski, A note on the stochastic shortest route problem. Oper. Res. 33 (1985) 696–698. | Zbl | DOI

C. M. Klein, Fuzzy shortest paths. Fuzzy Sets Syst. 39 (1991) 27–41. | MR | Zbl | DOI

A. Kumar and M. Kaur, A new algorithm, for solving shortest path problem on a network with imprecise edge weight. App. Appl. Math. Int. J. 6 (2011) 602–619. | MR | Zbl

Y. Li, M. Gen and K. Ida, Solving fuzzy shortest path problems by neural networks. Comput. Ind. Eng. 31 (1996) 861–865. | DOI

K. C. Lin and M. S. Chern, The fuzzy shortest path problem and its most vital arcs. Fuzzy Sets Syst. 58 (1993) 343–353. | MR | Zbl | DOI

I. Mahdavi, R. Nourifar, A. Heidarzade and N. Mahdavi-Amiri, A dynamic programming approach for finding shortest chains in fuzzy network. Appl. Soft Comput. 9 (2009) 503–511. | DOI

P. Mani, S. Broumi and K. Muthusamy, A network shortest path algorithm via hesitancy fuzzy digraph. J. New Theory 27 (2019) 52–62.

H. Motameni and A. Ebrahimnejad, Constraint shortest path problem in a network with intuitionistic fuzzy arc weights, edited by J. Medina, M. Ojeda-Aciego, J. Verdegay, I. Perfilieva, B. Bouchon-Meunier and R. Yager. In: Vol. 855 of Communications in Computer and Information Science. Information Processing and Management of Uncertainty in Knowledge-Based Systems. Applications. IPMU 2018. Springer, New York, NY (2018).

I. Murthy and S. Sarkar, A relaxation-based pruning technique for a class of stochastic shortest path problems. Trans. Sci. 30 (1996) 220–236. | Zbl | DOI

I. Murthy and S. Sarkar, Stochastic shortest path problems with piecewise-linear concave utility functions. Manage. Sci. 44 (1998) 125–136. | Zbl | DOI

S. M. A. Nayeem and M. Pal, Shortest path problem on a network with imprecise edge weight. Fuzzy Optim. Decis. Making 4 (2005) 293–312. | MR | Zbl | DOI

E. Nikolova, J. A. Kelner, M. Brand and M. Mitzenmacher, Stochastic shortest paths via quasi-convex maximization. In: Vol. 4168 of Lecture Notes in Computer Science. Algorithms–ESA 2006. Springer, New York, NY (2006) 552–563. | MR | Zbl | DOI

Y. Ohtsubo, Stochastic shortest path problems with associative accumulative criteria. Appl. Math. Comput. 198 (2008) 198–208. | MR | Zbl

S. Okada, Fuzzy shortest path problems incorporating interactivity among paths. Fuzzy Sets Syst. 142 (2004) 335–357. | MR | Zbl | DOI

S. Okada and M. Gen, Order relation between intervals and its application to shortest path problem. Comput. Ind. Eng. 25 (1993) 147–150. | DOI

S. Okada and T. Soper, A shortest path problem on a network with fuzzy arc lengths. Fuzzy Sets Syst. 109 (2000) 129–140. | MR | Zbl | DOI

S. K. Peer and D. K. Sharma, Finding the shortest path in stochastic networks. Comput. Math. App. 53 (2007) 729–740. | MR | Zbl

G. H. Polychronopoulos and J. N. Tsitliklis, Stochastic shortest path problem with recourse. Networks 27 (1996) 133–143. | MR | Zbl | DOI

C. M. Ramos and F. Sagols, The minimum cost flow problem with interval and fuzzy arc costs. Morfismos 5 (2011) 57–68.

A. Sengupta and T. K. Pal, Theory and methodology on comparing interval numbers. Eur. J. Oper. Res. 127 (2000) 28–43. | MR | Zbl | DOI

A. Sengupta and T. K. Pal, Solving the shortest path problem with interval arcs. Fuzzy Optim. Decis. Making 5 (2006) 71–89. | MR | Zbl | DOI

D. Sever, L. Zhao, N. Dellaert, E. Demir, T. V. Woensel and T. D. Kok, The dynamic shortest path problem with time-dependent stochastic disruptions. Trans. Res. Part C: Emerg. Technol. 92 (2018) 42–57. | DOI

C. E. Sigal, A. A. B. Pritsker and J. J. Solberg, The stochastic shortest route problem. Oper. Res. 28 (1980) 1122–1129. | MR | Zbl | DOI

A. Tajdin, I. Mahdavi, N. Mahdavi-Amiri and B. Sadeghpour-Gildeh, Computing a fuzzy shortest path in a network with mixed fuzzy lengths using α -cut. Comput. Math. App. 60 (2010) 989–1002. | MR | Zbl

H. Yu and D. Bertsekas, On boundedness of Q-learning iterates for stochastic shortest path problems. Math. Oper. Res. 38 (2013) 209–227. | MR | Zbl | DOI

Z. Zero, C. Bersani, M. Paolucci and R. Sacile, Two new approaches for the bi-objective shortest path with a fuzzy objective applied to HAZMAT transportation. J. Hazard. Mater. 375 (2019) 96–106. | DOI

J. Zhang, J. Zhuang and B. Behlendorf, Stochastic shortest path network interdiction with a case study of Arizona–Mexico border. Reliab. Eng. Syst. Saf. 179 (2018) 62–73. | DOI

Cité par Sources :