# The routing algorithm

The `RouteModule`

is used by the server to handle requests for routes between one or more origins to one or more destinations.

As the maps are represented as directed graphs, the normal algorithm used to calculate the shortest path between two nodes is the *Dijkstra* algorithm. This algorithm is used in conjunction with a modified version called the *A ^{*}* algorithm which uses the fact that the best path ought to lie in the direction towards the destination.

The server covers a large area, hence the map database is large. For memory efficiency we have partitioned the road network into sufficiently large maps. This means that the origin and the destination are not necessarily in the same map. For calculation efficiency we introduced hierarchical maps.

As with all modules, there is a route leader and zero or more available `RouteModule`

instances. The task of distributing sub routes is done by `RouteSender`

object in the server.

### Routing on lower hierarchical maps

If the distance between the origins and the destinations are small we have to consider all roads when calculating the best route, i.e. we are using a level 0 map. If the origin and the destination lies within the same map the algorithm calculates the route and returns the `RMSubRoutes`

to the destination and to the external nodes that have costs that are less than the cost to the destination.

### Routing to higher hierarchical maps

When routing over large distances, e.g. from Stockholm to Berlin, we cannot consider all the small roads in between, hence we have a hierarchical structure for the maps.

The difference between higher level routing and lower level routing is that the `RouteModule`

does not route on all nodes when the route should become a higher level route. The `RouteModule`

uses two bounding boxes to decide which nodes that should be included in the route calculation. The inner bounding box is created by taking the coordinate of the origin and expanding the box with a constant distance in the `x`

and `y`

directions. The outer bounding box is created the same way but with a larger increase in size. Inside the inner bounding box the following connections are allowed (`higher level node`

means that the node exists on the overview map):

Connections from a lower level node to a lower level node.

Connections from a higher level node to a higher level node.

Connections from a lower level node to a higher level node

Inside the outer bounding box the following connections are allowed:

Connections from a lower level node to a higher level node.

Connections from a higher level node to a higher level node.

This decreases the number of nodes and connections that have to be considered by the Dijkstra algorithm, hopefully without decreasing the optimality of the route very much.

### Calculating the cost

To quickly reach the destination we will use an algorithm that attracts the route towards the destination node, i.e. the *A ^{*}* algorithm. This is done by adding a second cost that represents the estimated cost of getting from the origin to the destination. This cost is used to decide which node to remove from the heap. When we update a node we first calculate the cost of getting from the origin to the current node and store this value in the normal cost. Then an estimation of the distance from the current node to the closest destination will be calculated and added to the estimation cost. This cost has to be lower than the actual cost to guarantee an optimal path. If we are using distance as cost parameter we would like to use the flight distance as the estimation. This is an expensive calculation, but it seems that the cost of reading/writing nodes from memory greatly overshadows this problem, so the estimated distance is calculated as

*sqrt( delta*. If the cost represents time we use

_{x}^{2}+ delta_{y}^{2})*dist/max(speed)*for the estimation. Currently

`max(speed)`

is set to 120 km/h.### CalRoute

For each `RoutingMap`

loaded in the `RouteModule`

, a `CalcRoute`

object is created. The `RoutingMap`

is deleted when the `CalcRoute`

is deleted. `CalcRoute`

is the class that does the actual routing.

#### Member functions

**route**Main function that loops through functions below for each request.**removeDups**Removes identical origins and destinations.**routeOnOneSegment**Creates routes where the origin and destination is on the same segment.**initRoute**Prepares the map and queues for the*Dijkstra*algorithm.**calcCostDijkstra**This function uses the*Dijkstra*algorithm or the*A*algorithm to create routes to the destination nodes.^{*}**calcCostExternalDijkstra**Calculates routes from the origin to all external connections.**readResult**Reads the routes from external nodes and/or destinations back to origins.

##### removeDups

This method removes duplicate origins and duplicate destinations. This is necessary for e.g. `calcCostDijkstra`

which ends when all destinations are found.

##### routeOnOneSegment

The method `routeOnOneSegment`

is called before `initRoute`

and loops over all origins and destinations and checks if the node id is the same for the current origin and destination. If the node id is the same, it calculates a route on the segment if the offset for the destination is greater than the offset for the origin. The `RouteModule`

