Saturday, March 03, 2012

Chained: the trick behind solving TSP and VRP in Planner with minimal code

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 :)