BL.Optim: A cutting-edge but static planning optimization tool

BL.Optim is our optimization engine for routing and scheduling, used to generate efficient planning under complex constraints. While highly flexible, it currently operates as a static solver: schedules are generated once, based on a submitted problem, and cannot be adapted without full recomputation.

When plans need to react to changes, especially in time-sensitive environments, this raises several questions:

• If some of the submitted problem properties have changed afterwards, for instance just before or even during the schedule execution, how can the solution be adapted quickly? There is no such option in BL.Optim, and the customer has to submit the modified problem or bring manual changes to the computed solution.
• In the case of an ill-adapted constraints configuration, bringing an unsatisfying solution, the customer might want to adapt some parts of the schedule while keeping others. As with the other questions, this is not yet possible and currently boils down to a new request with a new constraints configuration, and possibly some manual changes.

To address these challenges, we began exploring dynamic rescheduling and have since developed a dedicated module currently known internally as “Re.Optim”.

Re.Optim: Bringing dynamism to BL.Optim

Leveraging new features of our solver

Interestingly, the technology used as the basis for our solver has recently evolved to offer new features that would be useful for adding dynamicity to BL.Optim.

Firstly, we can now build a solver manager that allows us to re-optimize an already solved problem, starting from its last state, and a solution manager that let us update a solution based on changes in the problem. Secondly, it is possible to pass the constraints parameters as variables that can be modified with the rest of the problem. Then, using the same algorithm that we are using to initialize solutions in BL.Optim, we can now develop a recommendation system to help the user assign new planning variables. Finally, the new features can help us build a pinning system to limit the changes induced by the re-optimization of a problem.

Re.Optim: A solution for rescheduling

Leveraging on those new possibilities, we propose our rescheduling module for planning already optimized by BL.Optim. To go further, it can load any manually generated planning as long as it respects BL.Optim API output scheme.

Simple addition or deletion of planning entities

The first feature in this module makes it possible for the user to add or remove some planning entities or planning facts.

In BL.Optim, planning entities and planning facts are objects used by our solver to compute a score based on the different existing constraints. More specifically, planning entities hold all the planning variables, so they can change during solving, while facts do not change unless the problem itself changes. In the context of routing and scheduling problems, we work with activities as planning entities, assigned to resources that can be planning entities or facts depending on the built model.

The Figure 1 shows a pretty simple model example to illustrate what are entities, facts and variables, and how they are connected to constraints. Here, activities and staffs are entities since they hold the planning variables: a staff has a list of assigned activities, which is its planning, while activities have an assigned staff and start time. Those elements are variables since they change during solving to find the best solution. The possible offices and materials are not entities since they do not change during solving. However, since they hold attributes that are used by constraints, they are planning facts. In this case, locations are neither entities nor facts, since no constraints are using them. Staffs and materials are resources for our activities, which could have hold unavailabilities in a more complete problem.

However, due to unforeseen events, it is possible that the planning entities and planning facts change:

• A new activity may appear between the generation of the schedule and its execution, or an existing activity may be cancelled.
• A resource may become unavailable, or we can add a new resource that was not considered before.

It’s easy to remove activities from a timetable, which lightens the load. However, adding new activities is more technical as it makes the planning uninitialized until these activities are assigned to a resource. Adding resources is not a problem either, but removing some with assigned activities results in the creation of unassigned activities, as illustrated by our playground interface on Figure 2.

Once the schedule has been changed, Re.Optim can easily take the changes into account and build a new solution using its re-optimizing function.

Advanced changes to a problem and its constraints

However, it can be required to operate more subtle changes. For example, let’s say that we have an activity in our schedule that is supposed to last 20 minutes. In the end, some unforeseen event occurs and the activity needs an hour to complete. In this case, we don’t want to entirely replace the activity but solely its duration. Similarly, if a resource availability changes at some point, we prefer modifying its availability than adding a new resource and deleting the old one.

Those changes can be applied anywhere in a BL.Optim result, including the constraints configuration it includes. Similarly to the previous subsection, subtle changes also trigger an update in the solution using the solution manager and change the solver manager configuration if required.

Facilitating new assignments: recommendation system vs automation

As mentioned above, changes in the problem can result in some uninitialized elements appearing in the solution. In this case, re-optimizing will fix the issue, however it may also introduce too many adjustments into the resulting schedule, which can be counter-productive. Indeed, in most cases, customers want to adapt the solution to changes while minimizing perturbations.

Numerous options can be implemented to address this:

·        Using a pinning system to avoid unwanted changes.

·        Adding a stability constraint that would penalize disturbances to the schedule.

·        Initializing the problematic planning entities without a call to the re-optimizing function.

For now, the third strategy has been implemented in our rescheduling module. It can be operated through two different methods: the first one is a recommendation system that lets the user choose between multiple assignment possibilities, and the second one is a fully automated assignment. Both solutions use the initializing phase included in the BL.Optim solver. This phase is used to generate a first planning in which all activities are assigned, even if it is not optimal. However, the recommendation system treats uninitialized entities one-by-one and wait for a decision from the operator. The decision can be based on a view of the constraints violation difference induced by the assignment, as illustrated by Figure 3. Those violations of constraints induce a score that is used to evaluate solutions. This score is divided in different level based on the constraints criticality (soft for less critical constraints, hard for most critical constraints, medium in between).

Conclusion

Re.Optim is a rescheduling module that addresses the lack of dynamism in BL.Optim. It is now possible to respond to changes quickly without submitting a new problem. However, there is still a lot we can do to improve our solution.

We are currently performing a deep study on the existing construction heuristics, which are the approaches used to initialize a schedule by assigning all activities to resources, and their impact on the recommendation system and automated initialization method.

In the future, we would like to improve our recommendation system with better assistance in the user choice, relying on AI to offer a smarter and more readable description of the changes induces by each choice.

Finally, we have to work on the pinning system in order to let our customers control how new solutions should stick to the previous ones when calling the re-optimizing function.