459
1 INTRODUCTION
Manyworksdealwithrouteselection,navigation in
thetransportsector,veryfewmodelstakeuncertainty
into account information (or lack of information).
There are some works in transport research, which
take account of the uncertainty by Dempster‐Shafer
theory. The major application of this theory is the
decision ma
king, statistics and geographic
information systems. Intelligent Driving recognition
withExpertSystemusedDempster‐Shafertheoryfor
recognizingperformedbythedrivermanoeuvresthe
data from the sensors is installed in a vehicle.
Uncertaintyinformationmodelshavebeenusedonly
forthelocal problem,butourfocusisglobal:Theaim
oftheresearchisba
sedinformationtosolverouting
problemsonuncertainty.Dempster‐Shafertheoryisa
theory of uncertainty that can quantify a specific
statementtheextenttowhichsupportsomesourceof
evidence.Infact,thereisanalternativetotraditional
probabilitytheory,sothat the explicitrepresentation
of ignorance and combinat
ion of evidence. This
theorywasoriginallydevelopedbyDempster[3]and
then extended by Shafer in his book in 1976, A
MathematicalTheoryofEvidence[14].
The scientific and technological progress is
bringing some new solutions. There are more and
more electronic devices on the vessel’s bridge. That
cause1navigatorhastheaccesstova
rioussystemsof
theexchangeofdata.Someofthemcanreceivedata,
other combines send‐receive operation. The
navigator’s assessment of collision risk depends on
his knowledge about own ship’s motion and other
ships’motion.Theavailablemeansforassessing the
otherships’motionare for example: visua
lsighting,
radar,ARPA,AISandthevoicecommunicationwith
other ships. Each of enumerated systems possesses
particular reliable features. Voice communication,
radarandvisualsightinggiverealtimeinformation.
Eachofthemisaseparatesystemonthebridgeofthe
vessel. The most difficult for the navigator can be
predicting the situation in adv
ance if the safety
marginsaresmall,asincongestedwaters. Thesame
appliesfor AutomaticIdentification Systems (AIS) if
onlythetextdisplayisprovided.Itisappeared,that
the AIS will be able to replace many of enumerated
mea
nsofcommunication[6].
Routingproblemsinnetworksaretheproblemin
the context of sequencing and in recent times, they
Vessels Route Planning Problem with Uncertain Data
T.Neumann
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:Thepurposeofthispaperistofindasolutionforrouteplanninginamaritimetransportnetworks,
where the factor of safety and travel time are ambiguous. This approach is based on the Dempster‐Shafer
theory and well known Dijkstraʹs algorithm. In this a
pproach important are the influencing factors of the
mentionedcoefficientsusinguncertainpossibilitiespresentedbyprobabilityintervals.Basedontheseintervals
thequalityintervalsofeachroutecanbedetermined.Applieddecisionrulescanbedescribedbytheenduser.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 10
Number 3
September 2016
DOI:10.12716/1001.10.03.11
460
have to receive increasing attention. Such problems
usually occur in the areas of transportation and
communications. A network problem involves
identifying a route from the source to destination
because there are a number of alternative paths in
variousstagesofthejourney.Thecost,time,safetyor
cost of travel
are different for each routes.
Theoretically,themethodcomprisesdeterminingthe
costofallpossibleroutesandthefindwithminimal
cost. In practice, however, the number of such
alternativesaretoolargetobetriedoneafteranother.
Thetravelingsalesmanproblemisaroutingproblem
associated with rather
severe restrictions. Another
routing problem arises when it can to go from one
place to another or several other places, and choose
the shortest route with the least distance or time or
cost of many alternatives to achieve the desired
station.Suchacyclicroutenetworkproblemeasilycan
besolvedby
jobsequencing.Anetworkisdefinedas
aseriesofpointsornodesthatareinterconnectedby
links. One way to go from one node to another is
called a path. The problem of sequencing may have
putsomerestrictionsonit,suchastimeforeachjob
oneach
machine,theavailabilityofresources(people,
equipment, materials and space), etc. in sequencing
problem,theefficiencywithrespecttoaminimumbe
measured costs, maximize profits, and the elapsed
timeisminimized. Thegraphandthecostsofedgesis
given in the figure 1. In this theoretical concept the
road
network is represented by a graph. A graph is
givenwithanorderedpairG:=(V, E) comprisinga
set V of vertices or nodes together with a set E of
edges(paths),whichconnecttwonodes.Thetaskisto
reach the N1 node from N3 node in
the graph at
smallestcost[10].
Figure1.Graphwithdefinedvalues ofcostsofpaths.
Conventional Dijkstraʹs [3] should provide the
shortest route in the graph with non‐negative edge
path costs, but described example include
uncertainty. Therefore Dempster‐Shafer theory is
required, which concern with uncertainty by belief
functions. In Dempster‐Shafer theory the set
12
, ,...,
n
A
AA
of all the eventual conditions of
the structure. It can be presented by
P
the
powerset
2
.
12 12
2 , , ,..., , ,...,PAAAA
(1)
Dempster‐Shafertheorydesignatefunctions
m
calledBasicBeliefAssignmentonthe
P .
:2 0,1m
(2)
Itpermitsnotcommonlyworkouttheportionsof
evidence presented by power set
P . A basic
beliefassignment
m appeases:
0m
(3)
1
AP
mA
(4)
Belief function
B
el A for a set
A
is defined
asthesumofallBasicBeliefAssignmentofsubsetsof
A
defined and said that a part of faith
B
are
assigned,mustbeassignedtootherhypothesis,thatit
means:
|BB A
B
el A m B
(5)
The Dempster‐Shafer theory also defines the
plausibility
Pl A asthesumofalltheBasicBelief
Assignmentofsets
B
thatintersectsthesetof
A
:
|0BB A
Pl A m B
(6)
2 THEPROBLEM
Given that the total linear programming model of a
simplifiedversionoftheproblemofroutingthevessel
presentsanunacceptablesolutiontimesforatypical
daily planning process, taken a heuristic approach,
deciding on your hand. Author decided on this
approach for its implementation relatively
simple
calculation,aswellasitsrecordofgoodresultswith
similarproblemstothepresent[13].
There are several algorithms such as Dijkstraʹs
algorithm,whichisasinglesource‐singledestination
shortest path algorithm, the Bellman‐Ford algorithm
tosolvetheshortestpathalgorithmwithafreehand,
A*
algorithm solves the single pair shortest path
problems using a heuristic algorithm and Floyd
Warshall algorithm to find all pairs of Johnson‐
perturbation and the shortestpath algorithmto find
theshortestpathlocally.Geneticalgorithmsarealso
used to finding shortest path [1]. In this paper to
calculationwill
beusedDijkstraalgorithm.
2.1 Pathfindingalgorithm
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
citychanges
fromtimetotimeandthereareusuallya
461
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 directed graph G and a source vertexs in
Graph.Let‘sdenotethesetofallverticesinthegraph
GasV.Eachedgeofthegraphisanorderedpair
of
vertices(u,v)representingaconnectionfromvertexu
tovertexv.ThesetofalledgesisdenotedE.Weights
ofedgesaregivenbyaweightfunctionw:E→[0,
];
thereforew(u,v)isthenon‐negativecostofmoving
fromvertexu tovertexv.Thecostofanedgecanbe
thoughtofasthedistancebetweenthosetwovertices.
Thecostofapathbetweentwoverticesisthesumof
costs of the edges in
that path. For a given pair of
verticessandtinV,thealgorithmfindsthepathfrom
s to t with lowest cost (i.e. the shortest path). It can
alsobeusedforfindingcostsofshortestpathsfroma
singlevertexstoallotherverticesin
thegraph.[2]
2.2 Modelinput
Contributiontotheexample recordvesselproperties,
motionreportdataanddigitalclimateprognosisdata:
the example will join consumption curves, velocity
diminution curves, vessel class, ship wind and
weather sea borders, motion statement velocity,
maximal permitted speed, motion statement trace
data to contain waypoints, their
latitude and
longitude.Ontopofittodatarelatedtothemotionof
theshipitisindispensabletothespecificationofthe
surroundings. In particular significant is the
specification of the practicable routes between the
firstpointandthelastone.
2.3 Dijkstraʹsalgorithm
Forapublished
sourceapex(node)inthegraph,the
algorismdiscoversthewaywithsmallestcost(i.e.the
shortest path) among that vertex and every other
ones. It could also be used for discovering the
smallestcostwayfromonevertextoagoalvertexby
stoppagethealgorismisintendedbythe
smallestway
to the goal vertex. For instance, if the apexes of the
graphdescribethecitiesandtherearegivencostsof
flowing ways distances among pairs of points
combined immediately to the road, Dijkstraʹs
algorism can be used to discover the briefest route
amongonecityand
allothercities.Consequently,the
briefest path algorism is highly used in routing
protocolsinawebnetwork,inparticulartheIS‐ISand
OpenShortestPathFirst.
3 ROUTEPLANNINGWITHUNCERTAIN
INFORMATIONMODELINTRANSPORT
NETWORKS
Mainly in the road transportation area the most
importantdataforroutingis
thetrafficontheroads.
Itcanbeeasilycalculateintotwostates:congestionor
not congestion. Thus in this model the investigated
two hypotheses in Dempster‐Shafer theory are the
Congestion CO and
No Congestion NC ,
so
,CO NC and
,,,,PCONCCONC
characterizedbytheBasicBeliefAssignmentvaluesof
the focal elements
,,mCO mNC m
, where
m
expressestheuncertainty.
On the case of congestion on a pa rticular road
coststwiceconsideredbythepredeterminedcost.The
evolving traffic congestion can be caused by several
factors. These factors can be calculated as follows:
weather,trafficdensityandclosedtrack.Sothebasic
belief assignment functions are the
following:
1
m
:
bad weather,
2
m
: high vehicle density,
3
m
: closed
lane.
The mathematical theory of evidence deals with
functioncombininginformationcontainedintwosets
ofassignments,subjectiveexpertratings.Thisprocess
may be interpreted as a knowledge update.
Combiningsetsresultsinforming of new subsetsof
possible hypotheses with new va lues characterising
probability of specific options occurrence.
The
aforementioned process may continue as long as
provided with new propositions. This function is
known as Dempster’s rule of combination. If more
thanonefactorappearsonanedge, thenitispossible
to cumulate them based on the following formula,
where
A
is the investigated set,
B
,
C
are
elementsof
P
.
ThisequationisproposedbyDempster:
12
12
1
ABC
AB
mAmB
mC
mAmB
(7)
Combination rules specify how two mass
functions, say
1
m
and
2
m
, are fused into one
combinedbeliefmeasure
12 1 2
mmm
(weherelet
the binary operator
denote any rule for mass
functioncombination).Many combinationruleshave
been suggested (several are presented in [3]), and
below we briefly discuss the ones we use in this
study.
Foragivensourcevertex(node)inthegraph,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 of running paths edge distances between pairs
of cities connected directly to the road, Dijkstraʹs
algorithm can be used to find the shortest route
betweenonecityandallothercities.Asaresult,the
shortest path algorithm is widely used routing
protocolsina
network.
Short characteristic of Dijsktra algorithm [11]
presentedisinfigure2.
462
Figure2.Dijkstraalgorithm.
4 ROUTEPLANNINGALGORITHMWITH
UNCERTAININFORMATION
In the previous chapter, the decision of the relative
interval was simply because the lowest one was
worsethanthehighestvalueoftheother.Ifthereis
anoverlapbetweentheintervals,thenthedecisionis
not easy. When both endpoints of the
interval than
the end points of the other less: In this case, the
routingmethodmay choose fewervalues. However,
whenanintervalistheinnerpartofanotherinterval,
the decision is not clear. A possible choice is the
comparisonofthecenterpointsoftheintervals.The
election
rulesdependonthehumandecision:Theend
usercandevelopworst‐casedesign,oratbest,design
orotherdesignchoices[7].
So far it looked at the transportation planning
problemasastaticproblem.Ofcoursethisisinfact
notthecase.Uncertaintycanthrougheventssuchas
errors in the communication between automated
guided vehicles and the system maintained stay
reservations, break‐down of a mobile unit (engine
failure) or failures are caused (for example due to
traffic accidents) in the transport network.
Uncertainty can also be caused by a change in the
transportrequests.Forexample,
doesthearrivalofa
newtransportrequestacurrentplanunworkable.
Uncertainty and especially incidents can be dealt
with proactive or active. Proactive methods try to
create robust plans, while reactive methods of
incidents actually recover they occur. A typical
proactiveapproachistoinsertlimpinpla ns,sothat,
for example, delays have no consequences and new
demandscanbeeasilyinserted.Ifnothingunexpected
happenstheseplanstakemuchlongerthannecessary.
[15]
Figure3.Diagramofsearchingnewpaths.
For a given source vertex in the graph, the
algorithm finds the path with lowest cost between
thatvertexandeveryothervertex.Itcanalsobeused
forfindingtheshortestcostpathfromonevertextoa
destination vertex by stopping the algorithm is
determined by the shortest path
to the destination
node. For example, if the vertices of the graph
representthecityandarethecostsofrunningpaths
edge distances between pairs of cities connected
directlytotheroad,Dijkstraʹsalgorithmcanbeused
to find the shortest route between one city and all
other
cities.Asaresult,theshortestpathalgorithmis
widelyusedroutingprotocolsinanetwork.
The proposed scheme is shown in figure 3.
Provides an overview of the optimal path, the
removalofallfurtheredges[12].
Because of the uncertainty of the road network
after disasters, it is possible
that the chosen path is
blocked,although its reliabilityis very high and the
journey time is short. In such cases, one can do
nothingbutsetthepathisblocked.Soanotheroption
for the adjustability of the path is proposed. This
ensuresthatifthechosenpathis
blocked,wedonot
havetocircle.Thisproblemisnotsolvedinpresented
procedure.
When the assessment of the situation undergoes
solelyasubjectiveexpertrating,theresultsareonlyto
be obtained in form of linguistic variables. Theories
presentedshow[16]possibilityoftransformingsuch
valuesintofigureswith
useofthefuzzysetstheory,a
concept created by L.A. Zadeh in the sixties of the
20thcenturyanddevelopedeversince(mainlybyits
author), which increasingly intercedes in various
economic issues. According to Zadeh, the
aforementioned theory has not been sufficiently
employed for the purpose of detection
analysis of
marine units. A more extensive use of possibilities
offeredbythefuzzysetstheoryappearsasanecessity
for rational construction of new maritime traffic
monitoringsystems[7,8].
Afuzzynaturecanbeattributedtoeventswhich
may be interpreted in fuzzy manner, for instance,
inaccurateevaluationsofprecisely
specifieddistances
to any point. Subjective evaluations in categories:
near,far, very farmay be expressed withfuzzy sets
defined by expert opinions. Such understanding of
fuzzyeventsisnaturalandcommon.Introductionof
eventsdescribedbyfuzzysetsmoderatesthemanner
463
inwhichtheresultsofprocessingareused, expands
the versatility of such approach, as well as changes
the mode of perceiving the overall combining
procedure. Deduction of specific events involved in
theprocessofcombiningpalesintoinsignificance,as
obtaining information on related hypotheses is of
greaterinterest.Combining
evidenceoffuzzyvalues
bringsnewqualityintoknowledgeacquisitiondueto
the usage of combination results as a data base
capable of answering various questions. Other
possibilitiesofthemathematicaltheoryofevidencein
problemsof transportin navigation canbe found in
[6].
TheprincipleofconnectionDST
allowspeopleto
connecttwoindependentsourcesof evidence inone
or two basic probability assignments are defined on
thesameframe.Here, thetermʺindependentʺinthe
DST is not strictly defined. The word simply means
that a range of evidence shall be determined by a
varietyofmeans.
Figure5.Transformationofmultiplecombinedevidence.
Figure 5 shows that the combination of multiple
evidence can be converted into a double recursion
several combinations of evidence relates to the
propertiesofthecombinationrules,soitisconvenient
forpeopletoadda newsourceofevidencetotheold
systeminanarbitraryorder.
5 NUMERICAL
EXAMPLE
Thefigure6showsanexampleoftheunrealmaritime
restricted area. It consists of eight obstacles (in the
formofislands),21turningpointsand29edges.Each
edge is described by value of the distance between
twovertices.
AllconnectionsareshownintheFigure6.Number
of edge corresponds to the edge shown in Figure 6.
Each connection is between initial node and final
node. The distance between nodes describes a
dimensionless measurement of the distance between
thenodes.
For the purposes of demonstration and
calculations developed computer application [9]
which graphically created schema presented in the
article.Formiddle‐classcomputerallthecalculations
weredoneinlessthan150ms.Suchashortcalculation
timecanbeaprerequisiteforfurtherresearchintothe
searchforalternativepaths.
Result of the algorithm is a path with a length
equal1365.Thealgorithmindicatedthattheshortest
distancebetweenthevertexlabelled0and3leading
byedges:0,22,23,25,14,12,13.Theshortestpathis
presentedinTable2andinFigure7.
Figure6.Schemeoftrafficamongislands.
Figure7.Theshortestpath.
Table2.Descriptionofshortestpath
_______________________________________________
Numberof InitialFinal Distancebetween
edgesvertex vertex vertices
_______________________________________________
001295
22114176
231413225
251315293
141715107
121718139
13183130
_______________________________________________
Total1365
_______________________________________________
Selecting one of several paths is a multi‐criteria
problem.Conventionalmulti‐criteriadecisionmaking
(MCDM) techniques were largely non‐spatial. Use
medium or cumulative effects that are considered
appropriate for the entire area into account. In this
case, subjective approach is proposed to solve the
problem. Based on
expert opinion, it is possible to
464
submit the results and select the appropriate
transitionpath. Itseemsthat anappropriate toolfor
thismaybeDempster‐Shafertheory.Dempster‐Shafer
theory (DST) is a promising method to deal with
certain problems in data fusion and combination of
evidence. Based on statistical techniques for data
classification, it
is used when the evidence is not
sufficienttoassignaprobabilityofindividualevents
and declares that are mutually exclusive. Also, both
inputandoutputmaynotbeaccurateanddefinedby
sets. DST concept is relatively simple, and the
techniqueiseasilyextensible.Inthecaseofmaritime
transport, as an international business with a high
risk,newevidencewillappearandbecomeavailable
once the war, diplomatic events or other hazards.
DST‐basedmodel,whichallowsincrementaladdition
of knowledge, can satisfy the needs of those
conditions. Compared with Bayesian probability
theory time zone avoids the necessity of
assigning
prior probability, and provides intuitive tools to
manageuncertainknowledge.
6 CONCLUSIONS
The Dijkstra algorithm is well known. It was first
published half a century ago. To this day, finding
connectionsbetweenverticesisused.Butnotalways
theshortestpathisthebest.Itistoconsidervarious
criteria. This paper is an introduction to further
research.
Shortestpathproblemswidelyexistinrealworld
applications. The paper presents a model to be
considered and an algorithm for routing in road
networkofuncertaintyofstatusinformationofroads,
costfactorsandtheiruncertainty.Inpresentedmodel
uncertaintyhave
theprobabilityvaluesusingdefined
probability of at least and maximum values using
Dempster‐Shafer theory. Decision rules can be
defined for nodes by the end user. The calculations
arebasedonbasic beliefassignmentvalues.Resultsof
presented paper can be used for travel decisions, in
whichthedecision
isabinary,crispvalues,intervals
andfuzzynumbers.
Thispaperexplainedtheproblemofshortestpath
problemwithcrispandfuzzyarclengthresultingin
extendingtheDijkstraalgorithm.The method which
is proposed under fuzzy arc lengths to find the
shortestpathisbased onthegradedmeanintegration
representation of fuzzy numbers. A numerical
example was used to illustrate the efficiency of the
proposed method. As far as real applications are
concerned in the field of transportation systems,
logistics management, and many other network
optimization problem that can be formulated as
shortest path problem this method can be
applied.
Throughanexamplethispaperalsotriedtosimplify
theapplicationofroutingplanninginourgenerallife
whichbasicallygavetheshortestpathbetweensome
important cities of the world. At the same time,the
uncertaintyin theshortest path is not limitedto the
geometric distance this is also
shown by this paper.
For example, even if the geometric distance is fixed
duetotheweatherandotherunexpectedfactors,the
travel time from one city to another city may be
representedasafuzzyvariable.
REFERENCES
[1]Bagheri H., Ghassemi H., Dehghanian A.: Optimizing
theSeakeepingPerformance of Ship Hull Forms Using
GeneticAlgorithm.TransNav,theInternationalJournal
onMarineNavigationandSafetyofSeaTransportation,
Vol.8,No.1,pp.4957(2014)
[2]Boominathan P, Kanchan A. Routing Planning As An
Application Of Graph Theory. International
Journal of
Scientific&TechnologyResearch.Vol.3(6),61‐66,2014
[3]Bostrom, H.: On evidential combination rules for
ensemble classifiers. 11th International Conference on
InformationFusion,IEEE(2008)
[4]Dijkstra, E. W.: A note on two problems in connection
with graphs, Numerische Mathematik 1, pp. 269‐271
(1959)
[5]
Dempster,A.P.:AgeneralizationofBayesianinference.
JournaloftheRoyal StatisticalSociety,SeriesB,Vol.30,
pp.205‐247(1968)
[6]Filipowicz,W.:FuzzyReasoningAlgorithmsforPosition
Fixing.PomiaryAu‐tomatykaKontrola2010(12),s.1491‐
1494(2010)
[7]Szucs G.ʺRoute Planning with Uncertain Information
using Dempster‐Shafer
theoryʺ, International
Conference on Management and Service Science,
09/2009
[8]Neumann T.: Multisensor Data Fusion in the Decision
Process on the Bridge of the Vessel. TransNav, the
International Journal on Marine Navigation and Safety
ofSeaTransportation,Vol.2,No.1,pp.85‐89,2008
[9]Neumann,T.:A
SimulationEnvironmentforModelling
and Analysis of the Distribution of Shore Observatory
Stations‐Preliminary Results. TransNav, the
International Journal on Marine Navigation and Safety
ofSeaTransportation,Vol.5,No.4,pp.555‐560(2011)
[10]Neumann,T.:MethodofPathSelectionintheGraph‐
Case Study. TransNav, the International Journal
on
Marine Navigation and Safety of Sea Transportation,
Vol.8,No.4,pp.557‐562(2014)
[11]Neumann,T.:Goodchoiceoftransitvesselrouteusing
Dempster‐Shafer Theory. International Siberian
ConferenceonControlandCommunications(SIBCON),
IEEE(2015)
[12]Neumann, T.: Parameters in the softwares model to
choosea
betterrouteinthemarinetraffic.International
JournalofMachineIntelligence,454‐457(2015)
[13]Neumann, T.: The Shortest Path Problem with
Uncertain Information in Transport Networks,
ChallengeofTransportTelematics,Springer,(2016)
[14]ShaferG.:Amathematicaltheoryofevidence.Princeton
UniversityPress(1976)
[15]Zutt J., van Gemund A.,
de Weerdt M., Witteveen C.:
Dealing with Uncertainty in Operational Transport
Planning.IntelligentInfrastructures,IntelligentSystems,
Control and 349 Automation: Science and Engineering
42(2010)
[16]ZadehL.A.:Theconceptofalinguisticvariableandits
application to approximate reasoning. Information
Sciences8,199‐249(1975)
