Route Optimisation

Route Optimisation

In this section we outline the code used to generate optimal routes through a mesh constructed by the methods described in previous sections. This mesh should include the vessel performance parameters with respect to which objective functions can be defined for optimisation.

Route Optimisation Modules

Route Planner

This module is used for construction of routes within an environmental mesh between a series of user defined waypoints

RoutePlanner(mesh_file, config_file, cost_func=NewtonianDistance)

RoutePlanner finds the optimal route between a series of waypoints. The routes are constructed in a two stage process:

compute_routes: Uses a mesh based Dijkstra method to determine the optimal routes between a series of waypoints.

compute_smoothed_routes: Smooths the output of compute_routes using information from the environmental mesh to determine mesh independent optimal routes.

---

Attributes:

Name	Type	Description
env_mesh	EnvironmentMesh	mesh object that contains the mesh's cellboxes information and neighbour graph
cost_func	func	Crossing point cost function for Dijkstra Route creation
config	Json	JSON object that contains the attributes required for the route construction.
src_wps	list<SourceWaypoint>	a list of the source waypoints that contains all of the dijkstra routing information to reuse this information for routes with the same source waypoint

---

Constructs the routes within the mesh using parameters provided in the config file.

Args:

mesh_file(string): the path to the mesh json file that contains the cellbox information and neighbour graph

config_file (string): the path to the config JSON file which defines the attributes required for the route construction.
    Sections required for the route construction are as follows



    {

        "objective_function": (string) currently either 'traveltime', 'battery' or 'fuel',

        "path_variables": list of (string),

        "vector_names": list of (string),

    }


cost_func (func): Crossing point cost function for Dijkstra route construction. For development purposes
                  only!

compute_routes(waypoints)

Computes the Dijkstra routes between waypoints.

Parameters:

Name	Type	Description	Default
waypoints	String / Dataframe	DataFrame that contains source and destination waypoints info or a string pointing to the path of a csv file that contains this info	required

Returns: routes (List): a list of the computed routes

compute_smoothed_routes()

Uses the previously constructed Dijkstra routes and smooths them to remove mesh features paths will be updated in the output JSON

initialise_dijkstra_graph(cellboxes, neighbour_graph, route, path_index=False)

Initialising dijkstra graph information in a standard form used for the smoothing

Parameters:

Name	Type	Description	Default
cellboxes	list	List of cells with environmental and vessel performance info	required
neighbour_graph	dict	Neighbour graph for the mesh	required
route	Route	Route object for the route to be smoothed	required
path_index	bool	Option to generate the pathIndex array that can be used to generate new dijkstra routes	False

Returns:

Name	Type	Description
dijkstra_graph_dict	dict	Dictionary comprising dijkstra graph with keys based on cellbox id. Each entry is a dictionary of the cellbox environmental and dijkstra information.

to_json()

Output all information from the RoutePlanner object in json format

Returns:

Name	Type	Description
output_json	dict	the full mesh and route information in json format

flatten_cases(cell_id, neighbour_graph)

Identifies the cases with neighbours around a given cell and gets the ids of those neighbouring cells.

Parameters:

Name	Type	Description	Default
cell_id	str	The id of the cell to find the neighbours for	required
neighbour_graph	dict	The neighbour graph of the mesh	required

Returns:

Name	Type	Description
neighbour_case	list	A list of neighbouring case directions
neighbour_indx	list	A list of neighbouring cell indices

initialise_dijkstra_route(dijkstra_graph, dijkstra_route)

Initialising dijkstra route into a standard form used for smoothing

Parameters:

Name	Type	Description	Default
dijkstra_graph	dict	Dictionary comprising dijkstra graph with keys based on cellbox id. Each entry is a dictionary of the cellbox environmental and dijkstra information.	required
dijkstra_route	dict	Dictionary of a GeoJSON entry for the dijkstra route	required

Returns:

Name	Type	Description
aps	list<FindEdge>	A list of adjacent cell pairs where each entry is of type FindEdge including information on .crossing, .case, .start, and .end (see 'find_edge' for more information)

