661
1 INTRODUCTION
Inmanyapplicationssuchastransportation,routing,
communications, economical, and so on, graphs
emerge naturally as a mathematical model of the
observedrealworldsystem.Fuzzylogicisaformof
many‐valuedlogicorprobabilisticlogic;itdealswith
reasoning that is approximate rather than fixed and
exact. Compa
red to traditional binary sets (where
variablesmaytakeontrueorfalsevalues)fuzzylogic
variables may have a truth value that ranges in
degree between 0 and 1. Fuzzy logic has been
extendedtohandletheconceptofpartialtruth,where
the truth value may range between completely true
and complet
ely false. Djikstraʹs algorithm (named
afteritsdiscover,E.W.Dijkstra)solvestheproblemof
findingtheshortestpathfromapointinagraph(the
source)toadestination.Itturnsoutthatonecanfind
theshortestpathsfromagivensourcetoallpointsin
a graph in the same ti
me, hence this problem is
sometimes called the single‐source shortest paths
problem. Dijkstraʹs algorithm keeps two sets of
vertices:
S:Thesetofverticeswhoseshortestpathsfromthe
sourcehavealreadybeendeterminedand
V:‐Stheremainingvertices.
In finding the shortest path under uncertain
environment, an appropriate modelling approach is
tomakeuseoffuzzynumbers.Oneofthemostused
methods to solve the shortest path problem is the
Dijkstra algorithm. In the case of crisp number to
modelarclengths,theDijkstraalgorit
hmcanbeeasily
to implemented. However, due to the reason that
manyoptimizationmethodsforcrispnumberscannot
be applied directly to fuzzy numbers, some
modifications are needed before using the classical
methods.(BoominathanandKanchan,2014)
Routingproblemsinnetworksaretheproblemin
the context of sequencing and in recent ti
mes, they
have to receive progressive note. Congruous issues
usuallytakeplacesinthezonesoftransportationand
communications. A schedule problem engages
identifying a route from the one point to the other
because there are many of optional tracks in
miscellaneoushaltingplaceof thepassage.Thecost,
ti
me, safety or cost of travel are different for each
routes. Theoretically, the method comprises
determiningthecostofallprospectivetracksandthe
find with minimal expense. In fact, however, the
Routing Planning As An Application Of Graph Theory
with Fuzzy Logic
T.Neumann
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:The routingplanning oneof theclassic problemsin graphtheory. Itsapplication havevarious
practicalusesrangingfromthetransportation,civilengineering andotherapplications.Theresolutionofthis
paperistofindasolutionforrouteplanninginatransportnetworks,wherethedescriptionoftra
cks,factorof
safetyand traveltime areambiguous.In thestudy theranking system basedon thetheory ofpossibility is
proposed.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 10
Number 4
December 2016
DOI:10.12716/1001.10.04.17
662
amountofsuchoptionsaretoolargetobetestedone
after another. A traveling salesman problem is a
routing problem associated with preferably strong
restrictions.Differentroutingproblememergeswhen
itcantogofromonepointtoanotherpointorafew
points, and choose the best track
with the at the
lowestestimatelength,periodorcostofmanyoptions
toreachthedesiredpoint.Suchacyclicroutenetwork
problem easily can be solved by job sequencing. A
networkisdefinedasaseriesofpointsornodesthat
areinterconnectedbylinks.Onewaytogo
fromone
node to another is called a path. The problem of
sequencingmayhaveputsomerestrictionsonit,such
astimeforeachjoboneachmachine,theavailability
ofresources(people,equipment,materialsandspace),
etc.insequencingproblem,theefficiencywithrespect
to a minimumbe measured
costs, maximize profits,
andtheelapsedtimeisminimized.Thegraphimage
andtheexampleofcostsofbordersaregiven inthe
figure1.Inthishypotheticalideathetractnetworkis
illustratedbyagraph.Presentedgraphisgivenwith
an ordered pair G: = (V, E) comprising
a set V of
vertices or nodes together with a set E of edges
(paths),whichconnecttwonodes.Thetaskistoreach
the N1node fromN3 node inthe graphat smallest
cost.(Neumann,2016)
2 PATHFINDINGALGORITHMS
A path finding algorithm for transit network is
proposed to
handle the special characteristics of
transitnetworkssuchascityemergencyhandlingand
drive guiding system, in where the optimal paths
have to be found. As the traffic condition among a
citychangesfromtimetotimeandthereareusuallya
huge amounts of requests occur at any moment,
it
needs to quickly find the best path. Therefore, the
efficiency of the algorithm is very important . The
algorithm takes into account the overall level of
servicesandservicescheduleonaroutetodetermine
the shortest path and transfer points. There are
several methods for pathfinding: In Dijkstraʹs
algorithm the input of the algorithm consists of a
weighted directedgraphG and asource vertexes in
Graph.Let‘sdenotethesetofallverticesinthegraph
GasV.Eachedgeofthegraphisanorderedpairof
vertices(u,v)representingaconnectionfromvertex
u
tovertexv.ThesetofalledgesisdenotedE.Weights
ofedges aregiven bya weightfunction w:E → [0,
∞]; therefore w (u, v) is the non‐negative cost of
movingfromvertexutovertexv.Thecostofanedge
canbe
thoughtofasthedistancebetweenthosetwo
vertices.Thecostofapathbetweentwoverticesisthe
sumofcostsoftheedges inthatpath.Foragivenpair
ofverticessandtinV,thealgorithmfindsthepath
fromstotwithlowestcost
(i.e.theshortestpath).It
can also be used for finding costs of shortest paths
fromasinglevertexstoallotherverticesinthegraph
(BoominathanandKanchan,2014).
An ordered pair of sets G = (V, E) where V is a
nonempty finite set and E consisting
of 2‐element
subsets of elements of V is called a graph. It is
denotedbyG=(V,E).Viscalledvertexandedgeset
respectively. The elements in V and E are called
vertices and edgesrespectively. If elements of E are
ordered pairs, then G is called
a directed graph or
digraph. The vertices between which an edge exists
are called endpoints of the edge. An edge whose
endpoints are the same is called a loop. A graph
withoutloopsiscalledasimplegraph.
2.1 Dijkstraʹsalgorithm
For a given source vertex (node) in the
graph, the
algorithm finds the path with lowest cost (ie the
shortest path) between that vertex and every other
vertex.Itcanalsobeusedforfindingtheshortestcost
path from one vertex to a destination vertex by
stoppingthealgorithmisdeterminedbytheshortest
path to the destination
node. For example, if the
vertices of the graph represent the city and are the
costs ofrunning pathsedge distances betweenpairs
of cities connected directly to the road, Dijkstraʹs
algorithm can be used to find the shortest route
betweenonecityandallothercities.Asa
result,the
shortest path algorithm is widely used routing
protocols in a network, in particular the IS‐IS and
OpenShortestPathFirst.(Neumann,2014)
ShortcharacteristicofDijsktraalgorithm[2].
Theinputofthealgorithmconsistsofaweighted
directedgraphGandasourcevertexsinG
DenoteVasthesetofallverticesinthegraphG.
Each edge of the graph is an ordered pair of
vertices(u,v)
This representing a connection from vertex u to
vertexv
ThesetofalledgesisdenotedE
Weights of edges aregiven by a weight function
w:E → [0,∞)
Therefore w(u,v) is the cost of moving directly
fromvertexutovertexv
The cost of an edge can be thought of as (a
generalizationof)thedistancebetweenthosetwo
vertices
Thecostofapathbetweentwoverticesisthesum
ofcostsoftheedgesinthatpath
For a given pair of vertices s and t in V, the
algorithm finds the path from s to t with lowest
cost(i.e.theshortestpath)
It can also be used for finding costs of shortest
pathsfromasinglevertexstoallotherverticesin
thegraph.
Figure1.Dijkstrasalgorithmontreegraph
3 FUZZYNUMBERSANDPOSSIBILITYTHEORY
Incasewhenthereisneedtomodeluncertaintythat
originatesinindistinguishability,vaguesetc.itisnot
suitable to use statistical approaches and alternative
approachesisnecessary(GhateeandHashemi,2009).
663
Alternativeframeworkforallessentialoperationscan
befound inFuzzy settheory andPossibility theory.
(CahaandDvorsky,2015)
3.1 FuzzyNumbers
Fuzzy numbers are special cases of convex, normal
fuzzy sets defined on
ℝ with at least piecewise
continuous membership function, that represent
vague, imprecise or ill‐known value (Ghatee and
Hashemi, 2009). There are several types of fuzzy
numbers, commonly used are triangular and
trapezoidal ones, however other shapes arepossible
aswell (GhateeandHashemi, 2009).Triangular and
trapezoidal fuzzy numbers are
often used because
calculations with them and their comparison can be
done relatively easily, but it is much better if
calculations and comparisons can be done for any
shapeoffuzzynumbers.
Themostgeneraltypeoffuzzynumbersthatcan
be utilized for calculations are so called piecewise
linear fuzzy
numbers, these fuzzy numbers are
definedasasetofα‐cuts(GhateeandHashemi,2009).
They canapproximate anygiven shape and intheir
mostsimplerepresentationareequaltotriangularor
trapezoidalfuzzynumbers.
If there is need to combine fuzzy numbers with
classiccrispvaluesthencrispnumbers
aretreatedas
specialcaseoffuzzynumber,whereallα‐cutsarethe
same degenerative interval (Ghatee and Hashemi,
2009).
Figure2.Exampleoftriangularfuzzynumber
3.2 FuzzyArithmetic
Inorder toperformbasic arithmeticoperationswith
fuzzynumbersthereisneedforapparatusthatallows
andspecifiessuchoperations.Themostgeneralform
of such rule is specified by so called extension
principle (Zadeh, 1975), however this particular
definitioniscomplicatedintermsofimplementation,
so
alternative approaches that utilize decomposition
theoremandintervalarithmeticareused(Ghateeand
Hashemi, 2009). The decomposition theorem states
thateveryfuzzynumber(orgenerallyanyfuzzyset)
Ãcanbedescribedbyassociatedsequenceofα‐cuts.
Anα‐cut is an interval where all the objects have
membership at least
equalα. Formally it can is
written as:
|
A
cut A A x X x
(Ghatee
andHashemi,2009).Suchα‐cutofafuzzynumberis
always closed interval
A
ab
. The only
necessary arithmetic operation for determination of
shortest path is addition, using decomposition
theoremandintervalarithmetictheadditionoffuzzy
number
,
A
B
is(Mooreetal.,2009):
,
A
Babab
(1)
foreach
0,1
.Usingthisapproachtheadditionof
any two fuzzy numbers is possible (Caha and
Dvorsky,2015).
3.3 Possibilitytheory
To allow decision making based on fuzzy numbers
thereisaneedforasystemthatwillallowrankingof
fuzzy numbers. There are several such systems
however most of them
consider only one point of
view onthe problem (Duboisand Prade, 1983). The
complete set ofranking indicesin the frameworkof
possibility theory was proposed in (Dubois and
Prade,1983).Thisrankingsystemusespossibilityand
necessitymeasurestodeterminerelationoftwofuzzy
numbers (CahaandDvorsky,
2015).
Utilization of possibility theory allows also
semantically describe fuzzy numbers as possibility
distributions (Zadeh, 1975). This semantic than help
us explaining what such fuzzy numbers mean. The
values with membership value 1 are believed to be
absolutelypossibleorunsurprising,thustheyshould
covethemostlikelyresult.Withdecreasing
degreeof
membershipthe possibilityof obtaininggiven result
decreases and the surprise rises. When membership
value reaches 0 then such result is impossible (or
almostimpossibleatsomecases)andthesurprisethat
suchresultwouldpresentismaximal.Suchsemantics
helpswithpracticalexplanationwhattheresultstruly
mean.
To asses position of fuzzy number
X
to the fuzzy
number
Y
four indices are needed (Dubois and
Prade, 1983). Two of them define possibility and
necessitythat
X
isatleastequalorgreaterthan
Y
:
,supmin ,sup
XXY
xyx
Yxy
(2)
, inf max 1 ,sup
XXY
x
yx
N
Yxy
(3)
The other two determine if
X
is strictly greater
than
Y
:
,supmin ,inf1
XXY
yx
x
Yxy
(4)
, inf max 1 , inf 1
XXY
xyx
N
Yxy
(5)
Together these indices allow comparison of any
two fuzzy numbers, based on pairwise comparison
anysetoffuzzynumberscanbesorted.
664
Forbothsetofindicestherearefoursituationsof
thecombinationsofpossibilityandnecessitythatcan
beoutcomeofthecalculation.Inthisparagraphboth
relations – at least equal or greater, and strictly
greater – are referred as relation, because the
descriptions are valid for both pairs
of indices. The
first situation is when
,,0
XX
YNY
,
whichmeansthat
X
isdefinitelydoesnotfulfilthe
givenrelationto
Y
.Thenthereisoppositesituation
in which
X
completely satisfy the relation. The
other two relations contains some uncertainty,
becausethey indicatecertain resultsbut theycannot
providethemabsolutely.Thefirstofthoseissituation
when
,0
X
Y
and
,0
X
NY
. This means
that there is possibility that X̃ might satisfy the
relation,butitisnotnecessary.Obviouslythatmeans
that the indicators are not strong. The last possible
combination of values is
,1
X
Y
and
,0
X
NY
.Insuchcaseagainittherelationisnot
satisfied absolutely but the indicators are much
stronger than in previous case (Caha and Dvorsky,
2015).
4 FUZZYGRAPHTHEORY
Itisquitewellknownthatgraphsaresimplymodels
of relations. A graph is a convenient way of
representing information
involving relationship
between objects. The objects are represented by
vertices and relations by edges. When there is
vagueness in the description of the objects or in its
relationshipsorinboth,itisnaturalthatweneedto
design aʹFuzzy Graph Modelʹ (Sunitha and Sunil,
2013).
That is well
known that a graph is a symmetric
binary relation on a nonempty set V. Similarly, a
fuzzygraphisasymmetricbinaryfuzzyrelationona
fuzzy subset. The concept of fuzzy sets and fuzzy
relationswasintroducedbyL.A.Zadeh(Zadeh,1975).
It was (Rosenfeld, 1975) who considered fuzzy
relations on
fuzzy sets and developed the theory of
fuzzygraphsin1975.
A graph is a convenient way of representing
information involving relationship between objects.
Theobjectsarerepresentedby verticesandrelations
byedges.Inmanyrealworldproblems,wegetpartial
informationaboutthatproblem.Sothereisvagueness
inthedescriptionoftheobjectsorinitsrelationships
orinboth(Myna,2015).
5 CONCLUSIONS
The modification of the Dijkstra algorithm aims to
provide support for better decision‐making in
situationsofuncertainty.Itshouldbehelpful,butall
solutionscannotbedistinguishedbyproviding.This
is used of
theory possibility to manage the
uncertaintyandtheambiguity.
Theuseoffuzzynumbersasweightsinthegraph
allows for better modelling of real situations where
the time travel fromone point to another cannotbe
specifiedexactlyorothersimilarcases.Thetimeasa
sharp number can
indicate a much idealization and
simplificationoftheproblembecausethealgorithms
forthesearchthenoptimalwayidealizedtoproduce
solutions that are not in the calculation of either
uncertainty or the amount of dissimilarity of the
solutions.
REFERENCES
Boominathan, P., Kanchan, A., 2014. Routing Planning As
AnApplicationOfGraphTheory.Internationaljournal
ofscientific&technologyresearch3,61–66.
Caha, J., Dvorsky, J., 2015. Optimal path problem with
possibilistic weights, in: Geoinformatics for Intelligent
Transportation, Lecture Notes in Geoinformation and
Cartography.SpringerInternationalPublishing,pp.39–
50.
Dubois,
D.,Prade,H.,1983.RankingFuzzyNumbersinthe
Setting of Possibility Theory. Information Sciences 30,
183–224.
Ghatee, M., Hashemi, S.M., 2009. Application of fuzzy
minimumcostflowproblemsto networkdesignunder
uncertainty.FuzzySetsandSystems160,3263–3289.
Moore,R.E.,Kearfott,R.B., Cloud, M.J., 2009.Introduction
to interval analysis.
Society forIndustrial and Applied
Mathematics,Philadelphia,PA.
Myna, R., 2015. Application of Fuzzy Graph in Traffic.
International Journal of Scientific & Engineering
Research6,1692–1696.
Neumann, T., 2016. The Shortest Path Problem with
Uncertain Information in Transport Networks, in:
Mikulski, J. (Ed.), Challenge of Transport Telematics,
CommunicationsinComputer
andInformationScience.
SpringerInternationalPublishing,pp.475–486.
Neumann,T.,2014.MethodofPathSelectionintheGraph‐
Case Study. TransNav, the International Journal on
Marine Navigation and Safetyof Sea Transportation8,
557–662.doi:DOI:10.12716/1001.08.04.10
Rosenfeld,A.,1975.Fuzzygraphs,in:Zadeh,L.A.,Fu,K.S.,
Shimura,M. (Eds.),FuzzySets
and Their Applications.
AcademicPress,NewYork,pp.77–95.
Sunitha, M.S., Sunil, M., 2013. Fuzzy Graph Theory: A
Survey.AnnalsofPureandAppliedMathematics4,92–
110.
Zadeh,L.A.,1975.Theconceptofalinguisticvariableand
its application to approximate reasoning. Information
Sciences8,199–249.
