[1] Liu Chunlin**, He Jianmin, Shi Jianjun,. New Methods to Solve Fuzzy Shortest Path Problems* [J]. Journal of Southeast University (English Edition), 2001, 17 (1): 18-21. [doi:10.3969/j.issn.1003-7985.2001.01.005]

Copy

New Methods to Solve Fuzzy Shortest Path Problems^*()

模糊最短路问题的新方法

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

17

Issue:

2001 1

Page:

18-21

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2001-06-30

Info

Title:

New Methods to Solve Fuzzy Shortest Path Problems^*

模糊最短路问题的新方法

Author(s):

Liu Chunlin^1**, He Jianmin², Shi Jianjun¹

¹Business School, Nanjing University, Nanjing 210093, China
²College of Economics and Management, Southeast University, Nanjing 210096, China

刘春林¹, 何建敏², 施建军¹

¹南京大学商学院, 南京 210093; ² 东南大学经济管理学院, 南京 210096

Keywords:

triangular fuzzy number;  fuzzy shortest path;  ranking function

三角形模糊数;  模糊最短路;  排序函数

PACS:

O221.2

DOI:

10.3969/j.issn.1003-7985.2001.01.005

Abstract:

This paper discusses the problem of finding a shortest path from a fixed origin s to a specified node t in a network with arcs represented as typical triangular fuzzy numbers(TFN). Because of the characteristic of TFNs, the length of any path p from s to t, which equals the extended sum of all arcs belonging to p, is also TFN. Therefore, the fuzzy shortest path problem(FSPP)becomes to select the smallest among all those TFNs corresponding to different paths from s to t(specifically, the smallest TFN represents the shortest path). Based on Adamo’ s method for ranking fuzzy number, the pessimistic method and its extensions — optimistic method and λ-combination method, are presented, and the FSPP is finally converted into the crisp shortest path problems.

本文讨论三角形模糊网络中节点s到终点t的最短路问题.根据三角形模糊数(TFN)的性质可知, 连结节点s和t的任何路p的长度(p所经过路径的长度的扩展和)也是三角形模糊数.因此, 模糊网络最短路问题本质上就是TFN的选择比较问题, 即在连结s和t的所有路中选择长度(TFN)最小的一个.根据Adamo的模糊数悲观排序方法, 以及它的扩展——乐观排序方法和λ-组合排序方法, 模糊网络最短路问题最终可以转化为确定网络的最短路问题.

References:

[1] C.M. Klein, Fuzzy shortest paths, Fuzzy Sets and Systems, vol.39, pp. 27-41, 1991
[2] Y.L.Chen, and K.Tang, Minimum time paths in a network with mixed time constraints, Computers and Operations Research, vol.25, no.2, pp. 783-805, 1998
[3] Y.L.Chen, and K.Tang, Shortest paths in time-schedule networks, Internat. J. Operations and Quantitative Management, vol.3, no.1, pp. 157-173, 1997
[4] Y. Hadas, and A. Ceder, Shortest path of emergency vehicles under uncertain urban traffic conditions, Transportation Research Record, vol.11, no.1, pp. 34-39, 1996
[5] S.Okada, and M.Gen, Fuzzy shortest path problem, Computers Industrial Engineering, vol. 27, no.4, pp. 465-468, 1994
[6] G.Facchinetti, R.G.Ricci, and S.Muzzioli, Note on ranking fuzzy triangular numbers, Internat. J. Intelligent Systems, vol.13, no. 4, pp.613-622, 1998
[7] S.Okada, and M.Gen, Order Relation between intervals and its application to shortest path 0problem, Computers Industrial Engineering, vol. 25, no.1, pp.147-150, 1994
[8] J.M.Adamo, Fuzzy decision trees, Fuzzy Sets and Systems, vol. 4, pp. 207-219, 1980
[9] S.M.Baas, and H.Kwakernaak, Rating and ranking of multiple-aspect alternatives using fuzzy sets, Automatica, vol.13, no.1, pp. 47-58, 1977
[10] J.F.Baldwin, and N.C.F. Guild, Comparison of fuzzy sets on the same decision space, Fuzzy Sets and Systems, vol.2, no.1, pp. 213-233, 1979
[11] G.Bortolan, and R.Degani, A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems, vol.15, pp.1-19, 1985

Memo

Memo:

* The project supported by the National Nature Science Foundation of China(79970096).
** Born in 1970, male, doctor.

Common functions