Crossing Points

The python package crossing implements the optimisation of the crossing point for the Dijkstra path construction using the NewtonianDistance class. In the section below we will go through, stage by stage, how the crossing point is determined and the methods used within the class.

NewtonianDistance(node_id, neighbour_id, cellboxes, case=None, unit_shipspeed='km/hr', time_unit='days', maxiter=1000, optimizer_tol=0.001)

Class that uses the Newton method to find the crossing point between cells based on their environmental parameters.

Parameters:

Name	Type	Description	Default
node_id	str	the id of the initial cellbox	required
neighbour_id	str	the id of the neighbouring cellbox	required
cellboxes	dict	a dictionary with all cellboxes in the mesh indexed by their ids	required
case	int	the case between the cellboxes	None
unit_shipspeed	str	the speed unit to use	'km/hr'
time_unit	str	the time unit to use	'days'
maxiter	int	the maximum number of iterations for the optimisation	1000
optimizer_tol	float	the tolerance value for the optimisation	0.001

value()

Applying a correction to determine the optimal crossing point between the start and end cell boxes

All outputs are given in SI units (m,m/s,s)

Outputs

Traveltime (tuple,[float,float]) - Traveltime legs from start cell centre to crossing to end cell centre cross_points (tuple,[float,float]) - Crossing Point in (long,lat) cell_points (tuple,[int,int]) - Start and End cell indices Case (int) - Adjacent cell-box case between start and end cell box

waypoint_correction(Wp, Cp)

Determines the traveltime between two points within a given cell Args: Wp (tuple): Start Waypoint location (long,lat) Cp (tuple): End Waypoint location (long,lat) Returns: traveltime (float) - Traveltime between the two points within cell in unit_time

traveltime_in_cell(xdist, ydist, u, v, s, tt_dist=None)

Determine the traveltime within a cell

Parameters:

Name	Type	Description	Default
xdist	float	Longitude distance between two points in km	required
ydist	float	Latitude distance between two points in km	required
u	float	U-Component for the forcing vector	required
v	float	V-Component for the forcing vector	required
s	float	Speed of the vehicle	required
tt_dist	bool	Returns traveltime and distance if true, otherwise just traveltime	None

Returns: traveltime (float): the travel time within the cell dist (float): the distance within the cell

Crossing Point Smoothing

FindEdge(cell_a, cell_b, case)

Class to return characteristics information about the edge connecting two cells. This information includes:

crossing (tuple) - Crossing point (long,lat) case (int) - Case type connecting the two cells start (dict) - Dictionary containing the environmental parameters of the start cell end (dict) - Dictionary containing the environmental parameters of the end cell

PathValues(path_vars)

A class that returns attributes along a given path intersecting the environmental/vessel mesh.

Attributes:

Name	Type	Description
unit_shipspeed	string) - unit speed type. This is a string of type	'km/hr','knots'
unit_time	string) - unit time format. This is a string of type	'days','hr','min','s

Parameters:

Name	Type	Description	Default
path_vars		The path variables specified in the route config	required

objective_function(adjacent_pairs, start_waypoint, end_waypoint)

Given a list of adjacent pairs determine the path related information apply waypoint_correction to get path related information along the path

Inputs

adjacent_pairs (list of type find_edge) - A list of the adjacent cell pairs in the form of find_edge start_waypoint (tuple) - Start waypoint (long,lat) end_waypoint (tuple) - End waypoint (long,lat)

Smoothing(dijkstra_graph, adjacent_pairs, start_waypoint, end_waypoint, blocked_metric='SIC', max_iterations=2000, blocking_percentage=10.0, merge_separation=0.001, converged_sep=0.001, objective_function='traveltime')

Class construct that has all the operations required for path smoothing. Including: Relationship of adjacent pairs, edge finding new edges to add and returns a list of the adjacent pairs for the constructed path

Parameters:

