Document Type : Research Paper

**Authors**

Department of GIS Engineering, K. N. Toosi University of Technology, ValiAsr Street, Mirdamad cross, P.C. 19967-15433, Tehran, Iran

**Abstract**

Numerous algorithms have been proposed to solve the shortest-path

problem; many of them consider a single-mode network and crisp

costs. Other attempts have addressed the problem of fuzzy costs in

a single-mode network, the so-called fuzzy shortest-path problem

(FSPP). The main contribution of the present work is to solve the

optimum path problem in a multimodal transportation network, in

which the costs of the arcs are fuzzy values. Metropolitan

transportation systems are multimodal in that they usually contain

multiple modes, such as bus, metro, and monorail. The proposed

algorithm is based on the path algebra and dioid of $k$-shortest

fuzzy paths. The approach considers the number of mode changes,

the correct order of the modes used, and the modeling of two-way

paths. An advantage of the method is that there is no restriction

on the number and variety of the services to be considered. To

track the algorithm step by step, it is applied to a

pseudo-multimodal network.

problem; many of them consider a single-mode network and crisp

costs. Other attempts have addressed the problem of fuzzy costs in

a single-mode network, the so-called fuzzy shortest-path problem

(FSPP). The main contribution of the present work is to solve the

optimum path problem in a multimodal transportation network, in

which the costs of the arcs are fuzzy values. Metropolitan

transportation systems are multimodal in that they usually contain

multiple modes, such as bus, metro, and monorail. The proposed

algorithm is based on the path algebra and dioid of $k$-shortest

fuzzy paths. The approach considers the number of mode changes,

the correct order of the modes used, and the modeling of two-way

paths. An advantage of the method is that there is no restriction

on the number and variety of the services to be considered. To

track the algorithm step by step, it is applied to a

pseudo-multimodal network.

**Keywords**

S. Abbasbandy and M. Alavi, {it A method for solving fuzzy linear

systems}, Iranian Journal of Fuzzy Systems, {bf 4} (1988), 37-44.

bibitem{Biel:Boul:Moun}

M. Bielli, A. Boulmakoul and H. Mouncif, {it Object modeling and

path computation for multimodal travel systems}, Eur. J. Oper.

Res., {bf 175} (2006), 1705-1730.

bibitem{Boul}

A. Boulmakoul, {it Generalized path-finding algorithms on

semirings and the fuzzy shortest path problem}, Comput. Appl.

Math., {bf 162} (2004), 263-272.

bibitem{Boul:Laur:Moun:Taqa}

A. Boulmakoul, R. Laurini, H. Mouncif and G. Taqafi, {it

Path-finding operators for fuzzy multimodal spatial networks and

their integration in mobile-GIS}, Proceedings of the IEEE

International Symposium on Signal Processing and Information

Technology, (2002), 51-56.

bibitem{Buht:Mord:Rose}

K. R. Buhtani, J. Mordeson and A. Rosenfeld, {it On degrees of

end nodes and cut nodes in fuzzy graphs}, Iranian Journal of Fuzzy Systems,

{bf 1} (2004), 57-64.

bibitem{Cade:Verd}

K. M. Cadenas and J. L. Verdegay, {it A primer on fuzzy

optimization models and methods}, Iranian Journal of Fuzzy Systems, {bf

5} (2006), 1-22.

bibitem{Chua:Kung}

T. N. Chuang and J. Y. Kung, {it A new algorithm for the discrete

fuzzy shortest path problem in a network}, Appl. Math. Comput.,

{bf 174} (2006), 660-668.

bibitem{Chua:Kung2}

T. N. Chuang and J. Y. Kung, {it The fuzzy shortest path length and

the corresponding shortest path in a network}, Comput. Oper. Res.,

{bf 32} (2005), 1409-1428.

bibitem{Corm:Leis:Rive:Stei}

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, {it

Introduction to algorithms}, Second ed., MIT Press and

McGraw-Hill, (2001), 588-601.

bibitem{Dech:Pear}

R. Dechter and J. Pearl, {it Generalized best-first search

strategies and the optimality of $A^*$}, J. ACM, {bf 32} (1985),

505-536.

bibitem{Dubo:Prad}

D. Dubois and H. Prade, {it Fuzzy sets and systems: theory and

applications}, Academic Press, New York, 1980.

bibitem{Gond:Mino}

M. Gondran and M. Minoux, {it Dioids and semirings: links to

fuzzy sets and other applications}, Fuzzy Sets and Systems, {bf

158} (2007), 1273-1294.

bibitem{Gond:Mino2}

M. Gondran and M. Minoux, {it Linear algebra in dioids: a survey

of recent results}, Ann. Discrete Math., {bf 19} (1984), 147-164.

bibitem{Hern:Lama:Verd:Yama}

F. Hernandes, M. T. Lamata, J. L. Verdegay and A. Yamakami, {it The

shortest path problem on networks with fuzzy parameters}, Fuzzy Sets and Systems, {bf 158} (2007), 1561-1570.

bibitem{Ji:Iwam:Sha}

X. Ji, K. Iwamura and Z. Shao, {it New models for shortest path

problem with fuzzy arc lengths}, Appl. Math. Modell., {bf

31} (2007), 259-269.

bibitem{Kesh:Ales:Khei}

A. Keshtiarast, A. A. Alesheikh and A. Kheirbadi, {it Best route

finding based on cost in multimodal network with care of networks

constraints}, Map Asia Conference, India, {bf 66} (2006).

bibitem{Lin:Cher}

K. C. Lin and M. S. Chern, {it The fuzzy shortest path problem and

its most vital arcs}, Fuzzy Sets and Systems, {bf 58} (1993), 343-353.

bibitem{Loza:Stor}

A. Lozano and G. Storchi, {it Shortest viable path algorithm in

multimodal networks}, Transport. Res., {bf 35} (2001), 225-241.

bibitem{Mill:Stor:Bowe}

H. J. Miller, J. D. Storm and M. Bowen, {it GIS design for

multimodal networks analysis}, GIS/LIS 95 Annual Conference and

Exposition Proceedings of GIS/LIS, (1995), 750-759.

bibitem{Moaz}

S. Moazeni, {it Fuzzy shortest path problem with finite fuzzy

quantities}, Appl. Math. Comput., {bf 183} (2006), 160-169.

bibitem{Mode:Scio}

P. Modesti and A. Sciomachen, {it A utility measure for finding

multiobjective shortest paths in urban multimodal transportation

networks}, Eur. J. Oper. Res., {bf 111} (1998), 495-508.

bibitem{Naye:Pal}

S. Nayeem and M. Pal, {it Shortest path problem on a network

with imprecise edge weight}, Fuzzy Optim. Decis. Making, {bf

4} (2005), 293-312.

bibitem{Okad}

S. Okada, {it Fuzzy shortest path problems incorporating

interactivity among paths}, Fuzzy Sets and Systems, {bf 142} (2004),

335-357.

bibitem{Okad:Sope}

S. Okada and T. Soper, {it A shortest path problem on a network

with fuzzy arc lengths}, Fuzzy Sets and Systems, {bf 109} (2000),

129-140.

bibitem{Shie}

D. Shier, {it On algorithms for finding the K-shortest paths in a

network}, Networks, {bf 9} (1979), 195-214.

September and October 2010

Pages 1-13