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.Usingcuttingedge
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,whichisasinglesourcesingledestination
shortest path algorithm, the BellmanFord 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 ISIS 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 suchsituation,
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
edgesvertex vertex thevertices
_______________________________________________
001295
104257
245415
356215
449207
591098
610773
776183
878160
9108187
10816203
11
1617181
121718139
13183130
141715107
151519148
161920183
17911168
18912137
19111210
201112102
211213212
221
14176
231413225
241319216
251315293
26142452
27220343
28203362
_______________________________________________
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
edgesvertex vertex thevertices
_______________________________________________
001295
22114176
231413225
251315293
141715107
121718139
13183130
_______________________________________________
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
edgesvertex