SOLVING BEST PATH PROBLEM ON MULTIMODAL TRANSPORTATION NETWORKS WITH FUZZY COSTS

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.

Keywords


bibitem{Abba:Alav}
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.