ALGORITHMS FOR BIOBJECTIVE SHORTEST PATH PROBLEMS IN FUZZY NETWORKS

Document Type: Research Paper

Authors

1 Department of Industrial Engineering, Mazandaran University of Sci- ence & Technology, Babol, Iran

2 Faculty of Mathematical Sciences, Sharif University of Tech- nology, Tehran, Iran

3 Department of Industrial Engineering, Mazandaran University of Science & Technology, Babol, Iran

Abstract

We consider biobjective shortest path problems in networks with
fuzzy arc lengths. Considering the available studies for single objective shortest
path problems in fuzzy networks, using a distance function for comparison of
fuzzy numbers, we propose three approaches for solving the biobjective prob-
lems. The rst and second approaches are extensions of the labeling method to
solve the single objective problem and the third approach is based on dynamic
programming. The labeling methods usually producing several nondominated
paths, we propose a fuzzy number ranking method to determine a fuzzy short-
est path. Illustrative examples are worked out to show the e
ectiveness of our
algorithms.

Keywords


bibitem{baas1977rating}
S. M. Baas and H.~Kwakernaak, {it Rating and ranking of multiple-aspect alternatives using fuzzy
  sets}, Automatica, {bf 13}textbf{(1)} (1977), 47-58.

bibitem{baldwin1979comparison}
J. F. Baldwin and N. C. F Guild, {it Comparison of fuzzy sets on the same decision space}, Fuzzy Sets and Systems, {bf 2}textbf{(3)} (1979), 213-231.

bibitem{bellman1958routing}
R.~Bellman, {it On a routing problem, Quart}, J. Appl. Math, {bf 16}textbf{(1)} (1958), 87-90.

bibitem{bortolan1985review}
G.~Bortolan and R.~Degani, {it A review of some methods for ranking fuzzy subsets}, Fuzzy Sets and Systems, {bf 15}textbf{(1)} (1985), 1-19.

bibitem{brumbaugh1989empirical}
D.~Brumbaugh-Smith and D. Shier, {it An empirical investigation of some bicriterion shortest path
  algorithms}, European Journal of Operational Research, {bf 43}textbf{(2)} (1989), 216-224.

bibitem{campos1989subjective}
L.~Campos and A.~Munoz, {it A subjective approach for ranking fuzzy numbers}, Fuzzy Sets and Systems, {bf 29}textbf{(12)} (1989), 145-153.

bibitem{chanas1995fuzzy}
S.~Chanas, M.~Delgado, J. L. Verdegay, and M. A. Vila, {it Fuzzy optimal flow on imprecise structures}, European Journal of Operational Research, {bf 83}textbf{(3)} (1995), 568-580.

bibitem{chang1981ranking}
W.~Chang, {it Ranking of fuzzy utilities with triangular membership functions}, In Proc. Int. Conf. of Policy Anal. and Inf. Systems, (1981), 263-272.

bibitem{chen1985ranking}
S. H. Chen, {it Ranking fuzzy numbers with maximizing set and minimizing set}, Fuzzy Sets and Systems, {bf 17}textbf{(2)} (1985), 113-129.

bibitem{choobineh1993index}
F.~Choobineh and H.~Li, {it An index for ordering fuzzy numbers}, Fuzzy Sets and Systems, {bf 54}textbf{(3)} (1993), 287-294.

bibitem{delgado1990valuation}
M.~Delgado, J. L. Verdegay and M. A. Vila, {it On valuation and optimization problems in fuzzy graphs: a general
  approach and some particular cases}, INFORMS Journal on Computing, {bf 2}textbf{(1)} (1990), 74.

bibitem{dijkstra1959note}
E. W. Dijkstra, {it A note on two problems in connexion with graphs}, Numerische mathematik, {bf 1}textbf{(1)} (1959), 269-271.

