First optimization with JOpt for Java

Table of contents


General info

In this tutorial, we are going to create our first optimization definition. The problem which we try to solve consists of several nodes across Germany which we would like to visit with a resource called Jack. Please also refer to the previous basic elements tutorial.


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.


Preparation - Set up the example file

In the first step, we create a new file called FirstOptimizationExample.java within the package package com.dna.jopt.touroptimizer.java.examples.basic.firstoptimization_01. Further, we extend our example from Optimization. Also, we create a main() and an example() method. In the following, the initial source code for the example is defined, as well as all imports we need for this tutorial. The different parts we are going to create are already lined out as numbered comments (1) - (5) inside the example() method.

Press to expand or close code
package com.dna.jopt.touroptimizer.java.examples.basic.firstoptimization_01;

import static tec.units.ri.unit.MetricPrefix.KILO;
import static tec.units.ri.unit.Units.METRE;
import static java.time.Month.MAY;

import tec.units.ri.quantity.Quantities;

import javax.measure.Quantity;
import javax.measure.quantity.Length;

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 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.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;

public class FirstOptimizationExample extends Optimization {

    public static void main(String[] args) throws InterruptedException, ExecutionException, InvalidLicenceException {
        new FirstOptimizationExample().example();
    }

    public void example() throws InterruptedException, ExecutionException, InvalidLicenceException {
      // Will be filled out as part of this tutorial

      // Setting properties, adding all elements, and attaching to observables
      //    (1) Adding properties

      //    (2) Adding nodes

      //    (3) Adding resources

      //    (4) Attach to Observables

      // Starting the optimization via Completable Future
      // and presenting the result
      //    (5) Starting the optimization and presenting the result

    }


}


(1) Adding properties

By default, JOpt can start without adding any properties. However, to define a fully functional optimization with a desired convincing outcome, using settings is of great help. Please refer to Optimization Properties for a list of possible optimization-settings. In the following, we create a static method that adds some settings on an optimization instance. Later on, this method will be added to our example file.

  private static void addProperties(IOptimization opti) {

     // Create an empty properties object
    Properties props = new Properties();

    props.setProperty("JOpt.Algorithm.PreOptimization.SA.NumIterations", "10000");
    props.setProperty("JOptExitCondition.JOptGenerationCount", "2000");

    // Adding the properties to the optimization
    opti.addElement(props);
  }

What we have done:

  • JOpt.Algorithm.PreOptimization.SA.NumIterations: By default, an algorithm called Simulated Annealing is used. We adjusted this algorithm to used a total of 10,000 iterations. Usually, this number should be in the order of about half a million (the default value) and even higher.
  • JOptExitCondition.JOptGenerationCount: One standard algorithm which is used is Genetic Evolution. The generation count defines how many iterations we want to use. Precisely, it describes how many subsequent generations are used. The value should be in the order of several thousand (the default value is 10,000).

Adding the method to our Example method:

Now we simply copy the method addProperties() to our class body. Further, we add FirstOptimizationExample.addProperties(this); in section (1).

Press to expand or close code
    .
    .
    .

    public void example() throws InterruptedException, ExecutionException, InvalidLicenceException {
      // Will be filled out as part of this tutorial

      // Setting properties, adding all elements, and attaching to observables
      //    (1) Adding properties
      FirstOptimizationExample.addProperties(this);

      //    (2) Adding nodes

      //    (3) Adding resources

      //    (4) Adding resources

      //    (5) Attach to Observables

      // Starting the optimization via Completable Future
      // and presenting the result
      //    (6) Starting the optimization and presenting the result

    }

    private static void addProperties(IOptimization opti){
        .
        .
        .
    }

    .
    .
    .

Info

As we extended our class from Optimization the argument this refers to an optimization instance.


(2) Adding nodes

In the following, we define some nodes to be visited. Each of the nodes has a different position within Germany. Further, for the sake of simplicity, all nodes have the same opening hours, the same required visit duration, and importance.

  • OpeningHours: The 6th and 7th of May between 8 in the morning and 5 in the afternoon.
  • VisitDuration: 20 minutes
  • Importance: 1

For adding the elements to the optimization, we define a static method called addNodes(IOptimization opti). Each of the nodes is added within the method via opti.addElement(someNode); separately.

