Introducing the JOpt optimization engine

How does JOptTourOptimizer work, what kind of problems can be solved? How can it be utilized?

Introduction video

Watch our introduction video. Click, to open video:

Problem description - Overview

Allocating a set of tasks or shipments to mobile resources is a standard problem for dispatchers. The dispatchers' challenge is to find the right balance of "who should do what" or "who should deliver which shipment".

Once the allocation of the tasks and shipments (to the resources) are done, the set of tour stops must be ordered, ideally, in the most efficient way. For example, an order in which opening hours (at the tour stops) and all additional constraints are met. These constraints, for example, are working- and travel-time regulations, drivers' skills, and transportation rules, personal preferences of both resources and customers, already negotiated and assured appointment times, and many more.

For meeting all these constraints, although some of them may conflict with others while at the same time, the final result should be the most cost-effective one. Cost in our case in an abstract number uniting the costs from traveling-distances, traveling- and working-times, as well as fuel cost and even CO2 emission. Manually, this dispatching work is time-consuming, and reasonable solutions require experience. For huge problem sets, in fact, it is almost impossible to dispatch jobs and resources manually.

Working principle

State of the art algorithms can help to solve big dispatch problem sets and find a convincing solution in a reasonable time.

In our case, we provide a software package called JOpt, containing performance-optimized algorithms and a modern API for user interaction. JOpt takes the given set of resources, jobs, and shipments as well as all the constraints and will return an optimized solution. The optimized solution can be further processed, which will then be given, for example, to the dispatcher on the HMI of your program suite.

By default, the JOpt-TourOptimizer engine uses a powerful combination of construction-algorithms, a simulated annealing algorithm, and a genetic algorithm to find the optimal solution. The genetic algorithm internally uses, roughly spoken, two different kinds of operators. Random Operators hat perform random mutations/crossings as you would find in nature. Furthermore, it uses intelligent Operators. They evaluate a solution before/after modification and remind on LocalSearch Strategies.

Constructing a heuristic starting solution

When using the default JOpt's optimization scheme, the first step of JOpt is to find a suitable starting solution based on all inputs. JOpt takes all the tasks, shipments, and allocates them to the set of resources using a construction algorithm. One of our construction algorithms, for example, originates from the ideas of the savings algorithm, a widely used heuristic algorithm for solving capacitated vehicle routing problems. During this first step of the optimization, a heuristic solution will be achieved by rearranging all the tour stops and allocating them to the resources until finally, an acceptable starting solution is found based on different aspects, for example, the distance between tour-stops. Constraints are avoided by adding additional penalties.

Furthermore, additional weights (as optional user input) can help to modify the optimizer to balance adequately different KPIs for a given problem set. For example, it could be more important to meet agreed appointment times rather than to have minimum traveling times.

Improving the starting solution

Once a first initial solution has been constructed, it can be further optimized by the second step, the simulating annealing algorithm. This algorithm takes the solution from the construction phase and rearranges the tours, and their tour stops sequences in a way to achieve a state with a lower total cost. This algorithm is motivated by physical annealing processes in metallurgy where atoms and crystals are transferred into structures with the lowest energetic state when cooling down from high temperatures.

From a mathematically perspective, this is a probabilistic process modeled in an exponential function to find energetically lower states representing a better solution. The result from this process is usually quite convincing, and simulating annealing is comparable fast end effective. But sometimes simulating annealing tends to stuck in local minima during the optimization process.

Further enhance the quality of the solution

The more complex a problem space is, the more likely it is to end up in an acceptable but not optimal solution. Therefore, in a third step, we feed this solution into a genetic algorithm. The genetic algorithm is a very flexible process suitable for many different kinds of problems. It is simulating the biological process of evolution, trying to find solutions that fit well to a given environment, where the environment here can be understood as the system of constraints, opening hours, working hours, and locations.

In the JOpt-TourOptimizer, genetic evolution is utilized to improve the prior solution found from simulated annealing. Other than in the annealing process, the genetic algorithms develop many parallel solutions that are inherited with few modifications to the next generation of solutions. An elite-concept ensures that the best solutions are always propagated to the next generation. This broader approach can be more time consuming (depending on the initial settings), and the changes from one generation to the next generation can be small with big jumps from time to time.

However, the strength of the attempt lies in the fact that many paths of optimization are explored in parallel. This attempt reduces the danger of getting stuck to a particular solution. Therefore genetic evolution is typically used as the final step of the optimization engine.

We are not fixed - modify it corresponding to your needs

Since some problems may allow skipping one or two of the optimization steps, JOpt-TourOptimizer offers a modifiable optimization scheme where the optimization processes can be tailored to the given problem and allowing a user-defined order of execution. As we are targeting for a modular product, even injecting custom user-algorithms is possible.

Products in Preview

Vehicle routing problems are geographic optimization problems and rely on distance calculation between the tour stops and the resources visiting them. This can be done, by default, on the fly if straight distances as the crow flies are sufficient to find a proper order, or a small user-modification injected into the optimizer is adequate. For those problems where this is not precise enough, distance matrices or driving times matrices between each of the tour stops are required before starting the optimization process. For this pre-phase, DNA offers a preview of the products JOpt-GeoCoder and JOpt-TourPlanner, which both are using OpenStreetMaps data. JOpt-GeoCoder is used for coding and reverse-coding addresses into geo-coordinates and vice versa, which can be used by JOpt-TourPlanner. This data is stored in matrices, or more efficiently in "edge" objects, describing the distances and times, and their relevant variations over the day for further taken by JOpt.TourOptimizer as input during the optimization.

How to use our products

Whereas JOpt-TourOptimizer can be integrated natively as JAVA library into your product and will run in your or your customers' IT infrastructure, JOpt-GeoCoder, and JOpt-TourPlanner, require the installation via a docker-compatible environment.

Furthermore, for cloud-integration, JOpt-TourOptimizer also supports the installation via a docker-compatible environment working flawlessly with GeoCoder, and TourPlanner. All three tools are providing a Swagger compatible REST-API enabling the use of stubs in the user-preferred programming language (including famous ones like C#, Java, JS, Scala, Python, and many more ) to use our tool-chain.

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.