F
`
`AUTOMATED ROUTE PLANNING
`
`A NETWORK-BASED ROUTE PLANNING SOLUTION FOR
`MARINE NAVIGATION
`
`Department of Nautical Sciences, Royal Netherlands Naval College
`
`Institute of Engineering Surveying & Space Geodesy, University of Nottingham
`
`Author:
`Wichert J. de Jong, LTZ3
`
`Supervisor Royal Netherlands Naval College:
`H . Sabelis, KTZ ir.
`Head of the department of Nautical Sciences.
`
`Supervisor University of Nottingham:
`N. Bonnor, Air Commodore
`
`Bergen, December 2001
`
`This dissertation is submitted to the Royal Netherlands Naval College in partial fulfilment of
`the scientific education for naval officers.
`
`This dissertation is submitted to the University of Nottingham in partial fulfilment for the
`degree of Master of Science (Navigation Technology).
`
`1
`
`FLIR-1005.001
`
`

`

`Foreword
`
`Fore\vord.
`
`This thesis was written as conclusion of my studies at the Royal Netherlands Naval College.
`In addition, this dissertation was submitted to the University of Nottingham, in partial
`fulfilment for the degree of Master of Science in Navigation Technology.
`
`On the 14th of August 1996, I entered the Royal Dutch Navy, in order to fulfil my childhood
`dreams of sailing the seas. As my studies proceeded in the first three years of midshipman at
`the Royal Netherlands Naval College, my interest in especially navigation and its backgrounds
`grew. Therefore, I choose to attend the faculty of Nautical Sciences for the two years of
`specialisation. This choice also gave me the opportunity of attending the postgraduate MSc(cid:173)
`course in Navigation Technology at the Institute of Engineering Surveying and Space
`Geodesy (IESSG) at the University of Nottingham.
`
`During the lectures at the Royal Netherlands Naval College and the University of
`Nottingham, my interest was aroused in the modernisation of navigation, especially for the
`development of the Electronic Chart Display and Information System (ECDIS). Some
`research at the faculty of nautical sciences focussed on the automation of voyage planning.
`However, this research did not yet result in actual principles and algorithms. Therefore, I
`chose the subject of automation of route planning as the subject for this final project.
`
`In addition to this thesis, Martijn van der Drift wrote his thesis on the same subject, but
`focussed on the exact form and the programming of the route planning algorithm. [Drift, 2001]
`
`Now that my thesis is finished, I would like to thank a number of people. In the first place, I
`thank KTZ Ir. H. Sabelis, for the great enthusiasm he showed during his lectures and during
`the period of supervising my project. In the second place, I would like to thank Air
`Commodore Norman Bonnor for supervising my dissertation overseas. In the third place, I
`thank Martijn van der Drift for the close co-operation during the last months. I would like to
`thank Hanke for her great patience and unlimited support. Finally, I would like to thank my
`parents for their everlasting trust and support. Without all these people, I would never have
`come this far!
`
`Den Helder, September 2001,
`
`Wichert]. de Jong, LTZ3
`
`ii
`
`FLIR-1005.002
`
`

`

`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
`
`FLIR-1005.003
`
`

