Basic elements of JOpt for Java

In this part, we learn about the basic elements of JOpt for defining an optimization input in Java. (Please note, when using the Docker variant of JOpt elements are defined via the JSON format used by the containers Swaggers endpoint).


Table of contents


Examples - Educate yourself

Screenshot

For an extensive collection of examples (written in Java) please visit our official GitHub page. This fully functional Maven project can be cloned and can be used as a base for starting with JOptTourOptimizer.


General info

In easy terms, JOpt is finding an optimized distribution of nodes and resources. In general, a resource can visit and work on a node. In a pick-up and delivery problem, a resource might be seen as a truck, which carries goods and has the task to either deliver goods to a node or pick-up goods from a node. Of course, in a real-world problem, many different restrictions can occur like:

  1. Is the working time of the resource matching to the opening hours of the node?
  2. Is the resource allowed to visit the node, for example, due to skill restrictions or customer restrictions like "We want the same driver every day!". What about picking-up dangerous goods?
  3. Does the resource already have overtime?
  4. Is the resource's geographical location close enough to the node to reach the node in time?
  5. Does the route after optimization look convincing?

Preparation

Make sure you have imported JOpt either as dependency or as a jar file into your project. Please refer to getting started for help.

The following imports are used in this tutorial:

Click to show imports.
/*
 * Other imports - Java and third-party
 */
import static java.time.Month.MAY;
import static tec.units.ri.unit.MetricPrefix.KILO;
import static tec.units.ri.unit.Units.METRE;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.time.Duration;
import java.time.ZoneId;
import java.time.ZonedDateTime;
import java.util.ArrayList;
import java.util.List;
import java.util.Properties;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;


import javax.measure.Quantity;
import javax.measure.quantity.Length;
import tec.units.ri.quantity.Quantities;

/*
 * JOpt imports
 */
import com.dna.jopt.framework.body.IOptimization;
import com.dna.jopt.framework.body.Optimization;
import com.dna.jopt.framework.exception.caught.InvalidLicenceException;
import com.dna.jopt.framework.outcomewrapper.IOptimizationResult;
import com.dna.jopt.member.unit.hours.IWorkingHours;
import com.dna.jopt.member.unit.hours.IOpeningHours;
import com.dna.jopt.member.unit.hours.WorkingHours;
import com.dna.jopt.member.unit.hours.OpeningHours;
import com.dna.jopt.member.unit.hours.TimeWindow;
import com.dna.jopt.member.unit.node.INode;
import com.dna.jopt.member.unit.node.geo.TimeWindowGeoNode;
import com.dna.jopt.member.unit.resource.CapacityResource;
import com.dna.jopt.member.unit.resource.IResource;
import helper.ExampleLicenseHelper;

Nodes

There are multiple different subtypes of nodes. They share the property that all of them can be visited by a resource. However, in this beginner tutorial, we concentrate on a so-called TimeWindowGeoNode which itself is implementing the interface INode .

Parameters of a TimeWindowGeoNode

A TimeWindowGeoNode need the following input parameters to be defined:

  1. A unique node id as String.
  2. A geographical coordinate with latitude and longitude where the node is located.
  3. A list of opening hours when the node can be visited.
  4. A visit duration defining the time a task at the node needs to get done.
  5. A relative importance value as Integer.

The unique Id of an element:

Each element (not only Nodes) need a unique Id used for identifying the node.

Geo-Coordinate

In the easiest version, a geo-coordinate is defined via two double values for latitude and longitude:

// Geo-coordinate of Cologne in Germany
double latitude  = 50.9333;
double longitude = 6.95;

OpeningHours

A node can hold a list of OpeningHours, where each hour is mainly representing a time window which a start and an end. An OpeningHours is implementing the interface IOpeningHours which is extending the interface IDutyHours.

Defining a start and an end:

ZonedDateTime start 
    = ZonedDateTime.of(2020, MAY.getValue(), 7, 8, 0, 0, 0, ZoneId.of("Europe/Berlin"));