bibitem{dreyfus1969appraisal}
S. E. Dreyfus, {it An appraisal of some shortest-path algorithms}, Operations Research, {bf 17}textbf{(3)} (1969), 395-412.

bibitem{dubois1978algorithmes}
D.~Dubois and H.~Prade, {it Algorithmes de plus courts chemins pour traiter des donnees floues.
  RAIRO-Recherche Op{'e}rationnelle}, Operations Research, {bf 12}(1978), 212--227.

bibitem{dubois1980fuzzy}
D.~Dubois and H.~Prade, {it Fuzzy sets and systems: theory and applications}, Academic Pr, 1980.

bibitem{furukawa1994parametric}
N.~Furukawa, {it A parametric total order on fuzzy numbers and a fuzzy shortest route
  problem}, Optimization, {bf 30}textbf{(4)} (1994), 367-377.

bibitem{hansen1980bicriterion}
P.~Hansen, {it Bicriterion path problems}, In Multiple criteria decision making: theory and application:
  proceedings of the third conference, Hagen/K{`e}onigswinter, West Germany,
  August 20-24, (1979), 109, Springer, 1980.

bibitem{helgason1995primal}
R.V. Helgason and J. L. Kennington, {it Primal simplex algorithms for minimum cost network flows}, Handbooks in Operations Research and Management Science, {bf 7} (1995), 85-133.

bibitem{huarng1996computational}
F.~Huarng, P. Pulat, and L. S. Shih, {it A computational comparison of some bicriterion shortest path
  algorithms}, Journal of the Chinese Institute of Industrial Engineers, {bf 13}textbf{(2)} (1996), 121-125.

bibitem{klein1991fuzzy}
C. M. Klein, {it Fuzzy shortest paths}, Fuzzy Sets and Systems, {bf 39}textbf{(1)} (1991), 27-41.

bibitem{k—czy1992fuzzy}
L. T. K{'o}czy, {it Fuzzy graphs in the evaluation and optimization of networks}, Fuzzy Sets and Systems, {bf 46}textbf{(3)} (1992), 307-319.

bibitem{lin1993fuzzy}
K. C. Lin and M. S. Chern, {it The fuzzy shortest path problem and its most vital arcs}, Fuzzy Sets and Systems, {bf 58}textbf{(3)} (1993), 343-353.

bibitem{liou1992ranking}
T. S. Liou and M. J. J. Wang, {it Ranking fuzzy numbers with integral value}, Fuzzy Sets and Systems, {bf 50}textbf{(3)} (1992), 247-255.

bibitem{mahdavi2009dynamic}
I.~Mahdavi, R.~Nourifar, A.~Heidarzade and N. M. Amiri, {it A dynamic programming approach for finding shortest chains in a fuzzy network}, Applied Soft Computing, {bf 9}textbf{(2)} (2009), 503-511.

bibitem{martins1984multicriteria}
E. Q. V. Martins, {it On a multicriteria shortest path problem}, European Journal of Operational Research, {bf 16}textbf{(2)} (1984), 236-245.

bibitem{ishwar1991parametric}
J.~Mote, I.Murthy and D. L. Olson {it A parametric approach to solving bicriterion shortest path problems}, European Journal of Operational Research, {bf 53}textbf{(1)} (1991), 81-92.

bibitem{namorado1982bicriterion}
J. C. Namorado~Climaco and E.~Queiros Vieira~Martins, {it A bicriterion shortest path algorithm}, European Journal of Operational Research, {bf 11}textbf{(4)} (1982), 399-404.

bibitem{okada2000shortest}
S.~Okada and T.~Soper, {it A shortest path problem on a network with fuzzy arc lengths}, Fuzzy Sets and Systems, {bf 109}textbf{(1)} (2000), 129-140.

bibitem{prade1979using}
H.~Prade, {it Using fuzzy set theory in a scheduling problem: a case study}, Fuzzy Sets and Systems, {bf 2}textbf{(2)} (1979), 153-165.

bibitem{przybylski2008two}
A.~Przybylski, X.~Gandibleux and M.~Ehrgott, {it Two phase algorithms for the bi-objective assignment problem}, European Journal of Operational Research, {bf 185}textbf{(2)} (2008), 509-533.

bibitem{ram’k1985inequality}
J. Ram{'i}k and J. Rimanek, {it Inequality relation between fuzzy numbers and its use in fuzzy optimization}, Fuzzy Sets and Systems, {bf 16}textbf{(2)} (1985), 123-138.

bibitem{saade1992ordering}
J. J. Saade and H.~Schwarzlander, {it Ordering fuzzy sets over the real line: an approach based on
  decision making under uncertainty}, Fuzzy Sets and Systems, {bf 50}textbf{(3)} (1992), 237-246.

bibitem{sadeghpour2001distance}
B.~Sadeghpour~Gildeh and D.~Gien, {it La distance-Dp, q et le cofficient de corr{'e}lation entre deux
  variables al{'e}atoires floues}, Actes de LFA, (2001), 97-102.

bibitem{serafini1987some}
P.~Serafini, {it Some considerations about computational complexity for multi
  objective combinatorial problems}, In Recent Advances and Historical Development of Vector
  Optimization: Proceedings of an International Conference of Vector
  Optimization Held at the Technical University of Darmstadt, FRG, August 4-7,
  (1986), 222, Springer, 1987.

bibitem{skriver2000label}
A. J. V. Skriver and K. A. Andersen, {it A label correcting approach for solving bicriterion shortest-path problems}, Computers & Operations Research, {bf 27}textbf{(6)} (2000), 507-524.

bibitem{skriver2000classification}
A. J. V. Skriver, {it A classification of bicriterion shortest path (BSP) algorithms}, Asia Pacific Journal of Operational Research, {bf 17}textbf{(2)} (2000), 199-212.

bibitem{TajdinMahdavi2010}
A.~Tajdin, I.~Mahdavi, N.~Mahdavi-Amiri and B.~Sadeghpour-Gildeh, {it Computing a fuzzy shortest path in a network with mixed fuzzy arc lengths using $alpha$ -cuts}, Computer and Mathematics with Applications, 2010.

bibitem{tung1988bicriterion}
C. T. Tung and K. L. Chew, {it A bicriterion Pareto-optimal path algorithm}, ASIA-PACIFIC J. OPER. RES., {bf 5}textbf{(2)} (1988), 166-172.

bibitem{tung1992multicriteria}
C.~Tung and K.~Lin~Chew, {it A multicriteria Pareto-optimal path algorithm}, European Journal of Operational Research, {bf 62}textbf{(2)} (1992), 203-209.

bibitem{wang1997comparative}
X.~Wang, {it A comparative study of the ranking methods for fuzzy quantities}, Ghent University, Ghent, 1997.

bibitem{wang2001reasonable}
X.~Wang and E. E. Kerre, {it Reasonable properties for the ordering of fuzzy quantities (I)}, Fuzzy Sets and Systems, {bf 118}textbf{(3)} (2001), 375-385.

bibitem{wang2001reasonable2}
X.~Wang and E. E. Kerre, {it Reasonable properties for the ordering of fuzzy quantities (II)}, Fuzzy Sets and Systems, {bf 118}textbf{(3)} (2001), 387-405.

bibitem{yager1980general}
R. A. Yager, {it On a general class of fuzzy connectives}, Fuzzy sets and Systems, {bf 4}textbf{(3)} (1980), 235-242.

bibitem{yager1986paths}
R. A. Yager, {it Paths of least resistance in possibilistic production systems}, Fuzzy Sets and Systems, {bf 19}textbf{(2)} (1986), 121-132.

bibitem{zadeh1965fuzzy}
L. A. Zadeh, {it Fuzzy sets}, Information and control, {bf 8}textbf{(3)} (1965), 338-353.