557
1
INTRODUCTION
Rapidandaccuratecalculationoftheestimatedtime
ofarrivalattheportofdestinationoftheshipatsea,
is of great importance in many areas of the ocean
shipping industry. For example, the route and
scheduleofshipsonadaytoday,itisimportantto
knowwhenthe ship reachedthe port of destination
andtobeavailablefornewloads.Estimatedtimeof
arrivalcanalsobeimportantintheplanningofport
operations. Give a reliable estimated time of arrival
forshipsenteringtheport,planningportoperations,
such as work assignments, loading/unloading
equipment
and harbours for ships can be more
efficientlydone.
The traditional way is to base the estimate of
estimatedtimeofarrivalonships.However,thenew
technology of satellite position reporting combined
with electronic map allows users to land to check
weather or update the masterʹs estimated time of
arrival at regular intervals, not interfering with the
crewoftheshipatallhours.
The paper presents an efficient algorithm for
determiningtheestimatedtimeofarrivalinportthe
ship is at sea. The algorithm is implemented in a
decisionsupportsysteminplanningtheoperationof
ships,
one of which is installedand used by several
owners. By calculating the distance of the route
between the ship and the port of destination,
estimatedtimeofarrivalcanbeestimatedbydividing
the distance by the speed sailing. Calculating the
distancebetweentheshipandtheportofdestination
may be considered to determine the shortest path
between two points in the presence of polygonal
obstacles,whereonepointcorrespondstothevessel
andtheotherendtotheportofdestination.Sections
definingpolygonsareobstaclescoast.Estimatedtime
of arrival accuracy can be improved by defining
special
network structures in areas with limited
speed,orarewaitingforthepilots[3].
Thevehicle routingproblem liesin the designof
optimalroutesforafleetofvehicles,usuallyinorder
tominimizeoperatingcostsorthenumberofvehicles
used. Several variations of this problem has been
extensively
studied in the literature optimization as
efficient routing of vehicles have a great impact on
logisticscosts[8].
Method of Path Selection
in the Graph
- Case Study
T.Neumann
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:ThispaperpresentsadifferentperspectiveontheDijkstraalgorithm.Inthispaperalgorithmwill
beusedinthefurtheranalysistofindadditionalpathsbetweennodesinthemaritimesector.Inmanycases,the
bestsolutionforasingle criterionisnotsufficient.Iwouldbe the search for
moreeffective solutions of the
startingpointtouseforsubsequentanalysisordecisionmakingbythecaptainoftheship.Usingcutting‐edge
thinkingmechanisms,itispossibletocreateadecisionsupportsystembasedonknownDijkstraʹsalgorithm.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 8
Number 4
December 2014
DOI:10.12716/1001.08.04.10
558
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,as
wellasitsrecordofgoodresultswith
similarproblemstothepresent.
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 shortest path algorithm to find
theshortestpathlocally.Geneticalgorithmsarealso
used to finding shortest path [1]. In this paper to
calculationwillbeusedDijkstraalgorithm.
2.1
Modelinput
Inputs to the model record ship characteristics,
movement report data and numerical weather
predictiondata:themodelwillintegrateconsumption
curves,speedreductioncurves,shipclass,shipwind
and weather sea borders, movement report speed,
maximumallowedspeed,movementreporttracedata
to include waypoints, latitude and longitude. In
additionto
datarelatedtothemovementofthevessel
itisnecessarytothedescriptionoftheenvironment.
Especiallyimportantisthedescriptionofthepossible
routesbetweenthepointʹsstartandend.
2.2
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
stoppingthealgorithmis
determinedbytheshortest
path to the destination node. For example, if the
vertices of the graph represent the city and are the
costsof running paths edge distances between pairs
of cities connected directly to the road, Dijkstraʹs
algorithm can be used to find the shortest route
between
onecityandallothercities.Asaresult,the
shortest path algorithm is widely used routing
protocols in a network, in particular the IS‐IS and
OpenShortestPathFirst.
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
Weightsof edges are given 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.
2.3
Modeloutput
It is determined based on the input data and the
shortest time path by Dijkstraʹs algorithm, is
calculated:range,bearing,andtime(hours)fortransit
betweeneachwaypoint, total distance and duration,
network least timeʺshortestʺ path in latitude /
longitudepositions,thefuel consumptionfornetwork
path,costof
fuel.
Thecalculationdeterminesthefeasibilityofarrival
timegivenhowmanyhoursoftimeatthebeginning
and/orlate,theshipcanreachitsdestination.Ifthe
arrivaltimeofanetworkpathbeyondtheallowable
range of time of arrival of the model calculates the
recommended
increaseinspeedbasedonthedistance
ofatleastduring the pathmodel and the latest and
earliest times, depending on the case. The user can
then enter the recommended speed and run the
model.Ifyouneedtoincreasethespeedgreaterthan
themaximumallowablespeed,andthen
promptthe
user model that other options should be considered
redirectionpath.Dependingonthepointontheaxis
ofthetransittime,theseoptionsare:delayintheport
speedreductionwithoutchangingthetrackorstorm
evasion.
2.4
Proposed touse
Asindicatedabove,thealgorithmiswellknownand
widely used. Finding the shortest path between two
verticesingraphsisnotdifficult.Butnotalwaysthe
shortestpathisthebest.Itisproposedtofastsearch
method inferior alternatives. In suchsituation,
decisionmakercanchooseoneofthe
alternativesand
takealltheconsequences.
After finding the shortest path is proposed to
remove from the graph piece belonging to the
foundedpath.Disposalshouldbecarriedoutaslong
asthereisalotofsegmentsinthefoundedpath.For
eachnewgraphisnecessarytofind
theshortestpath.
Founded new path should be saved to an array of
solutions.
The proposed scheme is shown in figure 2.
Provides an overview of the optimal path, the
removalofallfurtheredges.
Resulting array can contain many of the same
tracks.It isthereforeremovedfromthesame
tracks.
Ofcourse,suchremovalisnotaproblem.
559
Firstedgeofoptimalpath
Nextedgeof
optimalpath?
Removeedgefromarrayofedges
Findnewshortestpath
Removeduplicatepaths
Y
N
Figure2.Diagramofsearchingnewpaths
3 NUMERICALEXAMPLE
Thefigure1showsanexampleoftheunrealmaritime
restricted area. It consists of eight obstacles (in the
formofislands),21turningpointsand29edges.Each
edge is described by value of the distance between
twovertices.
AllconnectionsareshownintheTable1.Number
of edge corresponds to the edge shown in Figure 1.
Each connection is between initial node and final
node. The distance between nodes describes a
dimensionless measurement of the distance between
thenodes.
Figure1.Schemeoftrafficamongislands
Table1.Tableofalledges
_______________________________________________
Numberof Initial Final Distancebetween
edgesvertex vertex thevertices
_______________________________________________
001295
104257
245415
356215
449207
591098
610773
776183
878160
9108187
10816203
11
1617181
121718139
13183130
141715107
151519148
161920183
17911168
18912137
19111210
201112102
211213212
221
14176
231413225
241319216
251315293
26142452
27220343
28203362
_______________________________________________
Result of the algorithm is a path with a length
equal1365.Thealgorithmindicatedthattheshortest
distancebetweenthevertexlabelled0and3leading
byedges:0,22,23,25,14,12,13.Theshortestpathis
presentedinTable2andinFigure3.
Table2.Descriptionofshortestpath
_______________________________________________
Numberof Initial Final Distancebetween
edgesvertex vertex thevertices
_______________________________________________
001295
22114176
231413225
251315293
141715107
121718139
13183130
_______________________________________________
Total1365
_______________________________________________
Figure3.Shortestpath
560
Aneasywaytofindanother quickwayfromthe
source to the target is to modify the optimal path,
found a particular method. The article proposes to
remove one edge. The cycle was repeated for each
edgeoftheoptimalpath.Inthiswaycalculatedtwo
other paths 1,4,5,9,10,11,12,13
and 0,22,23,24,16,28:.
DetaileddataareshownintheFiguresandtables.
Figure4.Secondpath
Table3.Descriptionofsecondpath
_______________________________________________
Numberof Initial Final Distancebetween
edgesvertex vertex thevertices
_______________________________________________
104257
449207
591098
9108187
10816203
111617181
121718139
13183130
_______________________________________________
Total1402
_______________________________________________
Figure5.Thirdpath
Table4.Descriptionofthirdpath
_______________________________________________
Numberof Initial Final Distancebetween
edgesvertex vertex thevertices
_______________________________________________
001 295
22114 176
231413 225
241319 216
161920 183
28203 362
_______________________________________________
Total1457
_______________________________________________
For the purposes of demonstration and
calculations developed computer application [6]
which graphically created schema presented in the
article.Formiddle‐classcomputerallthecalculations
weredoneinlessthan150ms.Suchashortcalculation
timecanbeaprerequisiteforfurtherresearchintothe
searchforalternativepaths.
Theresultsrequirefurthercalculations.According
totheauthorto be in the discussiontoconsider not
only the dimensionless values describing the edges,
but also values such as time, cost, security etc. It is
necessary to use the mechanism of multiple‐choice
decisionordatafusion[4,5].
In a
similar way for the selected paths other
parameters were calculated. They relate to the
average time needed for the transition path, the
numberofindirectverticesandthecalculateofsafety
factor.Thedataaresummarizedintable5.
Table5.Summaryofresults
_______________________________________________
Path Distance NumberofAveragetime
indirectvertices
_______________________________________________
Path1 13656220
Path2 14027260
Path3 14575200
_______________________________________________
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
submit the results and select the appropriate
transitionpath. It seems thatanappropriate tool for
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.Inthe
caseofmaritime
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.
4
ANEXPERTSYSTEMFORMULTI‐CRITERIA
DECISIONMAKINGUSINGDEMPSTER
SHAFERTHEORY
Dempster‐Shafer Theory is a generalization of the
Bayesian theory of subjective probability. Basic
functions of degrees of belief of faith (or trust, or
trust) to a single question about the probabilities
relatedquestion.Degreesofbeliefitselfmay
ormay
561
not have the mathematicalproperties of probability;
how they differ depending on how much these two
questions are related. In other words, it is a way of
representing epistemic plausibilities but it can give
theanswersthatarecontrarytothoseachievedusing
probabilitytheory.
There are two main functions
in DST: the belief
functionandplausibilityfunction.
Thebelieffunctionandtheplausiblefunctionare
twonon‐additiveevidentialmeasuresoftheDST,and
they can be calculated from the BPA. For any set
A, B
,thebelieffunctionisdefinedas:
BA
Bel A m(B)
Bel(A) represents the minimum belief, which
summarizes all reason to believe in A with the
availableknowledge.WiththedefinitionofBPA,the
functionsatisfies
Bel 0 and
Bel 1 .
Theplausiblefunctionisdefinedas:
BA
Pl A m(B)
Plrepresentsthemaximumbelief,whichsummarizes
all reason not to reject in A with the available
knowledge.Thefunctionalsosatisfies
Pl 0
and
Pl 1 .
According to the definition above, one of the
relationships between the belief function and the
plausible function is
Bel A Pl(A)
, and it is
possible to describe uncertainty of evidential
measures by the lower and upper bounds of an
interval
BelA,PlA
.
TheprincipleofconnectionDSTallowspeopleto
connecttwoindependent sources of evidence in one
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.
Combination
Rule
Bel
Bel
Bel
Bel
Bel
Bel
Combination
Rule
Bel
Bel
Bel
Combination
Rule
Bel
Combination
Rule
Bel
Combination
Rule
Bel
Figure6.Transformationofmultiplecombinedevidence
Figure 2 shows that the combination of multiple
evidence can be converted into a double recursion
several combinations of evidence relates to the
propertiesofthecombinationrules,soitisconvenient
forpeopletoaddanewsourceofevidencetotheold
systeminanarbitraryorder.
In the
shown example it is possible to evaluate
routesinthefollowingway.Oneoftheexpertssaid,
thatsaidthatthebestoftheroutesisPath1,because
it is shortest. He assesses it to 40%. Also takes into
consideration the path of a second, but I still
remember
thatitistheshortestP1.Thus,selectinga
P1orP2isestimatedat20%.Allcasesareshownin
Table6.
Table6.Summaryofexpertsreviews
_______________________________________________
CaseExpert1 Expert2 Expert3
_______________________________________________
P10,40 0,20 0,15
P1orP20,20 0,10 0,20
P1orP30,20 0,05
P20,10 0,15 0,15
P30,05 0,15 0,25
P1orP2orP3 0,25 0,20 0,20
_______________________________________________
Thedatastoredinthetablemaybeanalysedusing
the DST which will be the subject of further
consideration.
5
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.
In this study, we
developed a model of the ship
routing network that solves problems optimal path
using a modified version of Dijkstraʹs shortest path
algorithm and the basic function of the reaction
vessel.Wehaveestablishedfidelitymodelsbytesting.
Asyoucansee,themodelavoidstheadverseweather
conditions and
solves the path of least time to your
destination.Itcalculatestheusefultime,distance,fuel
consumption and metrics to quantify routing
decisions.Themodelalsoshowsthatmanualrouting
techniquesinvolvingmultiplecalculationsandgraph
plottingcanbeautomatedandsolutionsgeneratedin
milliseconds.Wehaveidentifiedhowtheresults
can
beusedbyemployeesoftheshiprouting,tohelpin
the analysis of alternatives and the routing decision
supportship. The performance of the model against
historical cases validates skills model and gives
insightintotheimprovementsthatcanbemadeinthe
future.
REFERENCES
[1]Bagheri H., Ghassemi H., Dehghanian A., 2014:
Optimizing the Seakeeping Performance of Ship Hull
Forms Using Genetic Algorithm. TransNav, the
International Journal on Marine Navigation and Safety
ofSeaTransportation,Vol.8,No.1,pp.49‐57
[2]Dijkstra, E.W., 1959: A note on two problems in
connexion with graphs.
Numerische Mathematik. 1,
269–271.
562
[3]Fagerholt,K., Heimdal,S.,Loktu,A.,2000.Shortestpath
in the presence of obstacles: an application to ocean
shipping.JournaloftheOperationalResearchSociety51,
683–688.
[4]Gopika,N.A.,Deeoa,S.2013.Asurveyonoptimalroute
queries for road networks, International Journal of
ResearchinEngineeringandTechnology,
02,12,447‐450
[5]Neumann T., 2008: Multisensor Data Fusion in the
DecisionProcessontheBridgeoftheVessel.TransNav,
the International Journal on Marine Navigation and
SafetyofSeaTransportation,Vol.2,No.1,pp.85‐89
[6]Neumann T., 2011:A Simulation Environment for
Modelling and
Analysis of the Distribution of Shore
Observatory Stations‐Preliminary Results.TransNav,
the International Journal on Marine Navigation and
SafetyofSeaTransportation,Vol.5,No.4,pp.555‐560
[7]Neumann T., 2014: The Shortest Not Necessarily the
Best. Other Path on the Basis of the Optimal
Path.International Journal of
Research in Engineering
andTechnology.Vol3,No.10,pp.322‐326.
[8]Romeroa,G.,Duran,G.,Marenco,J.Weintraub,A.2013.
An approach for efficient ship routing. International
TransactionsinOperationalResearch00,1‐28