uses offset from the current node (unlike the rest of *MC2* that always uses offset from node zero) which makes calculations easier to follow. The one segment routes created by the method are put into the result list and then it is up to the server to decide whether to use it or not. State changes and penalties are added to the route if it is impossible to drive on the segment.

##### initRoute and initRouteFirstTime

The method `initRoute`

enqueues the start nodes into the priority queue. If the originalRequest-flag is set in the packet from the server, `initRouteFirstTime`

is called instead. This behaviour should change, since there can be both `first time`

-routes and continued routes in the same request from the server. `initRouteFirstTime`

takes the offset into consideration and does not enqueue the start nodes themselves, but takes the origins and enqueues the nodes to which the origins have connections. The offset cost of the origin nodes are subtracted from the cost of the enqueued nodes. `initRouteFirstTime`

also enqueues nodes with restrictions which make the nodes forbidden for the vehicle selected by the user. These are enqueued in a separate queue, `m_notValidPriorityQueue`

. If there are no valid nodes in the ordinary priority queue, the nodes in `m_notValidPriorityQueue`

will be expanded until a valid node is reached. This node is then inserted into the normal priority queue and the ordinary routing can begin.

##### calcCostDijkstra} and calcCostExternalDijkstra

These two methods do essentially the same thing, i.e. calculates the shortest path from the origin to the destination(s) using the *Dijkstra* algorithm. The difference it that `calcCostDijkstra`

stops after finding one or many destinations (depending on the input) or until the heap is empty and `calcCostExternalDijkstra`

runs until the heap is empty. The methods dequeue nodes from the priority queue. Every connection from the dequeued node is checked for vehicle restrictions and every connected node is checked for node restrictions. If the connection and new node have restrictions which are allowed, the real cost and estimated cost of the new node are updated with the connection costs and, if the cost is less than the cut off, it is enqueued into the priority queue. The gradient of the new node is set to the old node so that the route can be followed backwards from the destination when the result is read. This is repeated until the stop criteria for the function is fulfilled.

##### readResult

After the *Dijkstra* functions are run `readResult`

is called. The main task for the method is to create `RMSubRoutes`

by following the gradients of the destination nodes back to the origins. But before this can be done it has to check if the destination could be reached the normal way or not. `calcCostDijkstra`

and `calcCostExternalDijkstra`

only consider the nodes that can be reached using the vehicle selected by the user. Sometimes that vehicle is not allowed to be used all the way to the destination. If this is the case we try to calculate the last part of the route using a pedestrian as vehicle. It is done like this:

The destinations are checked. If no destinations have been reached with the normal vehicle we continue to the next step.

The estimated cost of the destination nodes are set to

`0`

.The destination nodes are equeued into the

`m_notValidPriorityQueue`

.Routes are made from the destinations using

`m_notValidPriorityQueue`

and backward routing, but only the estimated cost of the nodes are used (in the method`expandNonValidNodesResult`

).If a node with the real cost set (by

`calcCostDijkstra`

) is reached it is put into`m_normal-PriorityQueue`

.All the nodes affected by

`expandNonValidNodesResult`

except the ones in`m_normal-PriorityQueue`

are reset to default values.`expandNodesResult`

is run. It calculates forward routes from the nodes in`m_normal-PriorityQueue`

to the destination without considering vehicle restrictions.

When this is done `readResulFromDestination`

is called for all destinations that were reached and the `RMSubRoutes`

are created. These are then sent to the server.

### The BucketHeap

The BucketHeap is the heap type used by the *Dijkstra* algorithm in the `RouteModule`

.

#### The idea of the heap

The BucketHeap is a data structure specifically designed to be used as a heap in the *Dijkstra* algorithm. Its idea is that the heap consists of several buckets in which to put nodes of the graphs (=maps). A specific range of costs has been assigned to each bucket so that each bucket contains nodes with about the same cost. In a bucket, the ordering of the nodes is not important, and therefore nodes can be inserted into the heap very fast. The only thing to be done is finding the correct bucket. Removing a node from a bucket is somewhat more slow, the bucket containing the nodes with the least cost has to be searched for the minimum cost with linear search, which is slow. To improve the speed of the heap, no sorting should be done unless there is a destination node in the current bucket.

