Skip to content

Why DNA-Evolutions' TourOptimizer - Special Features

What makes JOpt-TourOptimizer unique? Find out!

In contrast to most other Optimization-Suites for Tour-Optimization, we provide some (to our best knowledge) unique features that we developed over the recent years in close collaboration with our customers. These features are well designed, tested, and utilized in production systems.

Beside the well-known standard features (e.g., Service-level agreement matching (SLA) and skills) found in the area of Traveling-Salesman Optimizers, we would like to present our most outstanding features:

What makes us unique and the ideal fit for your business:

Overview

Guaranteed matching SLAs - CapturedNode

One of the most challenging tasks is to avoid SLA violations. In JOpt-TourOptimizer we call an SLA of a Node an OpeningHour with a particular TimeWindow. The related concept of a Resource is called WorkingHours.

Usually, Optimizers try to position Nodes most optimally, sometimes even violating SLAs depending on the cost-benefit ratio. But how to convince an Optimizer that a specific Node condition must not be violated under any circumstances, e.g. due to legal issues, contractual penalties or contractual agreements? Due to the nature of an optimization process, it is hard to tell the Optimizer that being 10 minutes late at one Node is fine, but for another Node, it is not acceptable.

For this purpose, we extended our Node object - called a CapturedNode or Pillar. The OpeningHours of a CapturedNode cannot be violated. Optionally a mandatory Resource can be attached to a CapturedNode, making sure the CapturedNode is visited by that specific Resource.

Example

Please visit our GitHub example section for an implementation example of a CapturedNode.

In the following examples, we take a look at the behavior of a CapturedNode in different use- and conflict-cases.

Case One: The CapturedNode acts like a normal Node

In the usual case matching OpeningHours to the WorkingHours of a Resource is unproblematic. Meaning, visiting CapturedNodes and Nodes in the same route are not conflicting, and the CapturedNodes behave like Nodes (Figure - CapturedNode 1).

John can visit both Nodes (light blue) within their OpeningHours (SLAs) and finish the tasks to be done (dark blue ). Fitting the CapturedNode (orange) is not causing any violations.

Screenshot

Figure - CapturedNode 1

Case Two: Conflict of a CapturedNode with a Node - Solved by moving a Node

In some cases, visiting a Node before a CapturedNode would lead to a late-violation arising at the CapturedNode (Figure - CapturedNode 2 - left). The Optimizer recognizes a potential late-violation and solves it by repositioning the Node (Figure - CapturedNode 2 - right).

Screenshot

Figure - CapturedNode 2

Case Three: Conflict of a CapturedNode with a Node - Solved via late-violation at the Node

Sometimes a Node and a CapturedNode have a conflict in that sense that only one of them can be visited without a late -violation. As by definition, we do not want to allow any late-violations at CapturedNodes. Therefore we have to accept a late-violation at the Node (Figure - CapturedNode 3).

Screenshot

Figure - CapturedNode 3

Case Four: Conflict of a CapturedNode with a Node - Solved by utilizing an additional Resource

In bigger problem sets more Resources are available usually. Often, the most optimized way to solve a late-violation is to move a "bad" Node to another Resource. Which Node stays within John's route depends on different aspects such as driving-times, required skills or the (optional) mandatory Resource set. (Figure - CapturedNode 4).

Screenshot

Figure - CapturedNode 4

Case Four: Conflict of a CapturedNode with a Node - Solved by removing a CapturedNode

Assuming John is the only available Resource for visiting two CapturedNodes that are conflicting which each other, the only possible solution is to remove one of the CapturedNodes. This example illustrates the definition of CapturedNodes in an extreme case: SLAs of CapturedNodes cannot be violated under any circumstances. If no other solution is viable, a CapturedNode contract is rather canceled than violated. (Figure - CapturedNode 5). Screenshot

Figure - CapturedNode 5

Conclusion and Usage

