Starting from 5.4.0.CR1 (soon to be released), Planner will have chained support: a feature specifically designed to help solve Traveling Salesman and Vehicle Routing like problems with minimal code. It’s compatible with all the other planner features (construction heuristics, metaheuristics, real-time planning, …) and it replaces a ton boilerplate code I used to have in the TSP example.
From the documentation:
A planning variable that is chained either:
- Directly points to a planning fact, which is called an anchor.
- Points to another planning entity with the same planning variable, which recursively points to an anchor.
Here are some example of valid and invalid chains:
Every initialized planning entity is part of an open-ended chain that begins from an anchor. A valid model means that:
- A chain is never a loop. The tail is always open.
- Every chain always has exactly 1 anchor. The anchor is a problem fact, never a planning entity.
- A chain is never a tree, it is always a line. Every anchor or planning entity has at most 1 trailing planning entity.
- Every initialized planning entity is part of a chain.
- An anchor with no planning entities pointing to it, is also considered a chain.
The optimization algorithms and build-in
MoveFactory‘s do chain correction to guarantee that the model stays valid:
Stay tuned… Vehicle routing (with capacity limits) demo video coming soon 🙂