`

`List of contents
`
`List of contents.
`
`Foreword ......................................................................................................................... ii
`Abstract .......................................................................................................................... iii
`List of contents ............................................................................................................... iv
`I
`Preface ...................................................................................................................... 1
`I.1 Setting the scene ....................................................................................................................... 1
`I.2 The project. ............................................................................................................................... 2
`rfhe structure of this dissertation ........................................................................................... 4
`I.3
`II Voyage planning ...................................................................................................... 6
`II.1 The need for voyage planning ................................................................................................ 6
`II.2 A model of the voyage planning-process ............................................................................. 7
`II.2.1
`International regulations on voyage planning ........................................................................... 7
`11.2.2 The voyage planning-process according to Sabelis .................................................................. 7
`II.2.3 Automating the voyage planning-process ................................................................................. 9
`II.3 Route planning ........................................................................................................................ 10
`11.3.1 The route planning-cycle ..................................... : ...................................................................... 10
`II.3.2 Automating the route planning-process .................................................................................. 11
`II.4 Equivalents in the navigation domains ............................................................................... 12
`II.5 Geographic Information Systems (GIS) and Electronic Chart Display and
`Information Systems (ECDIS) ...................................................................................................... 13
`11.5.1 Geographic Information Systems ............................................................................................. 13
`11.5.2 Electronic Chart Display and Information Systems (ECDIS) ............................................. 15
`III Route-network analysis ............................................................... ; ......................... 17
`III.1 Analysing the shipping routes at sea ............................................................................... 1 7
`III.2 Network and graphs .......................................................................................................... 20
`III.3 Route-network. .................................................................................................................. 22
`IIl.3.1 Different components needed in the route-network. ........................................................... 22
`111.3.2 Positioning of the route-points and -segments ....................................................................... 26
`III.4 Designing the data structure ............................................................................................ 28
`111.4.1 Some basics on data formats ..................................................................................................... 28
`111.4.2 Commonly used data structures ................................................................................................ 30
`111.4.3 ECDIS: S-57 Transfer Standard for Digital Hydrographic Data [IHO, 1996] ................. 30
`111.4.4 The route-network in S-57 ......................................................................................................... 34
`111.4.5 Chain-node structure .................................................................................................................. 35
`IV Route planning information requirements ............................................................ 38
`IV.1
`Sailing order ........................................................................................................................ 38
`IV.1.1 Mission characteristics needed for route selecting ................................................................. 38
`IV.1.2 Ship's characteristics needed for route selection ................................................................... .40
`IV.2
`Some considerations on the required information for route-planning ..................... .42
`IV.2.1 Sources & availability .................................................................................................................. 42
`IV.2.2 Ocean, coastal and confined passages .................................................................................... .43
`IV.3 Relevant passage information during the route-planning process ............................. 44
`IV.3.1 Dilnension characteristics ......................................................................................................... .45
`IV.3.2 Navigational aspects ................................................................................................................... 46
`IV.3.3 Regulations and restrictions ....................................................................................................... 47
`IV.3.4 Remaining aspects ....................................................................................................................... 49
`IV.4 Relations between and influence of different kinds of information in the route-
`selection process .............................................................................................................................. 50
`IV.4.1 Testing the passages in terms of suitability and feasibility .................................................... 51
`IV.4.2 Analysing the passages in terms of preferability of characteristics ..................................... 52
`IV.5
`Implementation in the test-environment. ...................................................................... 53
`IV.5.1
`Implementation of Sailing Order characteristics in the test-environment. ........................ 53
`IV.5.2
`Implementation of passage characteristics in the test-environment ................................... 54
`
`iv
`
`FLIR-1005.004
`
`

`

`List of contents
`
`V Route planning algorithm . .................................................................................... 56
`V.1 Important considerations when automating route planning ........................................... 56
`V.1.1 What is the optimalroute? ......................................................................................................... 56
`V.1.2 The time-distance problem ........................................................................................................ 57
`V.2 Structure of the route planning algorithm .......................................................................... 58
`V.3 Preparing the data set for the algorithm ............................................................................. 61
`V.3.1 Collecting the information ......................................................................................................... 61
`V.3.2
`Filtering ......................................................................................................................................... 61
`V.3.3 Calculations .............................................. : ................................................................................... 63
`V.4 Optimal route finding algorithm .......................................................................................... 64
`V.4.1 Dijkstra's algorithm for the shortest path ............................................................................... 64
`V.4.2 Generating the K- shortest paths ............................................................................................ 66
`V.4.3 Criteria of preference .................................................................................................................. 66
`V.4.4 Group decision making under multiple criteria for selection of alternatives .................... 70
`VI Testing the route planning algorithm ................................................................... 75
`VI.1 Developing the test environment .................................................................................... 7 5
`VI.1.1 The goal of testing the algorithm .............................................................................................. 75
`VI.1.2 Choice for a synthetic test environment... ............................................................................... 75
`VI.1.3 Often occurring situations ......................................................................................................... 76
`VI.1.4 The final area ................................................................................................................................ 77
`VI.2 Test scenarios ..................................................................................................................... 77
`VI.2.1 The test ship ................................................................................................................................. 77
`VI.2.2 Scenario 1: Testing the filter algorithm and Dijkstra's algorithm ........................................ 78
`VI.2.3 Scenario 2: Testing the decision algorithm in limited test areas .......................................... 79
`VI.2.4 Scenario 3: Testing the whole algorithm in larger test areas ................................................ 81
`VII Conclusions and recommendations . ..................................................................... 84
`VII.1 Conclusions ........................................................................................................................ 84
`VII.1.1 The first question: the route-network. ..................................................................................... 84
`VII.1.2 The second question: information requirements ................................................................... 86
`VII.1.3 The third question: the algorithm ............................................................................................. 88
`VII.2 Recommendations ............................................................................................................. 90
`Glossary ......................................................................................................................... 92
`References ..................................................................................................................... 97
`List of figures ............................................................................................................... 103
`Appendices .................................................................................................................. 104
`Appendix A: Traffic density chart: route bound traffic on the North Sea. [Traffic, 2000] 104
`Appendix B: Example of the positioning of route-segments ................................................. 105
`Appendix C: Cargo classification and ice classification ........................................................... 106
`Appendix D: Attributes and attribute values as used in the test-environment .................... 108
`Appendix E: Final chain-node structure as used in the test-environment. .......................... 112
`Appendix F: The synthetic test environment ........................................................................... 115
`Appendix G: Test results of scenario 1 ...................................................................................... 116
`Appendix H: Test results of scenario 2 ...................................................................................... 120
`Appendix I: Test results of scenario 3 ........................................................................................ 127
`
`v
`
`FLIR-1005.005
`
`

`

