`

`

`

`Abstract
`
`Abstract.
`
`In this thesis, a solution is presented for automating a part of the voyage planning process in
`marine navigation, namely route planning. Another, better term, for route planning is route
`selection, since route planning is about selecting an optimal route. The presented principle is a
`network-based route finding solution under multiple criteria.
`
`The voyage planning process is first analysed. A model presented by Sabelis [Sabelis, 1999(ii)],
`provides a good overview on the different phases of voyage planning. Also, it is made clear,
`that voyage planning is a time-consuming and laborious process. Automating the process can
`best be done by first automating the different phases. In that perspective, a principle is
`developed for automating the route planning phase.
`
`Existing routes at sea are historically formed by depth and land contours, positions of
`harbours and international and national regulations. When analysing these, it shows that a
`network is already formed by the existing routes.
`
`The components of the route-network and the structure of the network are meant to provide
`as many options as possible with appropriate coverage of the world. The route-network
`should be fitted into the ECDIS data structure, since ECDIS is the most suitable platform for
`the automation of route planning. Therefore, some recommendations are made to create new
`objects in S-57, the IHO transfer standard for digital hydrographic data. In order to test the
`principle, a chain-node data structure is used, mainly because of the simplicity of the
`structure.
`
`1he information that is required during the route planning phase is divided into the sailing
`order and the route characteristics. The sailing order contains the ship's characteristics and
`the mission characteristics. The route characteristics can be divided into dimensions,
`regulations and restrictions, navigational aspects and remaining aspects. The information
`reqnirements heavily depend on the classification (ocean, coastal or confined) of a passage.
`There are different sources of information but in order to automate the voyage planning
`process, all information should be available in ECDIS via ENCs or other data bases.
`
`The route characteristics influence the decision process in terms of denial and preference.
`The information that denies passage through a route-segment is implemented as filter criteria
`in the filter algorithm; the information that influences the phase in terms of preference is
`implemented as criteria of preference in the decision algorithm.
`
`The sequence of the presented algorithm is to firstly filter the unnavigable segments; then to
`calculate the shortest possible route; thirdly all possible routes within an interval are
`calculated, whereafter the route-alternatives are compared by means of the criteria of
`preference.
`
`1he presented principle seems to give the desired results, although more tests and new and
`reviewed criteria are required for optimisation of the algorithm. Also more research is needed
`in order to provide the perfect setting of weights.
`
`iii
`
`3
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Chapter II
`
`Voyage planning in marine navigation
`
`utilisation of weather routeing software, for example, can reduce the fuel consumption for an
`
`ocean passage.
`
`11.2 A model of the voyage planning-process.
`
`International regulations on voyage planning.
`II.2.1
`In order to provide a robust basis for automated route planning, I should use some sort of
`
`model of the process. A model provides a logical structure of voyage planning. In the
`
`aforementioned guide, the IMO distinguishes four stages in the planning and achievement of
`
`a safe passage, namely Appraisal, Planning, Execution and Monitoring. [IMO, 1978] Appraisal
`
`deals with the gathering of all information from charts and publications (e.g. sailing
`
`directions, Notices to Mariners, radio aids to navigation, etcetera). During the planning stage,
`
`a detailed plan of the passage is prepared, taking all gathered information into account. The
`
`execution stage should provide the navigator with all the tactics that will be used during the
`
`execution of the plan. The last stage, monitoring the ship's progress along the planned track,
`
`is then essential for the safe conduct of the passage.
`
`In my opinion, the IM0 omits to distinguish the difference between the choice of the
`
`trajectory and the detailed planning of a passage. The IMO deals directly with the (detailed)
`
`planning of a passage. This creates an illogical structure in the planning process. Sabelis
`
`[Sabelis, 1999(ii)] described the process in a more logical way and therefore I will base my
`
`research on his model of voyage planning.
`
`II.2.2 The voyage planning-process according to Sabelis.
`Sabelis divided the voyage planning-process into three cycles, Route Planning, Navigation
`
`Planning and Watch Preparation. [Sabelis, 1999(ii)] Going through these cycles iteratively, every
`
`cycle results in a more detailed outcome (directives), starting with the sailing order and finally
`
`resulting in the navigation scenario. Furthermore, all cycles exist of four steps, namely
`
`Analysis, Synthesis, Decision and Direction (See figure II-1). All cycles and steps, including
`
`the directives are briefly explained below, in order to get a good view on the marine voyage
`
`planning-process.
`
`The sailing order is the start of the whole voyage planning-process. All the demands are laid
`
`down in this directive, initiating the first cycle. During the first cycle, Route Planning, the best
`
`route has to be selected. 1 The outcome is the .Route Plan, which is a description of the route
`
`1 Perhaps a better term is Route-selection. In the further thesis these two terms are used as synonyms.
`
`7
`
`12
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Chapter II
`
`Voyage planning in marine navigation
`
`Spatial data is typically of vector, matrix or raster format (see paragraph III.4.1.), whereby
`
`vector is the most intelligent. Data is captured in a number of different ways. Direct data
`
`capture consists of Aerial photography, remote sensing, satellite surveying and total station
`
`survey. Scanning a paper map is a typical example of indirect data capture. Incorporation of
`
`existing data means the use of corporate data, postcoded data and digital maps. The data
`
`management system provides storage, integration and conversion of data. Map overlay is an
`
`important feature of GIS. The data management system can overlay data sets, once they are
`
`geo-referenced. This overlay provides both visual and mathematical comparison between
`
`different data sets.
`
`Furthermore, spatial analysis tools are developed, also called spatial queries. The most
`
`important types of spatial query are point-in-polygon queries, zone queries, vacant place
`
`queries, distance and buffer zone queries and path queries. [Laurini, 1992; p. 536] A point-in(cid:173)
`
`polygon query involves the search for the objects, into which input co-ordinates 'falls'. A
`
`' zone query determines which objects belong to the zone we are interested in. Vacant place
`
`queries provide vacant places within a certain area. With distance and buffer zone queries, the
`
`GIS can calculate distances and can retrieve all objects lying at a certain distance from a
`
`certain zone or object. Path queries provide path finding. There are various kinds of path
`
`finding that can be distinguished. First, there are network-based path queries, such as the
`
`search for the shortest path in a graph, the selection of a path in a hierarchized graph, and the
`
`travelling salesman problem. Secondly, it is possible to find paths within polygons. Finally,
`
`least-cost surface path finding based on matrix or raster formatted data is another type of
`
`path query, as provided in GIS.
`
`All kinds of queries could be very useful during the route planning phase. Various kinds of
`
`data are already available in the electronic charts and databases. Point in polygon queries
`
`could provide information on the passage of a routeing system; zone queries offers us the
`
`opportunity of searching for objects such as buoys and shallows within certain boundaries;
`
`distance and buffer zone queries provide distances to other objects and the vicinity of
`
`navigational dangers.
`
`Finally, GIS provides the graphical display of information. Overlay techniques of different
`
`kinds of (selected) information, provides an optimal view on various situations. This
`
`encourages comparison between sets of data, stages of development and so on. Typical
`
`employment of GIS is in a variety of fields of study, such as town and country planning,
`
`emergency services (e.g. police), farming, forestry and environmental protection.
`
`14
`
`19
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Chapter III
`
`Route-network analysis
`
`The route-point record is filled with a position (most likely in latitude and longitude), a couple
`
`of fields with information about harbours (including a field stating 'is it a harbour') and a field
`
`that contains the identification of any area it belongs to. 17 The first field contains the name or
`
`'identifier' of the node.
`
`The route-lane record contains two fields
`
`to define the nodes (with the use of the
`
`unambiguous identifier) a lane is terminated by. One field is reserved for the traffic regulation
`
`(is the lane two-way or one-way). Then the rest of the fields are reserved for the attributes.
`
`The first field contains the lane-identifier again. The route-area record contains one field with
`
`its identifier and. the rest of the fields are reserved for attributes. Appendix E shows the final
`
`chain-node data structure that is used for the test-environment.
`
`17 This is done because of the limitations of the chain-node structure. In theory, an area can be defined by an
`infinite number of nodes, but leaving an infinite number of fields availab~e in the table-type record structure
`would be impossible. Therefore, an area is defined in a contrary way in comparison to the datamodel.
`
`37
`
`42
`
`