ZonedDateTime end = 
    ZonedDateTime.of(2020, MAY.getValue(), 7, 17, 0, 0, 0, ZoneId.of("Europe/Berlin"));

Constructing an OpeningHour - Version 1: It is possible to use the variables start and end as constructor input.

IOpeningHours firstHour = new OpeningHours(start, end);

Constructing an OpeningHour - Version 2: We can also define a TimeWindow object first, and construct the hour using it.

TimeWindow secondTimeWindow = new TimeWindow(start,end);

Creating the OpeningHours object:

IOpeningHours secondHour = new OpeningHours(secondTimeWindow);

Constructing a list of OpeningHours:

List<IOpeningHours> myOpeningHours = new ArrayList<>();
myOpeningHours.add(oneHour);
myOpeningHours.add(anotherHour);

Visit duration

When visiting a node, usually a particular task has to be performed, which takes a certain amount of time.

Duration visitDuration = Duration.ofMinutes(20);

Importance

As we are usually talking about real-life problems, violations most often unavoidable. For example, we have two nodes, and we are not able to visit both of them in time. However, we can visit at least one of them in time. A node with higher importance has a lower likeliness of getting violated. It has to be kept in mind that the concept of importance is relative. Meaning, a high value for the importance of a node only affects when there also nodes available that have lower importance. Moreover, if all nodes have the same very high importance value, for the optimizer, it is the same, as assigning the equal small importance value to all of them.

Finally, we construct the Node

The default constructor

 INode koeln = new TimeWindowGeoNode("Cologne", latitude, longitude, myOpeningHours, visitDuration, 1);

Resources

There is one primary type of a resource the so-called CapacityResource which itself is implementing the interface IResource .

Parameters of a CapacityResource

A CapacityResource need the following input parameters to be defined:

  1. A unique resource id as String.
  2. A geographical coordinate with latitude and longitude where the resource is located.
  3. A list of working hours when the resource is allowed to be utilized.
  4. The maximal working time for the resource.
  5. The maximal driving distance for the resource

The unique Id of an element:

Each resource needs a unique Id used for identifying it (for example, John).

Geo-Coordinate

In the easiest version, a geo-coordinate is defined via two double values for latitude and longitude:

// Geo-coordinate of Cologne in Germany
double latitude  = 50.9333;
double longitude = 6.95;

WorkingHours

A WorkingHours is implementing the interface IWorkingHours which is extending the interface IDutyHours.

Note: WorkingHours and OpeningHours share the same interface IDutyHours.

Creating a working hour pretty much equals the process of creating an opening hour, after creating a start- and endpoint (compare to OpeningHours):

IOpeningHours firstHour = new OpeningHours(start, end);

or

TimeWindow secondTimeWindow = new TimeWindow(start,end);
IOpeningHours secondHour = new OpeningHours(secondTimeWindow);

and finally

List<IWorkingHours> myWorkingHours = new ArrayList<>();
myWorkingHours.add(oneHour);
myWorkingHours.add(anotherHour);

Maximal working time

Each resource needs a maximal working time definition. This definition serves more or less as a guideline for the optimizer. For example, assigning a maximal working time of 8 hours means the resource should work 8 hours within each of the predefined working hours. Of course, it can happen that the optimizer finds a solution in which one or multiple resources show overtime (maximal working time is NOT a hard constraint).

Duration maxWorkingTime = Duration.ofHours(10);

Info

The WorkingHours object has a start and an end. The maximal working time definition is independent of the predefined start and end. Moreover, the start and end can be seen as a frame for the maximal working time definition. This definition makes especially sense in case the use of a flexible start time for a resource is used.


Maximal distance

Each resource needs a maximal distance definition. This definition serves more or less as a guideline for the optimizer. For example, assigning a maximal distance of 500 kilometers means the resource should not drive more than 500 kilometers within each of the predefined working hours. Of course, it can happen that the optimizer finds a solution in which one or multiple resources show over-distance (maximal distance is NOT a hard constraint).