`Chapter I
`
`I
`
`Preface
`
`1.1
`
`Setting the scene.
`
`Preface
`
`The present developments in navigation are especially dealing with automation. Even the
`
`conservative world of marine navigation is at the threshold of the computerised environment.
`
`A great deal of effort is being put into integrating navigation systems, developing the one(cid:173)
`man-bridge and using computers as the new medium for publications. A large share of this
`
`effort is ascribed to the Electronic Chart Display and Information System (ECDIS), since the
`
`possibilities for development of this system are endless. In addition to the electronically
`
`displayed nautical chart, with the real-time presentation of the own ship's position and the
`
`projection of radar and ARP A (Automatic Radar Plotting Aid) information on top of the
`
`chart, having other kinds of information, such as sailing directions and lists of lights, at the
`
`users' disposal interactively should be possible in the future. The role of ECDIS should
`
`therefore be supportive in more disciplines than it is now.
`
`A process, which is not always completed with the same accurary and precision as appropriate
`
`as general navigation is the voyage planning-process. The planning of a voyage is rightly
`
`contemplated as a time-consuming and laborious activity. The great diversity of sources of
`
`information that have to be consulted during the planning-process makes the process
`
`cluttered and difficult. Among other possibilities that ECDIS offers, it should be able tO
`
`support voyage planning. Research has been undertaken on the various digital storage
`
`methods and the presentation of all the required information, that is not displayed on the
`
`nautical chart [Carol, 1996]. However, the planning of a voyage in ECDIS is still only possible
`
`by clicking and dragging way-points with a mouse or track-ball; it is just a drawing tool. The
`
`only automated function with respect to route planning is checking the drawn track against a
`
`few features within a certain safety-zone around the track. No warning is giving on following
`
`the wrong traffic lane, for example. Neither can the optimal route be calculated.
`
`This is remarkable, because in the other two navigation domains, land navigation and air
`
`navigation, these processes have been automated already. Widely available (e.g. on internet)
`
`are route planners for car navigation. By giving the start and end position (cities, streets or
`
`postal codes), the software is able to calculate the shortest :route, either in length or in
`
`travelling time, using a real road network. It then presents the route on a digital map together
`
`with an information sheet. The same types of systems exist in air navigation, since aircraft use
`
`a network of airways and preferred routes. Spatial analyses are possible too (where is the
`
`1
`
`FLIR-1005.006
`
`

`

`Chapter I
`
`Preface
`
`nearest gas station?), because these route planners are applications of dedicated Geographical
`
`Information Systems. Is an ECDIS not a special form of GIS? Hence, particularly an ECDIS
`
`forms an ideal environment for automated voyage planning. [Sabelis, 1999(ii)]
`
`The voyage planning-process can be dissected into route planning, navigation planning and
`
`watch preparation. [Sabelis, 1999(ii)] Route planning deals with the selection of the route,
`
`navigation planning deals with the more detailed planning of the track and watch preparation
`
`should provide the officer of the watch with all information needed during his particular
`
`watch. All these steps are feasible for automation in one way or another. An automated tool
`
`for voyage planning should always be supportive, because safety of life and environment is
`
`involved. Decisions should thus always be the navigator's. During the preparation and
`
`execution of the watch, ECDIS should present relevant information dealing with the area the
`
`ship is, and will be, sailing. During the first two sub-processes, the software can generate
`
`route and track options without the active participation of the navigator. Given the fact that
`
`these stages of the voyage planning-process are the most laborious, route . planning and
`
`navigation planning are ideal for automation.
`
`This thesis will focus on the first process of voyage planning, route planning or route
`
`selection. Sabelis sketched the functionality of voyage planning software. [Sabelis, 1999(ii)] He
`
`supposed that a route-network should be a robust basis for route planning-algorithms. The
`
`use of such a network enables the developer of these algorithms to use the methods and
`
`knowledge on route planners from the other navigation domains. My thesis is based on the
`
`assumption that using a route-network as a basis for the selection of a route would offer a
`
`reasonable solution for the route planning-problem in marine navigation. I will not discuss
`
`what should be the best solution.
`
`1.2 The project.
`
`The subject of this dissertation is automating the route planning-process. The main goal of
`
`my project is the development of a route planning-tool, which, based on a route-network,
`
`calculates an optimal route from the point of departure to the point of arrival. Within the
`
`route, the navigator can determine his track. In order to develop a route planning-tool as
`
`described above, an inventory of the features of such a tool is required. First, there has to be
`
`some kind of data storage and structure, which is geographically referenced and easy to
`
`access, to allow the system to analyse the information quickly and correctly. The route(cid:173)
`
`network will form the basis for the data structure and information storage. Secondly, an
`
`2
`
`FLIR-1005.007
`
`