`

`

`

`Chapter IV
`
`Route planning information requirements
`
`and port of destination, or better, position of departure and position of destination. If
`
`necessary, some extra information can be added on intermediate positions/ ports,
`
`exercise areas that have to be passed and required passages and anchorage areas. The
`
`structure of the route-network implies that some extra requirements on the use of
`
`network-regions should be stated.18
`
`2. Time characteristics. Time characteristics are a very important part of the sailing order.
`
`They state the conditions that influence the time-distance problem (see paragraph V.1.2.).
`
`Time characteristics consist of time of departure (I'oD) and time of arrival (ToA) for the
`
`positions ?f departure and destination and for intermediate positions, areas and passages.
`
`Important other statements which set the time margins are for example 'on-time', 'in(cid:173)
`
`time', 'not later than' and 'not sooner than'; also, 'during daytime' or 'during night-time'
`
`can be stated for some passages. Obviously, time requirements and speed requirements
`
`are very closely related to each other.
`
`3. Task characteristics. Task characteristics provide extra information that is due to
`
`operational conditions and demands. For example, the type of operation of a navy vessel
`
`influences speed, time and weather requirements and manoeuvrability (e.g. mine-hunting,
`
`anti-submarine warfare and helicopter operations). Obviously, the same differences can
`
`be distinguished between merchant vessels and fishery or offshore operations. On the
`
`other hand, passenger ships and ships with embarked troops will state some weather
`
`requirements to limit ship's movement. Another type of task requirements has to do with
`
`security and risk. Security demands consists of requirements on behaviour in war zones,
`
`prohibited zones, territorial waters and danger areas. Risk demands state the limitations
`
`on acceptable damage risks, piracy risks and delay risks.
`
`4. Navigator's demands. Navigator's demands consist of all sorts of demands that can also
`
`be stated in the previous types of mission characteristics. Furthermore, some typical
`
`navigation based requirements are set by the navigator. Examples are requirements on aids
`
`to navigation, weather and behaviour during the conduct of passages, and preference
`
`statements concerning the operational characteristics of passages.
`
`18 The network is divided in network-regions in order to decrease the amount of data that has to be searched
`during the computing process. The navigator can appoint regions that have to be used and, on the contrary, that
`should be avoided.
`
`39
`
`44
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Chapter VII
`
`Conclusions and recommendations
`
`options are properly filtered from the data set. The characteristics that were not selected for
`
`the test environment can be considered to be implemented in the same way as those that
`
`were selected. Further research should provide some more and more robust criteria and a set
`
`of corresponding weights that fulfil the needs in as many different cases as possible.
`
`Although the route planning tool, in the form suggested in this research, provides reasonable
`
`solutions for route selection, more research is needed on criteria and weights. As I proceeded
`
`in my research, my opinion altered. Perhaps a quicker solution to automate voyage planning is
`
`the use of a data base-based tool (see paragraph II.4). Many ships operate in limited areas, so
`
`that used routes already or, better, tracks could be used over and over again (every time
`
`checking the route on new, updated, information). When a network is made from old leg and
`
`way-points, from which the details are already known, the use of the Dijkstra algorithm for
`
`shortest paths, could provide an optimised solution. The advantage of this principle is that
`
`the route selection phase is, more or less, already complete.
`
`However, when the voyage planning process is automated entirely, the network-based
`
`solution as presented here, is the best option. The outline of navigable waters directly limits
`
`the region within which the navigation planning-process can be executed. Legs and way(cid:173)
`
`points can be positioned automatically, for example using a terrain model-based path finding
`
`algorithm. Dangerous obstacles and shallows can be marked by a buffer, providing safety
`
`limits. Of course, these ideas can be researched in the future.
`
`VII.2 Recommendations.
`
`In the previous paragraph, it is shown that all the questions are answered and the objectives
`
`are achieved. Also, some arguments for further research on automating voyage planning were
`
`mentioned. The following recommendations can be formulated:
`
`1. A more thorough research should be executed on the formulation and definition of the
`
`criteria of preference. Obviously, not all the characteristics were part of the test
`
`environment. The implementation of the other characteristics implies the use of
`
`corresponding criteria. The presented criteria should be reviewed, in order to ensure a
`
`robust best route solution.
`
`2. As the criteria are reviewed and new criteria are implemented, the set of weights should
`
`also be reviewed. The new criteria and weights should then be tested in a couple of areas,
`
`90
`
`95
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Appendices
`
`Appendix C: Cargo classification and ice classification.
`1. Cargo classification.
`
`In order to determine the critical cargo classes, more detail is required on this subject.
`
`Therefore, international legislation (MARPOL 73/78) was examined, as well as some copies
`
`of Sailing Directions. The conclusion is that most cargo restrictive measures are based on the
`
`categorisation as employed in MARPOL 73/78. The most important categories are:
`•
`•
`
`Noxious liquid substances in bulk (petroleum chemicals, vegetable oils etcetera) ill the
`
`Oil and gas [IMO, 1978(ii); annex I]
`
`categories:
`
`A. major hazard if discharged in sea for human and marine environment (stringent anti(cid:173)
`
`pollution measures needed).
`
`B. hazard if discharged in sea for human and marine environment (special anti-pollution
`
`measures needed).
`
`C. minor hazard if discharged ill sea for human and marille environment (special
`
`operation conditions needed).
`
`D. recognisable hazard if discharged in sea for human and marine environment (some
`
`attention in operations needed).
`
`For other classes of cargo, no restrictions were found, therefore no further classes need to be
`
`input in the sailing order and passage characteristics. 66
`
`2.
`
`Ice classification.
`
`As explained in paragraph IV.1.2, different formats, terms and procedures in ice condition
`
`reports and ice classification are issued by several authorities. Two examples are the Canadian
`
`Arctic regulations and the Finnish-Swedish ice class regulations. The Norwegian classification
`
`bureau Det Norske Veritas operate classification rules that meet both the ice regulation
`
`systems. The following most important classes can be distinguished [DNV, 2000]:
`•
`
`Ice-1A *. A vessel with Ice-1A * may operate in channels prepared by icebreakers and/ or
`
`in open waters with smaller ice flows. This vessel can cope with extreme ice conditions,
`
`where ice floes of thickness 1.0m are anticipated.
`
`•
`
`Ice-1A. A vessel with Ice-1A may operate in channels prepared by icebreakers and/ or in
`
`open waters with smaller ice flows. This vessel can cope with severe ice conditions, where
`
`ice floes of thickness 0.8m are anticipated.
`
`66 With reservations. It is very possible that there are restrictions made on other cargo classes, since only a
`couple of situations are studied.
`
`106
`
`111
`
`

`

`

`

`

`

`

`

`

`

`the segment. These values are 'none', 'GNSS', 'Loran-C', 'Visual/ radar positioning'69
`
`,
`
`'GNSS and Loran-C', 'GNSS and visual/radar', 'Loran-C and visual/radar' and 'all
`
`available'.
`
`Appendices
`
`Ice conditions. The attribute 'ice condition' states the ice conditions of the segment as
`
`should have been reported by local authorities. The values are as described in appendix .. .,
`
`namely 'no ice', 'new ice or nilas', 'young ice', 'first year ice -60cm', 'first year ice -80cm',
`
`'first year ice -100cm' and 'first year ice ~100cm'.
`
`Fog probability. The attribute 'fog probability' describes the chance of occurrence of fog
`
`during the passage of the segment. According to the Mariners Handbook [NP 100] the fog
`
`chances are given in the number of days of fog per month. Commonly used values are 'O
`
`days/month' if not significantly more fog occurs in the particular region, (around) '5
`
`days/month' if fog occurs quite often in that area and (around) '10 days/month' if fog
`
`occurs often in that region.
`
`Connectivity. Because of the fact that the chain-node structure is used in the test(cid:173)
`
`environment, the start node and end node are implemented as well (in terms of their
`
`unique ID number). Also traffic regulation is implemented with the values 'two-way',
`
`'one-way, start node to end node' and 'one-way, end node to start node'.
`
`Harbour characteristics. Route-points can have the attributes describing the simulated
`
`harbour. In the test-environment this is done by creating an attribute 'harbour with the
`
`values 'no harbour' and 'harbour', and an attribute 'maximum allowable draught ' with the
`
`maximum allowable draught in meters as value.
`
`69 Since the withdraw! of Decca, GNSSs, Loran-C and Visual/radar positioning are the only important
`positioning systems left for marine navigation. The latter system, rather a method, is dependent on the presence
`of visual and radar conspicuous objects, in order to take bearings and measure distances to the 'beacons'.
`
`111
`
`116
`
`

`

`

`

`Soeedlimit
`routing measures
`
`piracy
`
`obstacles
`no of marks
`fairway marking
`
`aids to navigation
`
`fog
`
`ice
`
`ice season
`
`Route-areas
`attribute
`classification
`
`depth
`
`max. allowed speed (kts)
`0= none
`1=TSS
`2= Deep water route
`3= Recomm. route
`?=Inshore traffic zone
`O=negligible
`1 =recognisable
`2=sianificant
`number of obstacles
`number of marks
`0= none
`1= poor
`2= good
`0= none
`1= GNSS
`2= Loran-C
`3= visual/radar
`4= GNSS + Loran-C
`5= GNSS + visual/ radar
`6= Loran-C + visual/radar
`7= all available
`days of fog per month
`
`O=No chance of ice
`1 =New ice or Ni las
`2=Young ice
`3=First year ice -60cm
`4=First year ice -80cm
`5=First year ice -1 OOcm
`6=First year/old ice >100
`cm
`1 =februari/march
`2=september/october
`
`values
`1 =ocean passage
`2=coastal passage
`3=confined passaqe
`minimal chart depth (m)
`
`no
`yes
`
`Maximum allowed speed in knots.
`Type of routing measure (O=no routing measure
`enforced!)
`
`Appendices
`
`yes
`
`yes
`yes
`yes
`
`yes
`
`The chance of a attack of pirates or terrorists
`expressed in percentage.
`
`Number of obstacles within the boundaries.
`Number of marks that indicate obstacles.
`state of fairway marking
`
`Availability. The
`indicated positioning system
`available in the area.
`
`is
`
`yes
`
`yes
`
`Days of fog per month, >5 days is significant, > 1 O
`davs is manv
`Ice types. Type of ice represents thickness and
`determines the possibility of passage.
`
`no
`no
`
`Month with the greatest extent of ice; in these
`months thickness of ice shall be the greatest.
`Normally: 1=Northern hemisphere; 2= southern
`hemisphere.
`
`oblig. description
`yes What is the classification of the passage
`
`yes Minimal chart depth within boundaries (not an
`obstacle!)
`Forbidden cargo classes.
`
`yes
`
`prohib. cargo class O=none
`1 =dangerous goods cat
`NB
`2=dangerous goods cat
`C/D
`3=oil/gas
`4=cat NB and oil/gas
`5=all cateQories and oil/qas
`0= none
`4= Caution area
`5= Anchorage area
`6= Military exercise area
`?=Inshore traffic zone
`O=negligible
`1 =recognisable
`2=sianificant
`number of obstacles
`number of marks
`0= none
`1= GNSS
`2= Loran-C
`3= visual/radar
`4= GNSS + Loran-C
`5= GNSS + visual radar
`
`routing measures
`
`piracy
`
`obstacles
`no of marks
`aids to navigation
`
`yes
`
`Type of routing measure (O=no routing measure
`enforced!)
`routing measures for areas
`
`yes
`
`The chance of a attack of pirates or terrorists
`expressed in percentage.
`
`Ives
`Ives
`yes
`
`Number of obstacles within the boundaries.
`Number of marks that indicate obstacles.
`Availability. The
`indicated positioning system
`available in the area.
`
`is
`
`113
`
`118
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`