Quantity<Length> maxDistance =  Quantities.getQuantity(500, KILO(METRE));

Finally, we can construct the Resource

The resource can be constructed by providing the discussed arguments by:

 IResource koeln = new CapacityResource("John", latitude, longitude,
    maxWorkingTime, maxDistance, johnWorkingHours);

Element connections

A NodeEdgeConnectorItem defines the distance and the driving time between two elements. Elements are either nodes or resources. By default, JOpt.TourOptimizer expects a list of connections as user-input. When doing an optimization run, connections can be optionally provided. In case a connection is missing, or even no connections are provided in the first place, connections will be auto-calculated based on the haversine formula.

In the following, we create two connections between two elements (Cologne and Munich). Precisely, we create a connection from Cologne to Munich and a connection from Munich to Cologne. As back and force connections are not necessarily symmetric; usually, two elements are resulting in two connections that need to be defined:

 INodeConnectorItem connectionCologneMunich = new NodeEdgeConnectorItem();
    connectionCologneMunich.setFromOptimizationElement(cologne);
    connectionCologneMunich.setToOptimizationElement(munich);
    connectionCologneMunich.setDistance(Quantities.getQuantity(600, KILO(METRE)));
    connectionCologneMunich.setDrivingTime(Duration.ofMinutes(240));

 INodeConnectorItem connectionMunichCologne = new NodeEdgeConnectorItem();
    connectionMunichCologne.setFromOptimizationElement(munich);
    connectionMunichCologne.setToOptimizationElement(cologne);
    connectionMunichCologne.setDistance(Quantities.getQuantity(580, KILO(METRE)));
    connectionMunichCologne.setDrivingTime(Duration.ofMinutes(220));

 // Define a list for the connections
 List<INodeConnectorItem> connectionItems = new ArrayList<>();

 connectionItems.add(connectionCologneMunich);
 connectionItems.add(connectionMunichCologne);

For providing the connections, the connections are added to an INodeEdgeConnector that serves as wrapper object, holding the connections:

 // Create a connector
 INodeEdgeConnector myNodeConnector = new NodeEdgeConnector();

 // Add connections to connector
 myNodeConnector.putNodeConnections(connectionItems);

 // Set NodeEdgeConnector
 optimization.setNodeConnector(myNodeConnector);

For further information, please visit our age about the Edge Connector.


Properties for the optimization run

For tuning the optimization for different use-cases, it is possible to provide a set of optimization properties.

Possible problems that need tuning:

  • The optimization takes too long. How do I tune the number of iterations?

  • I would like the optimizer to put more force on solving late-violations, occurring at nodes, instead of tuning the maximal allowed working time of resources.

  • I would like to skip some optimization steps.

  • ...and many more


Please visit our beginner example First optimization with JOpt for Java.

For further information, please visit our page about Optimization Properties.


License for the optimization

For running an optimization, a license is required, in case you use more than ten elements (including nodes and resources). The license will be provided as a JSON definition. In case you run the optimizer as a dependency, you can save this definition as a text file and set it on startup or as String.

 // Via String
 myOpti.setLicenseJSON(myJsonLicenseString);

 ...

 // Or via file
 myOpti.setLicenseJSON(myJsonLicenseFile);

Example of how a license can look like:

{
  "version" : "7.4",
  "identifier" : "TEST-",
  "description" : "Key provided to you@company.com by DNA evolutions GmbH",
  "contact" : "you@company.com",
  "modules" : [ {
    "Module:" : "Date",
    "creation" : "2020-05-25",
    "due" : "2024-05-08"
  }, {
    "Module:" : "Elements",
    "max" : 100
  } ],
  "key" : "TEST-AVERYUNIQUEKEY"
}

Warning

Changing any JSON-key (deleting, modifying, or adding) of the license will deactivate the license. The only allowed modification is a formating step, like prettifying the JSON.

In case you are using the docker version of JOptTourOptimizer, you will have to send this JSON definition along with your request.

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 ©