Press to expand or close code
 private static void addNodes(IOptimization opti) {

    List<IOpeningHours> weeklyOpeningHours = new ArrayList<>();
    weeklyOpeningHours.add(
        new OpeningHours(
            ZonedDateTime.of(2020, MAY.getValue(), 6, 8, 0, 0, 0, ZoneId.of("Europe/Berlin")),
            ZonedDateTime.of(2020, MAY.getValue(), 6, 17, 0, 0, 0, ZoneId.of("Europe/Berlin"))));

    weeklyOpeningHours.add(
        new OpeningHours(
            ZonedDateTime.of(2020, MAY.getValue(), 7, 8, 0, 0, 0, ZoneId.of("Europe/Berlin")),
            ZonedDateTime.of(2020, MAY.getValue(), 7, 17, 0, 0, 0, ZoneId.of("Europe/Berlin"))));

    Duration visitDuration = Duration.ofMinutes(20);

    int importance = 1;

    // Define some nodes
    INode koeln =
        new TimeWindowGeoNode("Koeln", 50.9333, 6.95, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(koeln);

    INode essen =
        new TimeWindowGeoNode("Essen", 51.45, 7.01667, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(essen);

    INode dueren =
        new TimeWindowGeoNode("Dueren", 50.8, 6.48333, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(dueren);

    INode nuernberg =
        new TimeWindowGeoNode("Nuernberg", 49.4478, 11.0683, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(nuernberg);

    INode heilbronn =
        new TimeWindowGeoNode("Heilbronn", 49.1403, 9.22, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(heilbronn);

    INode wuppertal =
        new TimeWindowGeoNode("Wuppertal", 51.2667, 7.18333, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(wuppertal);

    INode aachen =
        new TimeWindowGeoNode("Aachen", 50.775346, 6.083887, weeklyOpeningHours, visitDuration, importance);
    opti.addElement(aachen);
  }

Adding the method to our Example method:

Now we simply copy the method addNodes() to our class body. Further, we add FirstOptimizationExample.addNodes(this); in the section (2) (compare to (1) Adding properties).


(3) Adding resources

Each node needs to be visited by somebody. In our case, this somebody is a resource called "Jack from Aachen". For simplicity, we only add a single resource to our optimization problem. Jack has the following properties:

  • WorkingHours: The 6th and 7th of May between 8 in the morning and 5 in the afternoon.
  • Maximal working time (per working hour): 9 hours
  • Maximal distance (per working hour): 1200 km
  • Starting location: Aachen (latitude: 50.775346, longitude: 6.083887)

For adding Jack to the optimization, we define a static method called addResources(IOptimization opti). Jack is added within the method via opti.addElement(jack); .

Press to expand or close code

   private static void addResources(IOptimization opti) {

    List<IWorkingHours> workingHours = new ArrayList<>();
    workingHours.add(
        new WorkingHours(
            ZonedDateTime.of(2020, MAY.getValue(), 6, 8, 0, 0, 0, ZoneId.of("Europe/Berlin")),
            ZonedDateTime.of(2020, MAY.getValue(), 6, 17, 0, 0, 0, ZoneId.of("Europe/Berlin"))));

    workingHours.add(
        new WorkingHours(
            ZonedDateTime.of(2020, MAY.getValue(), 7, 8, 0, 0, 0, ZoneId.of("Europe/Berlin")),
            ZonedDateTime.of(2020, MAY.getValue(), 7, 17, 0, 0, 0, ZoneId.of("Europe/Berlin"))));

    Duration maxWorkingTime = Duration.ofHours(9);
    Quantity<Length> maxDistanceKmW = Quantities.getQuantity(1200.0, KILO(METRE));

    IResource jack =
        new CapacityResource(
            "Jack from Aachen", 50.775346, 6.083887, maxWorkingTime, maxDistanceKmW, workingHours);
    opti.addElement(jack);
  }

Adding the method to our Example method:

Now we simply copy the method addResources() to our class body. Further, we add FirstOptimizationExample.addResources(this); in the section (3) (compare to (1) Adding properties).


(4) Attaching to observables

Of course, we would like to keep track of the running optimization. Usually, we are also interested in getting warnings, statuses, and error messages from the optimizer. For this purpose, JOpt provides different Replay-Subjects to which a user can subscribe.

Info

It is possible to create multiple subscriptions to a single event source.

In the following, we create a static method attachToObservables(IOptimization opti) that will be used to subscribe to different optimization events (progress, warning, status, and error). Please refer to basic events for further information.

Press to expand or close code
  private static void attachToObservables(IOptimization opti) {

    opti.getOptimizationEvents()
        .progressSubject()
        .subscribe(
            p -> {
              System.out.println(p.getProgressString());
            });

    opti.getOptimizationEvents()
        .warningSubject()
        .subscribe(
            w -> {
              System.out.println(w.toString());
            });

    opti.getOptimizationEvents()
        .statusSubject()
        .subscribe(
            s -> {
              System.out.println(s.toString());
            });

    opti.getOptimizationEvents()
        .errorSubject()
        .subscribe(
            e -> {
              System.out.println(e.toString());
            });
  }

For consuming our events, we simply print them out inside each of the lambda bodies.

Adding the method to our Example method:

Now we simply copy the method attachToObservables() to our class body. Further, we add FirstOptimizationExample.attachToObservables(this); in the section (4) (compare to (1) Adding properties).


(5) Starting the optimization and presenting the result

Finally, we are ready to run our optimization. For this purpose, we first ask the optimization instance to provide a completable future by calling opti.startRunAsync(). In the next step, we have to perform a blocking call via get() on the future object, resulting in the start of the optimization. After the optimization is done, we get an optimization result that we print out.

Warning

Extracting the completable future itself does not start the optimization process.

In the following, we create a static method startAndPresentResult(IOptimization opti) which is used to start the optimization and print out the result.

private static void startAndPresentResult(IOptimization opti) throws 
    InvalidLicenceException, InterruptedException, ExecutionException {

    // Extracting a completable future for the optimization result
    CompletableFuture<IOptimizationResult> resultFuture = opti.startRunAsync();

    // It is important to block the call, otherwise optimization will be terminated
    IOptimizationResult result = resultFuture.get();

    // Presenting the result
    System.out.println(result);
  }

Adding the method to our Example method:

Now we simply copy the method startAndPresentResult() to our class body. Further, we add FirstOptimizationExample.startAndPresentResult(this); in section (5) (compare to (1) Adding properties).

After adding this last part, the example() method looks as follows:

Press to expand or close code

  public void example() throws InterruptedException, ExecutionException, InvalidLicenceException {

    // Will be filled out as part of this tutorial

    // Setting properties, adding all elements, and attaching to observables
    //    (1) Adding properties
    FirstOptimizationExample.addProperties(this);

    //    (2) Adding nodes
    FirstOptimizationExample.addNodes(this);

    //    (3) Adding resources
    FirstOptimizationExample.addResources(this);

    //    (4) Attach to Observables
    FirstOptimizationExample.attachToObservables(this);

    // Starting the optimization via Completable Future
    // and presenting the result
    //    (5) Starting the optimization and presenting the result
    FirstOptimizationExample.startAndPresentResult(this);

  }

Executing our example:

When running our example, we can track the optimization output in a console.

Example

Screenshot


Analyzing the result

In our example, we use the internal toString() method of the class OptimizationResult to get a result representation. Of course, it is possible to extract the result object itself and process it in the desired way (get more information). However, it is recommended (if possible) to save the output of the result via toString(), as it allows for easier debugging later on.

Analyzing the result header

Let's first inspect the header of the result, before we look at a single route and even node results. The resulting header condenses different individual route-results in overview numbers. For example, the total time spend by all resources (driving, working, idling) is about 15 hours in our example:

-------------------------------- --------------------------
--------------------- RESULTS -----------------------------
----------------- -----------------------------------------
 Number of Route         : 2
 Number of Route (sched.): 2
 Total Route Elements    : 8
 Total cost              : 2865.4956477605183
-----------------------------------------------------------
 Total time        [h]   : 15
 Total idle time   [h]   : 0
 Total prod. time  [h]   : 2
 Total tran. time  [h]   : 13
 Total distance    [km]  : 1036
 Termi. time       [h]   : 4
 Termi. distance   [km]  : 390
  • Number of Route: The total number of routes of the problem. Each route represents a single workingHours object of a single resource. In our example, we have one resource called Jack with two working hours; therefore the number of total routes is two.
  • Number of Route (sched.): The total number of routes that were scheduled. Here, scheduled means, routes that carry nodes.
  • Total Route Elements: The total number of elements, including nodes and resources.
  • Total cost: JOpt is using a cost assessment strategy to define which result is better compared to another result. For comparing results, each result gets an abstract cost value (the figure of merit) where a lower cost is indicating a better result.
  • Total time: The total time spent by all resources (driving, working, idling).
  • Total idle time: The total accumulated time the resources wait, for example, because a node is closed and opens in 30 minutes.
  • Total prod. time: The total accumulated productive time is the time the resources are working on all nodes.
  • Total tran. time: The total accumulated time the resources need to move from one location to another.
  • Total distance: The total accumulated distance the resources need to move from one location to another.
  • Termi. time: The total accumulated time the resources need to move from the last node of a route to their home locations.
  • Termi. distance: The total accumulated distance the resources need to move from the last node of a route to their home locations.

Analyzing a route result header

Each route has its route result header. This header contains some useful condensed route information. For the sake of simplicity, some parts are skipped.

-----------------------------------------------------------
Route information
RouteId                : 0
Resource               : Jack from Aachen
Closed route           : true
Defined WorkingHours   : 06.05.2020 08:00:00 - 06.05.2020 17:00:00 (Europe/Berlin)
Effective Route Start  : 06.05.2020 08:00:00 (Europe/Berlin)
Effective Route Stop   : 06.05.2020 12:32:00 (Europe/Berlin)
WorkingHours Index     : 0
-----------------------------------------------------------
Route cost             : 249.71761948307574
Route time       [min] : 272
Transit time     [min] : 172
Productive. time [min] : 100
Idle time        [min] : 0
Route Distance   [km]  : 227.05
Termi. time      [min] : 74
Termi. distance  [km]  : 98.957
Start Id               : Jack from Aachen
Termination Id         : Jack from Aachen
  • Route id: Each route has a unique route id. The route-id is an integer value.
  • Resource: The resource that owns the route.
  • Closed route: Each route has a start and a termination element. Usually, the start and termination element is the resource's home location. In the case of a non-closed route, the route does not have a termination element. Moreover, the effective termination element becomes the last node of the route.
  • Defined WorkingHours: The working time of the resource connected to this route.
  • Effective Route Start: The time the resource start working. By default, this is the start of the corresponding working hour.
  • Effective Route Stop: The time the resource is done with the route.
  • WorkingHours Index: Each resource can carry multiple working hours as a list. Each route is connected to one of the working hours objects from that indexed list.
  • Route cost: The result of the cost assessment for this particular route.
  • Route time: The route-specific value accounting to "Total time".
  • Transit time: The route-specific value accounting to "Total tran. time".
  • Productive. time: The route-specific value accounting to "Total prod. time ".
  • Idle time: The route-specific value accounting to "Total idle time".
  • Route Distance: The route-specific value accounting to "Total distance".
  • Termi. time: The route-specific value accounting to "Termi. time" in the result header.
  • Termi. distance: The route-specific value accounting to "Termi. distance" in the result header.
  • Start Id: The id of the start element of the route.
  • Termination Id: The id of the termination element of the route.

Analyzing a route

A route can be seen as an ordered collection of nodes, belong to a particular resource for an individual working hours object. As each route consist of nodes which are getting visited, the planned arrival, departure, along with possible violations for each node is the most interesting part of the optimization result.

0.0 Dueren / 
Arrival: 06.05.2020 08:21:21 (Europe/Berlin) ,
Departure: 06.05.2020 08:41:21 (Europe/Berlin) / 
Duration: 20 [min] / 
Driving: 21.36 [min], 28.201 [km]

0.1 
Koeln / 
Arrival: 06.05.2020 09:08:36 (Europe/Berlin) , 
Departure: 06.05.2020 09:28:36 (Europe/Berlin) / 
Duration: 20 [min] / 
Driving: 27.25 [min], 35.966 [km]

0.2 
Wuppertal / 
Arrival: 06.05.2020 09:59:17 (Europe/Berlin) , 
Departure: 06.05.2020 10:19:17 (Europe/Berlin) / 
Duration: 20 [min] / 
Driving: 30.67 [min], 40.49 [km]

0.3 
Essen / 
Arrival: 06.05.2020 10:37:02 (Europe/Berlin) , 
Departure: 06.05.2020 10:57:02 (Europe/Berlin) / 
Duration: 20 [min] / 
Driving: 17.75 [min], 23.433 [km]

0.4 
Aachen / 
Arrival: 06.05.2020 12:12:00 (Europe/Berlin) , 
Departure: 06.05.2020 12:32:00 (Europe/Berlin) / 
Duration: 20 [min] / 
Driving: 74.97 [min], 98.957 [km]

Let's evaluate in detail the result for Koeln (Engl. Cologne). The corresponding values/variables of the node result are listed in the following table:

Variables Result values for Koeln
"RouteId" . "VisitngIndex" 0.1
"Element Id" Koeln
ZonedDateTime Arrival: 06.05.2020 09:08:36 (Europe/Berlin)
ZonedDateTime Departure: 06.05.2020 09:28:36 (Europe/Berlin)
Visit duration Duration: 20 [min]
Driving time from the previous element Driving: 27.25 [min]
Driving distance from the previous element Driving: 35.966 [km]


Download the example

To directly download the class described in this tutorial, click here.