In general, using CapturedNodes is a powerful concept, as it can guarantee to match SLAs. This guarantee is primarily ensured by the architecture of the Optimizer and not by the Optimization process itself. However, a CapturedNode is limiting the optimization process as the available optimization space shrinks. Therefore, we are recommending using CapturedNodes as a substitute for normal Nodes only in case a violation would lead to legal issues or other high priority business problems and should NOT be used for, say a hairdressing appointment.

The intrinsic behavior of the Optimizer is highly tuned to achieve SLA matching for Nodes. Using CapturedNodes guarantees matching SLAs except for the unlikely occasions where exclusive problems arise. In these seldom cases skipping a CapturedNode serves as damage control.

Info

In times in which online-meetings became common, it is important to note that both Nodes and CapturedNodes can also be defined as events without any geographical location.

Hard Constraints - Violations not allowed

The previous section about CapturedNodes, from a high-level perspective, described hard constraints of matching TimeWindows. There potentially are other conditions in many business-cases that need to be matched no matter how sub-optimal an optimization result can become. Some jobs might require a particular qualification - for example, a truck driver who has to pick up dangerous goods. A second Resource nearby that has more time, is better located but does not have the qualification is not making the conditions easier to fulfill. Sending the wrong Resource will lead to serious legal issues.

The JOpt-TourOptimizer achieves hard-constraint free solutions by using an attempt based architecture, rather than relying on the optimization process itself. Every possible permutation of the order of Nodes and Resources will lead to a new solution to the initial problem set. Our Optimizer effectively cuts the solution space for invalid solutions. In return, every solution it can find is a valid solution, not necessarily converging or at optimal costs, but not containing any hard constraint violations ** (Figure - HC 1). An iterative process filters out and improves on the best solutions, achieving better and better solutions the longer the optimization process runs.

Screenshot

Figure - HC 1

Example

Please visit our GitHub example section for implementation examples of different hard constrained conditions.

Overnight Stay

In JOpt-TourOptimizer, a Resource can have multiple predefined WorkingHours which contain the time and dates the Resource is allowed to visit Nodes. Each of the WorkingHours is connected to precisely one resulting route object . Usually, a route starts and ends at the Resource's home location. However, sometimes it is preferrable if a Resource is allowed to stay one or multiple nights in a hotel (Figure - ON 1). Further, whether a Resource is allowed to stay outside is a function of the day and the Resource itself. The rule set can be adjusted meticulously. For example, the Resource can be allowed to have a maximum of two overnight stays per week (or any other time unit), whereas Mondays and Fridays are not allowed.

Screenshot

Figure - ON 1

Example

Please visit our GitHub example section for an implementation example of overnight stays.

Flexible Start Time (Positive and Negative)

Flexible start time is a concept for Resources to reduce either idle time (starting the WorkingHours later), or to arrive at a Node when it opens (starting the WorkingHours earlier). Effectively, the WorkingHours-start of a Resource becomes a flexible TimeWindow itself, instead of a fixed spot in time - like 8 am.

Example

Please visit our GitHub example section for an implementation example of FlexTime.

Positive FlexTime

Each Resource has a predefined start-time of its WorkingHours. Let's assume this is at 8 am in the morning. If the first Node opens at 10 am, the Optimizer will assign the so-called Idle time to the Resource by default (Figure - FL 1 - top). In practice, it is common that Resources, depending on their schedule , are allowed to start their workdays later. In JOpt-TourOptimizer, this is called positive FlexTime. For each Resource and each of its WorkingHours, a custom positive FlexTime can be assigned.

In Figure - FL 1 - center: John has a FlexTime of one hour. The FlexTime that is assigned to the WorkingHours of a Resource is hard constrained, and it is not possible to use up more than the maximal assigned time. Here, since the time until the Node's OpeningHours and driving time is longer than the positive FlexTime, John utilizes the full one hour of FlexTime and therefore reduces his idling time by one hour.

