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.