#### Algorithms for the BucketHeap

The only supported operations on the BucketHeap are `enqueue`

, `dequeue`

, `isEmpty`

and `reset`

. The reason that no other operations are defined is that the kind of *Dijkstra* used does only need these. The heap work in the following way:

The buckets of the heaps all carry nodes with ascending costs, i.e. one bucket contains nodes carrying the currently lowest costs, the next bucket contains the following node costs and so on. The cost span is the same for all buckets. The bucket with the lowest costs, the minimum cost bucket, and the lowest cost available for enqueue itself are stored in variables. The maximum cost is decided by the number of buckets and the cost span of a bucket. This implies that only a finite cost range of node costs can exist at a time in the heaps. However, the *Dijkstra* algorithm will never enqueue a node with cost lower than the lowest cost the heap can handle (that node cannot have been previously dequeued). If, for any reason, this happens anyway, the node will be enqueued in the minimum costs bucket and will be found. If a node with larger cost is to be enqueued, it will simply have to be put into a special, extra large bucket that is used for too large costs, the large costs bucket.

As the buckets have a finite size, overflow might occur. Therefore, to every bucket (also the large costs bucket) an overflow list is attached to take care of the overflow nodes. Normally, these lists will be empty.

##### Resetting

The `reset`

operation simply marks the buckets as empty and sets all other variables (like the minimum cost the heap is supposed to handle and the bucket with the minimum cost) to zero or something equivalent. If overflow has occurred during the routing, the overflow lists will be cleared.

##### Enqueueing a node

There are three cases that can occur when starting `enqueue`

. If the cost of the node is so large that it is larger than the cost span of the heap the node has to be put into the large costs bucket. This very large bucket should be emptied by `dequeue`

at certain conditions. If the cost is smaller than what the minimum cost bucket holds, the node will be enqueued into that bucket anyway. This will not pose a problem, since `dequeue`

will find that node in its linear search and return it. Although the approach with too small costs is straightforward it should never happen, as *Dijkstra* and *Dijkstra-like* algorithms never will enqueue a node with smaller cost than the lowest cost in the heap. There are some special cases though, when a modified algorithm makes this happen. The third and most common case of costs is when the cost of a node fits into the cost span. The correct bucket to put the node into is computed, and the node is enqueued. Also, a variable containing the total number of nodes is increased.

If the chosen bucket is full when one wants to put more nodes in it, overflows, the node will be put in the respective overflow list by a special function `overflowEnqueue`

.

##### Checking if the heap is empty

The operation `isEmpty`

is the simplest. It simply checks if all buckets are empty. If so is the case, the function returns `true`

, otherwise `false`

. This will be done by checking if the total number of nodes is zero.

##### Dequeuing the minimum cost node

The `dequeue`

-operation is the most time consuming and complex of the BucketHeap, because all work has been left to this function. First a consolidating function, `flushHeap`

is called. It examines the minimum cost bucket and if the number of nodes in this bucket is zero, the next bucket in cost order becomes the minimum cost bucket and the old bucket is assigned costs one step higher than the previously largest costs. If the first bucket that was the minimum cost bucket has again become minimum cost bucket `flushHeap`

calls another function, `tryToEmptyLargeCostsBucket`

, that will try to empty the large costs bucket carrying the nodes that previously had too large costs to be enqueued into the normal buckets. There is a good chance that many of the nodes in this bucket now successfully can be moved to the normal heap, because the node costs handled by the heap now are substantially larger. The reason for moving the nodes back to the normal heap is that dequeuing never will take place in the large costs bucket. The function `tryToEmptyLargeCostsBucket`

examines every element in the large costs bucket and, if the current node is enqueueable, puts it into the right bucket, just as `enqueue`

would. If the node still has a too large cost it will remain in the large costs bucket. When `tryToEmptyLargeCostsBucket`

and `flushHeap`

are done, `dequeue`

has a minimum cost bucket containing nodes and starts to search (with linear search) for the node with the smallest cost. When that node is found the total number of nodes in the heap is decreased and the minimum cost node is returned. If this bucket has a non-empty overflow list the function `overflowDequeue`