In Figure - FL 1 - bottom: John has two hours of FlexTime. He uses up 90 minutes of this FlexTime to align his workday to the OpeningHours of the Node and gets rid of the idling time completely. Note, that FlexTime can also be customized so that driving time is not included. If driving time would be excluded from FlexTime in the last example, only 45 minutes of FlexTime would be used. John would start his workday at 9:15 am and use the first 45 minutes of his work to drive to the Node and arrive there at 10 am.

Screenshot

Figure - FL 1

Info

Other custom settings allow a Resource to start working at a Node right away after arrival without having to wait for the Node's OpeningHours to begin. This function is called isWaitOneEarlyArrival.

Negative FlexTime

Negative FlexTime is the counter-concept to positive FlexTime. Let's assume a Node opens at 8 am and the Resource John starts working at 8 am as well. Let's further assume that John needs 30 minutes of driving time to reach the first Node. In this setting, John would reach and start working at the Node at 8:30. However, by assigning a negative FlexTime of up to one hour (defined as "only allowed to be used for driving"), John will effectively start driving at 7:30 am and reaches the Node ready to work at 8 am (Figure - FL 2).

Screenshot

Figure - FL 2

Info

Beside the fact that Nodes can be visited right when they are opening, the usage of negative FlexTime also has a beautifying effect on Gantt plots. Indeed, the result looks more convincing and leads to a higher acceptance.

In Figure - FL 3 - top four Resources are shown. While there are no violations, the Gantt-Plots look quite messy due to the driving times. By assigning a negative FlexTime (Figure - FL 3 - bottom), the first Nodes of each route are nicely stacked and can be visited at the beginning of their OpeningHours. An exception is Bob, who's maximal negative FlexTime is not long enough to reach the first Node when it opens. Negative FlexTime, like positive FlexTime, is hard constrained and cannot be exceeded.

Screenshot

Figure - FL 3

Combining

The concepts of positive and negative FlexTime can be used in combination with one another leading to a flexible TimeWindow for the Resources' WorkingHour start which is used most optimally depending on the circumstances of each particular workday.

Optional Nodes

Usually, every Node is creating cost, increasing the overall cost of the solution. Every additional Node in a solution increases the total cost. However, in pickup and delivery scenarios adding an optional Node can be used to reduce the cost. The Optimizer will decide whether visiting an optional Node is beneficial in terms of the total cost.

In a waste-management-business scenario, optional Nodes (in this case: waste deposits) are added to the optimization in order to provide an opportunity to dump the collected waste. As driving with high load is penalized (increased fuel consumption and potential overload), unloading the waste at an optional Node will decrease the cost.

Figure - OP 1 shows an example of two routes starting from the cities of Stuttgart and Ulm. Within the route beginning at Stuttgart, a Resource is picking up 20 units of waste at the first Node and another 30 units of waste at the second Node. Let's further assume that the maximal loading capacity of the Resource is 50 units of waste . Therefore, the Resource cannot pick up any more waste without getting overloaded. By visiting an optional Node, it is possible to unload the waste before visiting the next Node. Note that the optional Node Freiburg is not visited.

Screenshot

Figure - OP 1

Example

Please visit our GitHub example section for an implementation example of optional Nodes.

Pickup and Delivery (PND) - Manufacturing-Planning

Pickup and delivery (PND) problems are one of the most challenging tasks to solve for any Optimizer, yet they are of critical importance for industries.

Usually, when thinking of PND-Problems there is a customer (Node) that has a request or a supply of goods, and a Resource that tries to serve these demands. In short, solving PND-Problems is about optimal and violations-free exchange of goods between parties.

Here, we would like to describe how JOpt-TourOptimizer can be used to solve a variety of PND-Problems. More specifically, we would like to explore the unique features that allow using our PND-system for solving problems connected to manufacturing-planning of goods besides basic transportation Optimization.

Info

A full explanation of our PND-Module can be found here.

Example

In the following example, we look at a manufacturing-planning PND task. A bakery company has two production sites for bread (Bakery Aachen and Bakery Cologne). These two production sites are located in different cities, and each of them has one employee (a Resource) to supply Supermarkets/Stores (Nodes) with trays of bread. In general, each production site is allowed to provide each Store. However, a Resource's truck can load a maximum of 20 bread trays . "Figure - PND 1" shows an illustration of this setup.