`

`Chapter I
`
`Preface
`
`algorithm is needed, which both analyses and combines all information, and which calculates
`
`and optimises route-alternatives. In the third place, a presentation method is required. The
`
`method of presentation will not be an issue in this dissertation. The following two objectives
`
`are defined:
`
`1.
`
`2.
`
`The development of a route-network at sea, which 1s suitable as basis for route
`
`planning-calculations.
`
`The search for a simple shortest path algorithm, with which the route planning(cid:173)
`
`problem can be solved, considering all the relevant information and in such way that
`
`the different options are feasible and navigable.
`
`From these objectives, the following questions and sub-questions are formed and will be
`
`answered in this thesis:
`
`A.
`
`What should be the structure of a route-network, to provide a robust basis for a
`
`shortest route algorithm?
`
`1.
`
`What data structure should be used for such a route-network, in order to
`
`provide the algorithm with
`
`the relevant information, and
`
`to provide
`
`compatibility with the Electronic Chart Display and Information System?
`
`11.
`
`What kinds of real routes can be distinguished at sea and with what kind of
`
`features can they be described adequately?
`
`111.
`
`How can such a network cover as many parts of the world as possible,
`
`without diminishing the calculation speed and extending disk storage?
`
`B.
`
`Which information is essential when selecting a route and should therefore be
`
`available to the shortest path algorithm?
`
`1.
`
`11.
`
`What are the relevant characteristics of a passage that are essential for the
`
`selection of a route?
`
`How should the characteristics of a route-segment be implemented in the
`
`route-network?
`
`111.
`
`How should the influence of particular route characteristics be expressed in
`
`terms of preference?
`
`lv.
`
`What are the ship's characteristics that are essential when selecting a route?
`
`How can the optimal route be calculated on the basis of a route-network?
`
`1.
`
`11.
`
`What is the optimal route?
`
`How should the ship's characteristics 'delete' route-segments that can or may
`
`not be used?
`
`3
`
`FLIR-1005.008
`
`