will browse the list and the minimum cost bucket to find the minimum cost node.

##### Implementation of the heap

The buckets are implemented as a matrix with the rows as buckets and the columns representing spaces in the buckets. The large costs bucket is an extra large array (if the length of a bucket array is $A$, the length of the large costs bucket has length *A ^{*}*, just to make sure that it is so large that overflow almost never occurs). The number of nodes in a bucket is stored as an array with the size of the number of rows in the matrix. Thus, when performing

`reset`

only the array is set to zero, and the time consuming reset of the heap matrix is omitted. The number of nodes in the heap is stored in a variable and then `isEmpty`

only needs to check if this variable is zero or not.When `enqueue`

decides which bucket (row in the matrix) a node should be put into the following piece of code is used:

Here `rowIndex`

denotes the row chosen, `cost`

is the cost of the node to enqueue, `m_costsStartAt`

is the lower cost bound of the heap and `m_heapStartIndex`

is the index of the matrix that denotes the minimum cost bucket. `ROWS`

is the number of rows in the matrix (number of buckets). The `MATRIX_DIFF`

is the cost span of a bucket which equals *2 ^{MATRIX_DIFF_EXPONENTIAL}*. The logical shift operation

`>>`

is used instead of dividing, as this is an essentially faster operation.The four important heap constants are `ROWS`

(= the number of buckets), `COLUMNS`

(= the number of possible spaces to put a node into in each bucket), `MATRIX_DIFF`

(= the cost difference between two rows in the matrix, i.e. between two buckets) and `MATRIX_DIFF_EXPONENTIAL`

which was explained above. These parameters have an enormous influence on the performance of the Bucket Heap and the choice of these constants is a matter of optimization. See figure below for an example of the BucketHeap.

### RouteRequest and subclasses

The tree of classes under `RouteRequest`

takes care of the intelligence that controls how to do routing between maps, whereas the `RouteModule`

does the routing on each map. These two instances communicate through the classes held in `ServersShared`

described in a separate section below. Dependencies within the server as well as to the shared objects are found in this figure.

#### CoordinateObject

This class handles questions concerning mapping from coordinates to item. It finds the item closest to the coordinate. Note that two maps can overlap, and hence several maps may contain the required information.

##### Member functions

**processPacket**Takes care of a`CoordinateReplyPacket`

after a request has been sent, and either generates a new request or prepares the answer.**getNextPacket**Returns the next packet from`m_packetsReadyToSend`

**addCoordinate**Adds a coordinate to the question.**getCoordinateReply**Returns a`CoordinateReplyPacket`

as an answer to the original question.

#### OrigDestLookup

This class is used to complete data about each `OrigDestInfo`

in a request, and uses a `CoordinateObject`

for one type of questions.

##### Member functions

**processPacket**Takes care of a`CoordinateReplyPacket`

or an`ItemReplyPacket`

after a request has been sent.**getNextPacket**Returns the next packet from`m_outgoingQueue`

.

#### ServerSubRouteVector

Inheriting from Shared class `SubRouteVector`

this class will help other server classes to keep track of what `SubRoutes`

have been routed on and which to continue.

##### Member functions

**insertSubRoute**Inserts an element last in the vector. Also tells the SubRoute what index it is.**getCutOff**Returns the greatest of the costs to get to a destination if we should return the routes to all destinations. Returns the cheapest cost to one destination if this is the last part of the route. MAX_UINT32 if we have not reached all destinations yet.**containsCheaperThan**Returns true if the vector contains a subroute with cheaper or same real cost to the same destination node.**merge**Adds all the SubRoutes from sourceVector, except the last one, which instead is returned.**getResultVector**Function for finding the SubRoutes that make up a route with specified index to`m_destIndexArray`

when routing is finished.

#### SubRouteContainer

Main server class for holding information about a group of `SubRoutes`

while routing. When routing is finished, the `SubRoutes`

will instead be put in a `ServerSubRouteVector`

.

Entries consist of `SubRoutePair`

objects (see `pair`

in map in STL). Key is estimated cost in the node where the `SubRoute`