Screenshot

Figure - PND 1

As a bakery does not want to waste bread and on the other hand is interested in finding the most optimal route (keeping timeWindows, short total distance, etc.), we want to allow the Optimizer to do the manufacturing-planning. In other words: The Optimizer decides how much bread each production site fabricates.

For achieving the manufacturing-planning-capability of the Optimizer, we add two optional Nodes. These two optional Nodes act as factories for bread. The factories adjust the number of trays of bread they fabricate automatically based on what is beneficial for solving the overall optimization problem. For simplicity's sake, we locate one factory (Supply Node) close to the Bakery Aachen and one factory (Supply Node) close to the Bakery Cologne. In general, factories can be located at any desired position.

"Figure - PND 2" shows the optimized result for the outlined problem. Bakery Aachen has to produce 10 pallets of bread in its factory and Bakery Cologne has to produce 17 trays of bread in its factory.

Screenshot

Figure - PND 2

Please keep in mind that solving this simple task was relatively easy. When confronted with mixed pickup and delivery problems or problems with a high number of Nodes and multiple constraints, however, the outlined concept proves to be a powerful tool.

Example

Please visit our GitHub example section for an implementation example of supply Nodes.

Defining Territories via ZoneCodes

In reality, Resources are often constrained in some way or form. Either they are bound to geographical territories, the customer might prefer a particular Resource etc. Moreover, territories of the Resources may change on a daily basis. For these kinds of problems, we have developed the concept of ZoneCodes, which in essence works similar to regional postcodes.

Attaching ZoneCodes to Resources and Nodes is a way to tell the Optimizer which Resources can potentially be scheduled to visit the Nodes with the matching ZoneCodes. To allow as much finetuning as possible, the ZoneCodes can be defined for each WorkingHours of a Resource. It is also possible to allow a Resource to visit multiple ZoneCodes.

Conversely, one or multiple ZoneCodes get attached to each Node. Attaching multiple ZoneCodes to a single Node makes particular sense if a Node is geographically positioned at a territory border. In this case, the Optimizer decides which Resource will be scheduled for the smallest additional costs. Figure - ZO 1 shows a typical setup for Zones.

Screenshot

Figure - ZO 1

Attaching ZoneCodes instead of defining abstract territories has the significant advantage that it allows tailoring fine-grained and precise territory-definitions according to the customer's needs. It is possible to integrate small territories within big ones, for example. Further, the concept of ZoneCodes can be hard-constrained if necessary.

Example

Please visit our GitHub example section for an implementation example of UK-PostCodes based on ZoneCodes.

AutoFilter

It can happen during optimizations that only a few Nodes are responsible for most violations caused. One Node might be so far away from all Resources home locations that none of the Resources are able to visit the Node in time, for example. The number of Nodes being too high to fit them inside the available WorkingHours of the Resources is another case in point. Another common problem is that too many Nodes demand a particular Resource as preferred Resource.

During the optimization run, JOpt-TourOptimizer is creating a massive number of parallel solutions. Each solution is representing a full schedule of all Nodes and all Resources. The AutoFilter is designed to analyze each solution regarding the Nodes that have caused a violation.

Figure - AF 1 shows two different solutions for a particular route. One solution performs a right turn. The other solution performs a left turn. As a result, Node D is visited late in Solution One, whereas Node A is visited late in Solution Two. The AutoFilter will assess both solutions and will assign penalty points to Node A AND Node D.

During the optimization, while several solutions are generated, Nodes collect these penalty points. The task of the Autofilter is to exclude Nodes from the optimization that are prone to cause violations. Therefore, if the number of penalty points compared to the number of solutions in which a particular Node is not showing violations is getting too high, said Node is getting filtered out. It is possible to set custom filter reasons in the AutoFilter. It is possible to set the margins for being filtered out. Particular reasons like late- or early-violations can be set to be reasons for being filtered out instantly, for example. Conversely, individual Nodes can be protected from being filtered out at all.

