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.