# The Backup-Connector

Automatically calculated distances and driving-times between `Nodes`

and `Resources`

are usually sufficient to solve an optimization problem. By default, a direct line between two elements is drawn to calculate the distance.
Follow this direct line, the driving-time is calculated by setting an average speed. The `BackupConnector`

can manipulate the calculations, account for external conditions, or completely exchange the algorithm used to calculate a connection.

## Overview

- Description - How JOptTourOptimizer calculates distances and times
- Modifying the distance and time calculation

## Description - How JOptTourOptimizer calculates distances and times

By default, JOptTourOptimizer uses a spherical earth model projected on to a plane for the distance calculation (flat-surface formula).

This flat-surface formula is getting more unprecise the further away two points are from each other. However, since
directly connected `Nodes`

in an optimized solution are usually not too far away from one another (on
earth-scale) the flat surface-formula is usually sufficient. Performance wise, the flat surface-formula is the
more efficient of the two.

The Haversine formula is more precise as it uses the great-circle distance between two points on a sphere. When comparing distances calculated with both formulas, the difference is almost negligible.

### Comparing Haversine and Flat-Surface

As an example, let's have a look at a distance of about 400 km between the cities "Cologne" and "Nuernberg":

- Flat-surface formula: 398.76 km
- Haversine formula: 403.73 km

The difference in the calculations of this magnitude is in the order of about 1%.

If we calculate a short distance of about 30 km between the cities "Essen" and "Wuppertal" the calculations look as follows:

- Flat-surface formula: 28.09 km
- Haversine formula: 28.13 km

Here, the error margin is even smaller than 0.1%.

**Keep in mind, that in an optimized solution distances between consecutively visited nodes are usually small. When
optimizing within cities, the distance between two successively visited Nodes is usually a few kilometres at most.**

### Calculation of the driving time

The calculation of the driving time is straightforward. By assuming a default average speed of *avgSpeed = 22 [meter/second]* the driving time can be calculated by:

*drivingTime = avgSpeed x distance*.

The average speed of each `Resource`

can be modified as follows:

```
IResource capacityResource = new CapacityResource("John", latitude, longitude,
maxWorkingTime, maxDistance, johnWorkingHours);
// Setting average speed to 30 meters/second
Quantity<Speed> avgSpeed = Quantities.getQuantity(30.0, Units.KILOMETRE_PER_HOUR);
capacityResource.setAvgSpeed(avgSpeed);
```

Please refer to the manual Basic Elements on how to create a `Resource`

.

## Modifying the distance and time calculation

Example

Find this example on GitHub: CustomNodeBackUpConnectorExample.

First of all, we need to tell the Optimizer's `NodeEdgeConnector`

to use a custom `BackupElementConnector`

. In our case, this will be the class `MyBackupElementConnector`

.

```
// Set custom backup connector
INodeEdgeConnector connector = new NodeEdgeConnector();
connector.setBackupElementConnector(new MyBackupElementConnector(false));
optimization.setNodeConnector(connector);
```

Using a `BackupConnector`

it is possible to modify the distance and driving time calculation of a connection. For this purpose, a custom class can be created that is extending `DefaultFlatEarthAverageSpeedBackupElementConnector`

:

When constructing our class `MyBackupElementConnector`

the constructor expects a boolean called `doRecalculateElement2ElementDuration`

.

```
public class MyBackupElementConnector
extends DefaultFlatEarthAverageSpeedBackupElementConnector {
/**
* Instantiates a new backup element connector.
*
* @param doRecalculateElement2ElementDuration the do recalculate
* element 2 element duration
*/
public MyBackupElementConnector(boolean doRecalculateElement2ElementDuration){
super(doRecalculateElement2ElementDuration);
}
...
```

When all defined `Resources`

have the same average speed, every `Resource`

will need the same time for the same connection and a recalculation will nod be necessary => `doRecalculateElement2ElementDuration = false`

. In case `Resources`

have different average speeds, the driving time has to be re-evaluated for each Resource separately => `doRecalculateElement2ElementDuration = true`

.

Overriding the two methods `getElement2ElementDistance(...)`

and ```
getElement2ElementDuration
(...)
```

changes the default calculation of distances and driving times in JOptTourOptimizer. In the following
paragraph, we implement both methods:

```
@Override
public Quantity<Length> getElement2ElementDistance(
String fromElementId,
double fromElementLon,
double fromElementLat,
String toElementId,
double toElementLon,
double toElementLat,
IResource visitor) {
double distance =
NodeEdgeConnector.distancePlacePlaceFlatEarth(
fromElementLon, fromElementLat, toElementLon, toElementLat)
* 1.2;
return Quantities.getQuantity(distance, METRE);
}
@Override
public Duration getElement2ElementDuration(
String fromElementId,
String toElementId,
double distanceMeter,
IResource visitor) {
long traveltimeMillis = (long) (distanceMeter / visitor.getAvgSpeed() * 1000L);
return Duration.ofMillis(traveltimeMillis);
}
```

In our implementation example we use the default method `NodeEdgeConnector.distancePlacePlaceFlatEarth(...)`

to calculate the distance between two points on the map. Further, we add a correction factor of 1.2 to each distance to factor in difficult terrain and twisty roads.
From now on every connection is 1.2 times longer than what JOptTourOptimizer usually would calculate. For the driving-time we use the default implementation.

In order to apply the haversine formula, we create a new method and use it within ```
getElement2ElementDistance
(...)
```

:

```
public static double haversineDistanceMeter(
double lon1,
double lat1,
double lon2,
double lat2) {
double r = 6371 * 1000.0; // Radius of the earth in meter
double deltaLatRad = toRad(lat2 - lat1);
double deltaLonRad = toRad(lon2 - lon1);
double a =
Math.sin(deltaLatRad / 2) * Math.sin(deltaLatRad / 2)
+ Math.cos(toRad(lat1))
* Math.cos(toRad(lat2))
* Math.sin(deltaLonRad / 2)
* Math.sin(deltaLonRad / 2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return r * c; // Distance in meter
}
private static Double toRad(Double value) {
return value * Math.PI / 180;
}
```

Example

Find Haversine example on GitHub: CustomNodeBackUpConnectorHaversineExample.

## Agreement

For reading our license agreement and for further information about license plans, please visit www.dna-evolutions.com.

## Authors

A product by dna-evolutions ©