Why DNA-Evolution's TourOptimizer - Special Features

What makes JOptTourOptimizer 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.

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

What makes us unique and the ideal fit four your business.


Overview


Guaranteed matching SLAs - CapturedNode

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

Usually, Optimizers try to position Nodes most optimally. But how to convince an Optimizer that a Node condition should not be violated (even 10 minutes late is not allowed), e.g., due to legal issues or 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. Further, (optionally) you can attach a mandatory Resource to a CapturedNode, making sure the CapturedNode is visited by the right 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

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

John can visit both Nodes (light blue) within their opening hours (SLAs) and finish the task 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 - Solve 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 - Solve via late-violation at 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 a late-violation at a CapturedNode, we have to accept a late-violation at a Node (Figure - CapturedNode 3).

Screenshot

Figure - CapturedNode 3

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

In bigger problem sets, usually, other Resources are available. The most optimized way to solve a late-violation, often, is to move one of a "bad" Node to another Resource. Which Node stays within John's route depends on different aspects like driving-times, is John the mandatory Resources (?), skills, and many more (Figure - CapturedNode 4).

Screenshot

Figure - CapturedNode 4

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

Assuming John is the only available Resource and for visiting two CapturedNodes that are conflicting which each other, the only possible solution is to remove one of the CapturedNodes (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 the CapturedNode as a substitute for normal Nodes only in case a violation would lead to legal issues or other high priority business problems.

Ask yourself, is a hairdressing appointment of a Resource considered to be a CapturedNode? Further, the intrinsic behavior of the Optimizer is highly tuned to achieve SLA matching also for Nodes.

Info

Nodes and CapturedNodes can be both also defined as Events (without a geographical location).


Hard Constraints - Violations not allowed

The previous section about CapturedNodes, from a high-level perspective, describes a hard constraint of matching TimeWindows. Further, there are potentially other conditions in a lot of business-cases that need to be matched no matter how sub-optimal an optimization result can become. For example, think of a truck-driver who needs a particular qualification to pick up some dangerous goods. It doesn't matter that there is another Resource existing (without the qualification) that has more time, is better located, or something else. Sending the wrong Resource will lead to serious legal issues.

The JOpt-TourOptimizer achieves this by using an attempt based on its architecture instead of 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 optimal (high costs), but not containing any hard constraint violations (Figure - HC 1).

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. 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 a Resource should stay one or multiple nights in a hotel (Figure - ON 1). Further, if a Resource should stay outside is a function of the day and the Resource itself. Is it fine to stay at a hotel on particular days? Is the Resource allowed to stay at a hotel in general?

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 (for convenience) this is at 8 am in the morning. What happens if the first Node opens at 10 (?). By default, the Optimizer will assign the so-called Idle time to the Resource (Figure - FL 1 - top). In reality, 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 for each of its WorkingHours, a positive FlexTime can be assigned (which can also be different).

In Figure - FL 1 - center: John has a FlexTime of one hour. The FlexTime that is assigned is hard constrained, and it is not possible to use up more than the maximal assigned time. Here, 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 and therefore, completely, gets rid of the idling time.

Screenshot

Figure - FL 1

Info

It is also possible to define that a Resource starts working at a Node right away after arrival without waiting for the Node to open officially (called isWaitOneEarlyArrival).

Negative FlexTime

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

Info

Negative FlexTime can be used only for driving (default), or for driving AND working on a Node.

Screenshot

Figure - FL 2

Besides 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. There are no violations; however, the Gantt-Plots looks quite messy. By assigning a negative FlexTime (Figure - FL 3 - bottom), the first Nodes of each route are nicely stacked. An exception is Bob, where the maximal negative FlexTime is not high enough to reach the first Node when it opens. Moreover, like positive FlexTime, negative FlexTime is hard constrained and cannot be exceeded.

Screenshot

Figure - FL 3

Combining

Both concepts can be used in parallel leading to a flexible TimeWindow for the Resources' WorkingHour start.


Optional Nodes

Usually, every Node is creating cost and increases the cost of a solution. However, in pick-up and delivery scenarios adding a Node can reduce the cost. The Optimizer will decide if an optional Node is visited or not.

As an example, think of a waste-management-business scenario. Optional Nodes are added to the optimization to provide an opportunity to dump the collected waste. As driving with high load is penalized (high fuel consumption), unloading the waste at an optional Node will decrease the cost. Further, potential overloading can be avoided.

Figure - OP 1 shows an example of two routes (starting from the cities Stuttgart and Ulm). Within the route, beginning at Stuttgart, a Resource is picking up 20 parcels of waste at the first Node and another 30 parcels of waste at the second Node. Let's further assume, the maximal loading capacity of the Resource is 50 parcels of waste. Therefore, the Resource cannot pick up any more of waste without getting overloaded. By visiting an optional Node, it is possible to unload the waste before visiting the next Node. Please 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 hardest tasks to solve for any Optimizer, yet they are critically important for industries.

When thinking of PND-Problems, usually, 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 a desirably optimal violation-free exchange of goods (loads) between two parties (here, a Node, and a Resource).

Here, we would like to describe how JOptTourOptimizer can be used to solve a variety of PND-Problems. Especially, here we would like to explore unique features, for example, a way to use our PND-system for the manufacturing-planning of goods besides basic transportation Optimization.

Info

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

Example

In the following, 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 pallets 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. "Figure - PND 1" shows an illustration of this setup.

Screenshot

Figure - PND 1

As a bakery does not want to waste bread, but on the other hand, is interested in finding the most optimal route (keeping timeWindows, low total distance, etc.), we want to allow the Optimizer to do the manufacturing-planning. Or 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 can act as factories (for bread). The factories adjust the number of pallets of bread they fabricate automatically, based on what is beneficial for solving the overall optimization problem. For simplicity, we locate one factory (Supply Node) close to Bakery Aachen and one factory (Supply Node) close to 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 Bread in its factory, and Bakery Cologne has to produce 17 bread in its factory.

Screenshot

Figure - PND 2

Of course, for the outlined problem, the solution seems quite simple. However, when thinking of mixed pickup and delivery problems or problems with a high number of nodes, and multiple constraints, the outlined concept reveals itself as a powerful tool.

Example

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


Defining territories via ZoneCodes

In reality, often, Resources are bound to territories, for example, because of geographical reasons, the customer is used to a particular Resource or for any other reason. Moreover, territories of the Resources may change on a daily basis.

Attaching ZonesCodes to Resources and Nodes is a way to tell the Optimizer which Nodes should be visited by which Resources. Further, it is possible to define the territory number (or ZoneCode) for each WorkingHours of a Resource. Also, it is possible to tell a Resource that it is allowed to visit multiple different ZoneCodes.

The Nodes get one or even multiple ZoneCodes attached as well. Attaching multiple ZoneCodes to a single Node usually makes sense if a Node is positioned geographically at a territory border, and the Optimizer should decide which Resource should be scheduled. Figure - ZO 1 shows a typical setup for Zones. Please note that the Zones are defined via the ZoneCodes attached to the elements (Nodes and Resources).

Screenshot

Figure - ZO 1

The significant advantage of attaching ZoneCodes instead of defining abstract territories is, that, in general, every customer territory-definition can be met. For example, think of small territories within big territories. 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

During the optimization, it can happen that some Nodes are most often creating violations. For example, one Node that needs to be scheduled is so far away from all Resources' home locations that none of the Resources is able to visit the Node in time. Or the number of Nodes is too high to fit them inside the available workingHours of the Resources.

In huge optimization problem sets, it is sometimes not obvious that on certain days the number of Nodes that need to be scheduled is exceeding the available working time of the available Resources. Also, other problems can occur, for example, too many Nodes need 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, whether particular Nodes show a violation.

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

Therefore, during the optimization, Nodes can collect these penalty points. If the number of penalty points (compared to the number of solutions in which these Nodes are not showing violations) is getting too high, these Nodes are getting filtered out. Also, the AutoFilter allows for several adjustments. For example, adjusting a particular reason (like late- or early-violations, etc.) for filtering, setting margins, protecting individual Nodes from being filtered, and so on.

Screenshot

Figure - AF 1

Example

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


Custom solution

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

However, using construction is not as flexible as our subsequent optimization algorithms due to its deterministic nature. For special use-cases, either a custom construction algorithm can be defined (contact us), or you construct a starting solution on your own and provide it on start-up.

Example

We use a human-friendly JSON definition to save an optimization state. On loading a persisted state, the JSON definition is converted into a custom solution and is used on start-up.

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 OpenAssesor allows injecting custom restrictions into the optimization process.

In the following, we look at two conditions that impressively show the 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 request that each Node should be visited as early as possible within its OpeningHours. For example, we are dealing with two Nodes. Node A is open from 8 am to 5 pm, and Node B is open from 9 am to 5 pm. Further, a Resource needs one hour 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 exactly in the same cost as both Nodes would be arrived 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. Meaning, as Node A is already open for one hour, 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 is preferable over another order, 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 pm.

Custom condition on Route-Level

The need for custom restrictions can also arise on the route level. Let's assume, for the sake of argument, we want the Optimizer to preferably find routes with an odd number of Nodes in each route (Figure - OA 2).

Screenshot

Figure - OA 2

With the Open Assessor, we can formulate this restriction and inject it into the Optimizer.


Closing Words

When visiting our GitHub-examples, you may notice that there 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 provide and develop new customer-inspired features.


Authors

A product by dna-evolutions ©