`

`111.
`
`How is an 'optimal' route (and alternatives) calculated?
`
`This project is carried out in co-operation with Martijn van der Drift. His project will focus
`
`on the development of the algorithm. He will engage himself in programming the algorithms
`
`and in discussing which algorithm is the most suitable solution for route planning at sea. The
`
`design of the test-environment as well as the testing is carried out together. If the reader is
`
`interested in his part of our project, he should read his dissertation [DRlFI, 2001].
`
`I.3 The structure of this dissertation.
`
`This thesis consists of seven chapters, including the preface. In the first chapter an
`
`introduction in the subject is given. After the introduction, the objectives of this thesis are
`
`discussed and translated into three research questions and a number of sub questions.
`
`Before we go into answering the questions, the reader is provided with the theory and
`
`backgrounds of the voyage planning process in chapter two. A model is used to describe the
`
`whole voyage planning process in order to clarify the role of route planning within that
`
`process. Some considerations are presented on the automation of the whole voyage planning
`
`process and the route planning process specifically. Also, the route planning equivalents in
`
`the other navigation domains are discussed, because of the fact that knowledge in the other
`
`domains could well be used for automation of voyage planning in marine navigation. Some
`
`important details on Geographical Information Systems (GIS) and the Electronic Chart
`
`Display and Information Systems (ECDIS) are discussed, since these are probably the
`
`systems a route planning tool should run on.
`
`Chapter three then concentrates on the first research question, concerning the route-network.
`
`It starts with the analysis of the existing routes at sea, and how they were formed historically.
`
`These routes are used as a basis for positioning the required route-network components, that
`
`are discussed in the next paragraph. Also, the appropriate data structure is discussed, after
`
`some theory on networks and graphs is presented. Finally, the implementation in the S-57
`
`data structure is described, as is the data structure that is used for testing the principle.
`
`The next chapter all the route planning information requirements are analysed and presented
`
`in chronological order. The route planning phase starts with the definition of the sailing
`
`order, which includes ship's characteristics and mission characteristics. Then the required
`
`4
`
`FLIR-1005.009
`
`

`

`route characteristics that influence the selection of the route are discussed. Finally, the kind of
`
`influence of the different types of information is described.
`
`Preface
`
`Chapter five considers all the aspects of the route planning algorithm. First, a definition of
`
`the best route is researched. Then, the important considerations and the logical sequence of
`
`the algorithm are discussed. The whole algorithm is presented in the following paragraphs.
`
`In the next chapter, the test environment and the tests are described, followed by conclusions
`
`and recommendations in chapter seven.
`
`Some words are printed in italics, which means that a definition of the term is listed in the
`
`glossary. After a term is mentioned, it will not be printed in italics again. The glossary also
`
`contains some important abbreviations.
`
`5
`
`FLIR-1005.010
`
`

`

`Chapter II
`
`Voyage planning in marine navigation
`
`JI Voyage planning.
`
`In this first chapter, some important theory is presented, that is essential for
`
`the
`
`understanding the different subjects covered by this research. The chapter begins with the
`
`need for voyage planning and what it is all about. Then, a model of the voyage planning
`
`process is presented against the background of international regulations on voyage planning.
`
`The following paragraphs will discuss some issues on automation of the voyage planning and
`
`route-selection processes. In the fourth paragraph, existing equivalents to route-planning in
`
`all the navigation domains are described. Finally, some background on Geographical
`
`Information Systems (GIS) and Electronic Chart Display and Information Systems (ECDIS)
`
`complete the chapter.
`
`11.1 The need for voyage planning.
`Before I go into the process of voyage planning more deeply, I should emphasise the need for
`
`a thorough preparation. The International Maritime Organisation (IMO) has set the present
`
`standard in the 'Guide to the planning and conduct of passages'. [IMO, 1978(i)] In paragraph
`
`three, the importance of planning and monitoring a passage is stated:
`
`' ... both planning of passages and the close and continuous monitoring of position
`
`during the execution of such plans are necessary and highly important in the interest
`
`of the safety of navigation.'
`
`Still, many casualties occur, of which many are due to the lack of a thorough planning of the
`
`passage. Especially groundings and strandings could be avoided if the planning is carried out
`
`correctly.
`
`In addition, it is important to state the objectives that can be achieved by planning a voyage.
`
`In the first place, the preparation provides a reference for the voyage enabling sensible
`
`monitoring of the ship's position. Monitoring the ship's state vector is only useful when all
`
`the safety limits and other important external factors in the vicinity of the ship are well
`
`defined. In the second place, dangero.us situations and potential conflicts can be foreseen and
`
`hence prevented. When the .mariner is aware of these situations and can identify the areas
`
`where potential conflicts can occur in advance, he can avoid these. Thirdly, planning is meant
`
`to provide a detailed scenario for the execution of a passage. The fourth objective is the
`
`possibility of optimising the route, in terms of travelling time or fuel consumption. The
`
`6
`
`FLIR-1005.011
`
`

`

`Chapter II
`
`Voyage planning in marine navigation
`
`utilisation o