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

8 comments:

  1. "A chain is never a tree, it is always a line."

    Technically, a "line" is also a tree - you may want to re-phrase that sentence.

    ReplyDelete
  2. @triceo Good point. As was your suggestion to call it simply "chained" instead of "triggerChainingCorrection" :)
    Not sure how to re-phrase it. Got any suggestion? Would stating "A chain is not a tree, it is a line" be less falsely implying that a tree cannot be a line?

    ReplyDelete
  3. Can an entity exist in more than one chain?

    In my current problem, I want to put a work item into one or more queues and whichever queue gets to the item first does the work. (My rules prevent the work items from being placed in incompatible queues but sometimes I don't care which queue performs the work)

    ReplyDelete
  4. @Chris no, not if you only use 1 @PlanningVariable.
    An entity with a @PlanningVariable(chained = true) cannot exist in more than one chain for that variable.

    How do you see your domain model?
    For example: the class Visit has a method getPreviousAppearance() which returns a single Appearance instance, which is either another Visit or a Domicile instance. If a Visit can be assigned to multiple chains, then of what type would your getter of your @PlanningVariable be?

    Using multiple @PlanningVariable(chained = true) works (although test coverage is still low for it). So you could create Visit.getPreviousAppearance1() and .getPreviousAppearance2().

    ReplyDelete
  5. Geoffrey,

    My model is a collection of Jobs with varying priorities, durations and requirements. They will be processed by a heterogeneous pool of Services which request jobs from the collection (i.e. a pull behavior). My optimization problem is deciding which job to hand to a Service that asks, favoring jobs that are likely to succeed, favoring high-priority jobs, favoring jobs that are nearing deadline, favoring jobs that have been sitting in the pool a long time.

    My initial thought was to model the problem as one chain per Service. The chain is composed of JobEntry entities and each JobEntry holds one Job. I want to pre-compute the chains before the Services ask for better latency. Because Services can crash or otherwise behave unpredictably, I can't risk putting a Job in just one chain because the Service for that chain might never ask for a Job.

    In the end, I'm instead considering modeling the problem as an N x M grid of JobSlot entities where N is the number of Jobs and M is the number of Services. Then Job is the planning variable.

    ReplyDelete
  6. @Chris Interesting use case :)

    The JobSlot idea sounds like a good idea, presuming that it doesn't matter that a certain Job is executed twice (as they can start in parallel). I don't think you even need chaining in that implementation, as the JobSlots are naturally chained per Service. This will make the implementation simpler. Question is how will you score the same Job running on 2 Services at the same time?

    Another alternative is to look at real-time planning (see the chapter in the Planner manual): If a Job fails, you could create a PlanningFactChangeEvent, adding a restriction that that failed Job should not be scheduled on the Service it failed on. Then replanning will schedule the Job on another Service.

    ReplyDelete
  7. Im new to drools planner.could you please teach me the work flow of tsp sample example in drools.

    ReplyDelete
  8. @Anonymous Read the quick start in the documentation:
    http://docs.jboss.org/drools/release/6.0.0.Beta1/optaplanner-docs/html_single/index.html

    ReplyDelete