Screenshot

Figure - AF 1

Example

Please visit our GitHub example section for an implementation example of the AutoFilter.

Custom solution

In the first step, when starting an optimization run, a deterministic construction algorithm is used to create a first starting-solution. This starting-solution is further optimized in iterative steps. Creating such a solution is helpful as it shrinks the possible space for desirable solutions.

However, using this construction algorithm is not as flexible as our subsequent optimization algorithms due to its deterministic nature. For particular use-cases, either a custom construction algorithm can be defined (contact us), or you construct a starting solution on your own and provide it to us on start-up. We use a human-friendly JSON definition to save an optimization state. When loading a persisting state, the JSON definition is converted into a custom solution that can be used on start-up.

Example

Please visit our GitHub example section for an implementation example of a custom solution.

Open Assessor

One of the most powerful tools is the OpenAssessor. Even though JOpt-TourOptimizer already has a lot of predefined restrictions, sometimes end-customers require custom restrictions. The OpenAssessor allows injecting custom restrictions into the optimization process.

Below, we look at two conditions that show the impressive potential of this tool.

Example

Please visit our GitHub example section for an implementation example of the OpenAssessor.

Custom Condition on Node-Level

An end-customer requests that each Node should be visited as early as possible within its OpeningHours. Take a problem set with two Nodes, for example. Node A is open from 8 am to 5 pm and Node B is available from 9 am to 5 pm. A Resource needs one hour of driving time to reach any of these Nodes. Figure - OA 1 shows an illustration of the example.

By default, the Optimizer can either schedule Node A or Node B first, resulting in exactly the same cost as both Nodes would be visited at 9 am by the Resource, and no late-, early-, or idle-time is arising.

However, we prefer the Nodes to be visited as early as possible during their OpeningHours. As Node A is already open for one hour at the time the Resource would arrive, we prefer Node A to be visited before Node B * (Figure - OA 1 - left*).

Screenshot

Figure - OA 1

By defining a custom restriction, it is possible to tell the Optimizer that particular order of Nodes are preferred , resulting in a powerful tool to meet your customers' requirements.

To further show the impressive potential of this feature, we added a fun-example in our GitHub-section where all Nodes with Node-Ids starting with a capital "M" need to be visited before 11 am.

Custom Condition on Route-Level

Custom restrictions can also be made on the route level. We could, for example, tell the Optimizer to prefer routes with an odd number of Nodes (Figure - OA 2).

Screenshot

Figure - OA 2

With the OpenAssessor we can formulate this restriction and inject it into the Optimizer.

Clustering Construction - A good base for Optimization

JOptTourOptimizer uses a multi-algorithm solving strategy. Meaning, different algorithms are used in direct succession to solve a Tour-Optimization problem where the output of one algorithm is the input of the subsequent algorithm.

By default, in the first step, a deterministic construction algorithm is used to create an initial starting solution (working solution). Even though theoretically, it is not necessary to use a constructed starting solution, it helps to converge faster against a better solution in subsequently executed non-deterministic optimization algorithms.

Indeed, the expectable quality of the solution (utilizing the same processing power for crunching) is highly improved when using construction.

The HybridMultiDimensionalClusteringAlgorithm construction algorithm is suitable for creating a feasible solution for different problem scenarios. Moreover, it became the default construction algorithm used in JOpt-TourOptimizer and is already heavily used worldwide in production. Indeed, it is also used to provide an approximate solution to end customers before doing any optional additional optimization steps.

Clustering Zoom Even

Figure - Phyllotaxis solved by Construction (Click to enlarge)

Info

A full explanation of our Clustering-Construction can be found here.

Closing Words

When visiting our GitHub -examples, you may notice that there are a lot of other features that can be used to support your business. Feel free to explore the examples and contact us if you are missing anything. We are always keen to develop and provide new customer-inspired features.

Authors

A product by dna-evolutions ©