Name	Type	Description	Default
adjacent_pairs (list,find_edge) - An initial list of adjacent cell pairs as 'find_edge' objects comprising		.start, the start cell environmental mesh dictionary; .end, the end environmental cell information; .crossing, a tuple of the crossing point on the edge (long,lat); and, .case, the adjacent cell case between the two cell boxes.	required

add(index, ap_list)

Adding in a new adjacent cell pair

blocked(new_cell, cell_a, cell_b)

Function that determines if the new cell being introduced is worse off than the original two cells according to various metrics.

Return

True if the cell cannot be entered, False if the cell can

blocked_ice(new_cell, cell_a, cell_b)

Function that determines if the SIC of the new cell being introduced is worse than the original two cells. Currently, this is hard encoded to not enter a cell 5% worse off in Sea-Ice-Concentration

Return

True if the cell cannot be entered, False if the cell can

blocked_objective(new_cell, cell_a, cell_b, blocked_variable)

Function that determines if the relevant objective variable of the new cell being introduced is worse than in the original two cells.

Return

True if the cell cannot be entered, False if the cell can

blocked_tt(new_cell, cell_a, cell_b)

Function that determines if the tt for the new cell being introduced is worse than the original two cells.

Return

True if the cell cannot be entered, False if the cell can

clip(cell_a, cell_b, case, x)

Given two cell boxes clip point to within the cell boxes

Function that clips back the crossing point so that it is only on the intersection between the two cell boxes in the adjacent cell pair

Return

x (tuple) - Updated crossing point clipped to cell intersection (long,lat)

diagonal_case(case)

Function that determines if the adjacent cell pair is a diagonal case

Returns True is diagonal case, false if not

diagonal_select_side(cell_a, cell_b, case, firstpoint, midpoint, lastpoint)

Assuming that midpoint is the common corner of the two cells in the diagonal edge ap. Then this function returns the cell that shares a boundary with both ap.start and ap.end on the same side of midpoint as the shorter great circle arc (using pyproj with default projection 'WGS84') passing between firstpoint and lastpoint.

If that cell is not in the neighbourhood graph then this returns None

Returns additional_indices (list) - A list of possible cell dictionary info. None if no index added. additional_cases (list) - A list of the cases connecting the additional cell indices. None if no index added.

dist(start_point, end_point)

Determining the absolute distance between two points using pyproj and the reference project (default: WGS84)

Inputs

start_point (tuple) - Start Point (long,lat) end_point (tuple) - End Point (long,lat)

Outputs: distance (float) - Distance between the two points in km

forward()

Applies inplace this function conducts a forward pass over the adjacent cell pairs, updating the crossing points between adjacent cell pairs for the given environmental conditions and great-circle characteristics. This is applied as a forward pass across the path moving out in adjacent cell pairs (triplets of crossing points with the cell adjacency).

Key features of forward pass include reverse edges - Removal of adjacent cell edges that enter and exit a cell on subsequent iterations. e.g. routes going back on themselves merging - When two crossing points are close, merge points and determine new common edge between start and end point diagonal case - If the middle point is a diagonal edge between cells, introduce a new cell box dependent on start and end crossing points. If cell is inaccessible 'blocked' then remain on corner for a later iteration.

                If exact diagonal, with same start and end crossing point, has be seen before
                then skip.

newton smooth - If adjacency is not diagonal then smooth the midpoint crossing point on the boundary given a
                horizontal or vertical smoothing. Returns a new midpoint that can either lie on the boundary
                between the two cells or outside the boundary

                If lies on the boundary then check if similar to previous seen case of this crossing point
                else continue and not converged

v shaped add  - If the crossing point lies outside the boundary in the newton smoothing stage the addition
                cell/cells must be included.

                Determine the new edges that need to be included if only a single cell (two edges) then do
                a v-shaped addition. If blocked then trim back. If exact v-shaped seen before, with same
                midpoint prime and possible edge additions, then skip. If blocked or seen before and crossing
                point hasn't changed within converge_sep then the crossing point has converged

u shaped add - Identical to v-shaped add but now with the addition of 2 cells (3 edges). If blocked then trim back. If exact v-shaped seen before, with same
                midpoint prime and possible edge additions, then skip. If blocked or seen before and crossing
                point hasn't changed within converge_sep then the crossing point has converged.