ends. By using this key, two things will go faster:

Assigning a new best SubRoute when the previous is dequeued.

Finding and removing SubRoutes above cutoff cost.

Data in the pair is a pointer to a `SubRoute`

. Class inherits from `multimap`

(STL).

##### Member functions

**moveAllSubRoutes**Finds and dequeues all remaining SubRoutes in the container and moves them to specified resultVector.**dequeueSubRoutesFromBestMap**Finds and dequeues all`SubRoutes`

ending in`m_mapIDBestSubRoute`

.**checkAndInsertSubRoute**Uses multimap function ‘insert’ on a`SubRoute`

pointer.**insertSubRoute**Uses multimap function ‘insert’ on a SubRoute pointer.**insertOrigDestInfo**Inserts an`OrigDestInfo`

as a new`SubRoute`

into the container.**updateContainer**Calls`clearGreaterThanCutOff`

and then updates`m_mapIDBestSubRoute`

.**updateCutOff**Sets the value of`m_cutOff`

if new cutOff smaller than`m_cutOff`

.**getSize**Returns the size of the`SubRouteContainer`

#### LevelTransitObject

This class does all the tasks involved in going up and down a level in the routing. That includes finding origin and destination nodes on higher level, and keeping track of which maps to route on after routing on higher level.

##### Member functions

**processPacket**Takes care of a range of different`ReplyPacket`

s after a request has been sent, and either generates a new request or prepares an answer.**getNextPacket**Returns the next packet from`m_outgoingQueue`

.**allowedMapID**Returns true if specified mapID is in`m_destMapSet`

.**getLowerLevelDest**Returns an OrigDestInfo from`m_matchHighLowIDMap`

specified by map ID and node ID.**getHigherLevelOrigList**Returns`m_higherLevelOrigList`

which must previously have been created by this object.**getHigherLevelDestList**Returns`m_higherLevelDestList`

which must previously have been created by this object.

#### RouteSender

Adminstrates the packets for a route request. Divides the question into subroute requests for a single map, and then creates a `RequestPacket`

for that question. The packet is sent through the server to the `RouteModule`

to be calculated.

##### Member functions

**processPacket**Takes care of a range of different`ReplyPacket`

packets after a request has been sent, and either generates a new request or prepares an answer.**getNextPacket**Returns the next packet from`m_outgoingQueue`

.**getRoute**Goes through the`m_finishedSubRouteVector`

and backtracks the finished routes. Each of these is a`SubRouteVector`

. Return type is`SubRouteVectorVector`

.**insertOrigDestInfo**Inserts an origin as destination in a SubRoute to initialize routing there. Then adds this SubRoute to`m_requestSubRouteContainer`

.

#### RouteObject

Class for taking care of a route. Any number of origins and destinations can be used but in most cases only one origin and one destination is used or either multiple origin or multiple destinations but not both.

##### Member functions

**processPacket**Takes care of a range of different`ReplyPacket`

packets and rebuilds the outgoing list.**getNextPacket**Returns the next packet from`getNextPacket`

in`m_routeSender`

.**getRoute**Returns the answer to the constructor question when the routing is finished.

#### ExpandRouteConcatenator

Creates a new list of split packets internally in the object.

#### RouteExpander

Class that creates an expanded list of directions corresponding to a finished route.

##### Member functions

**processPacket**Takes care of a`ExpandRouteReplyPacket`

and merges all to one route.**getNextPacket**Returns the next`ExpandRouteRequestPacket`

packets from`m_requestPacketList`

.**getList**Returns the answer to the constructor question when the routing is finished.

#### RouteRequest

This class administrates a routing question.

##### Member functions

**processPacket**Takes care of a`ReplyPacket`

and sends on to the appropriate child.**getNextPacket**Returns the next`RequestPacket`

from the appropriate child.**getExpandedRoute**Get the route as an`ExpandedRoute`

object that is easy to use.**addOrigin**Adds an origin for the routing. Must be called before the`RouteRequest`

is processed.**addDestination**Adds a destination for the routing. Must be called before the`RouteRequest`

is processed.**getStatus**The status after the`RouteRequest`

has been processed. StringTable::OK if routing was successful.