This code should be read relative to the pseudocode outlined in the paper. https://arxiv.org/pdf/2209.02389

nearest_neighbour(start, end, case, x)

Returns the cell in the mesh that shares a boundary with cellA and has an edge on the line that extends the common boundary of cellA and cellB (and on which the point x lies) in the direction of x. If x lies inside cellA or there is no cell that satisfies these requirements, it returns null.

Returns additional_indices (list) - A list of possible cell dictionary info. None if no index added. additional_cases (list) - A list of the cases connecting the additional cell indices. None if no index added.

newton_smooth(start, end, case, firstpoint, midpoint, lastpoint)

Given an adjacent cell pair that are non-diagonal determine the update to the crossing point/midpoint given the environmental conditions

Input

start (dict) - Dictionary of the start cell information end (dict) - Dictionary of the end cell information case (int) - Adjacency case type connecting the two cells firstpoint (tuple) - First Point (long,lat) midpoint (tuple) - Midpoint Point (long,lat) lastpoint (tuple) - Last Point (long,lat)

Return: midpoint (tuple) - Updated midpoint (long,lat)

previous_diagonals(edge_a, edge_b, firstpoint, lastpoint)

For a diagonal-additional case determine if we have already seen these edges added in the same situation and the same first and last points. If a common past has been seen return True, otherwise add an additional case to of the diagonal to the global list and return False

Input

edge_a (find_edge) - First-edge connecting start cell to new cell edge_b (find_edge) - First-edge connecting new cell to end cell firstpoint (tuple) - firstpoint in the adjacent cell triplet of points (long,lat) lastpoint (tuple) - lastpoint in the adjacent cell triplet of points (long,lat)

Return

True if this diagonal case has been seen before, or false if not

previous_us(edge_a, edge_b, edge_c, midpoint_prime)

For a U-additional case determine if we have already seen these edges added in the same situation and the same crossing point. If a common past has been seen return True, otherwise add this U-additional case to a global list and return False

Input

edge_a (find_edge) - First-edge connecting start cell to new cell 1 edge_b (find_edge) - First-edge connecting new cell 1 to new cell 2 edge_c (find_edge) - First-edge connecting new cell 2 to end cell midpoint_prime (tuple) - midpoint that triggered the u-additional case addition (long,lat)

Return

True if this U-additional case has been seen before, or false if not

previous_vs(edge_a, edge_b, midpoint_prime)

For a V-additional case determine if we have already seen this edge added in the same situation. If a common past has been seen return True, otherwise add this v-additional case to a global list and return False

Return

True if this v-additional case has been seen before, or false if not

remove(index)

Removing an adjacent cell pair

dist_around_globe(start_point, crossing_point)

Determining the longitude distance around the globe between two points

Parameters:

Name	Type	Description	Default
start_point	tuple	Start Waypoint (long,lat)	required
crossing_point	tuple	End Waypoint (long,lat)	required

Returns: a (float): longitude distance between the two points in degrees

rhumb_line_distance(start_waypoint, end_waypoint)

Defining the rhumb line distance from a given waypoint start and end point

Parameters:

Name	Type	Description	Default
start_waypoint	list([Long, lat])	Start Waypoint location with long lat	required
end_waypoint	list([Long, lat])	End Waypoint location with long lat	required

Returns:

Name	Type	Description
distance	float	Calculated rhumb line distance

rhumb_traveltime_in_cell(cellbox, cp, sp, s, u, v)

Calculates traveltime in a cellbox based off of rhumb line distance

Parameters:

Name	Type	Description	Default
cellbox	dict	Cellbox containing line segment being analysed	required
cp	ndarray	End waypoint coordinates (long,lat)	required
sp	ndarray	Start waypoint coordinates (long,lat)	required
s	float	Ship speed value	required
u	float	Current velocity x-component	required
v	float	Current velocity y-component	required

Returns:

Name	Type	Description
tt	float	Calculated rhumb line travel time