Friday, February 03, 2012

Traveling Salesman Problem demo with Drools Planner

Implementing TSP or vehicle routing in Drools Planner 5.4.0.Beta2 and earlier was difficult. But starting from 5.4.0.CR1, such use cases are easy and far less code to implement. And they are compatible with real-time planning.

Just take a look at the Traveling Salesman Problem (TSP) demo. It shows adding cities in real-time and demonstrates how easy it is to change the constraints:



Coming soon: a vehicle routing example and even better scalability.

6 comments:

  1. Geoffrey, wanted to ask this and didn't know the right place. Is it possible to know which constraints are broken with each best solution while the algorithm is running?

    Is it possible to do so with SolverEventListener? thanks!
    Manuel

    ReplyDelete
  2. @Manu: The right place for community questions is the user forum:
    http://www.jboss.org/drools/lists
    To answer the question:

    1) In the examples there's a button on the left bottom that shows a list of each constraint rule, it's broken count and it's broken weight. Also, if you click on it it shows exactly which constraint occurrences break it. That's done through a dirty hack currently, but for 5.4.0.CR1 that's been refactored into a much-less-dirty hack (by cloning a separate SolutionDirector). So that's one way of doing it.

    2) Another (cleaner but less fine-grained way) is to write your own ScoreDefinition (see manual for howto) and define a MyScore that has an int rule1Broken, int rule2Broken, rule3Broken, ... That will only give you info on which constraints are broken, but not on which constraint occurrences are broken and therefor not on which entities are breaking what.

    The SolverEventListener just gives you the best Solution (with the filled in Score). Performance and design wise I am not in favor of include the constraint occurrences in each event. I do agree that users need to be able to reuse score calculation outside the Solver, without resorting to the hack in 1). It might be a matter of defining SolutionDirector as an API.

    What exactly are you looking for? Could you explain your use case a bit more (examples) and how you'd envision the API?

    ReplyDelete
    Replies
    1. Thanks a lot Geoffrey! I'll check the user forum and try to solve my problem using approach 1. Approach 2 seems interesting too, btw, I had already taken the default hard/soft score as "the only way" to do stuff with planner.
      In my case I am solving a real exam scheduling problem (~2000 students, ~300 exams, ~50 rooms, data from the past, though) and the hard score never reached 0, so I wanted to debug which rules where in trouble.

      Delete
    2. @Manu "the hard score never reached 0": It could be you're facing a "score trap". Look in the manual for the explanation of that. Simply put, the pitfall is that the same room with 2 seats to little should have a hard score of -2 and one with 30 seats to little, should have a hard score of -30. Seeing the actual constraint occurrences will indeed expose that score trap better.

      Delete
  3. Hello every body, i'm Drools planner beggener i would like to ask the following question :
    Is it possible to keep the history of each step best solution ? this is important for researcher for drawing curves to show the evolution of solution space exploration.

    Thank you in advance.

    ReplyDelete
  4. @Cheikh That's already supported :) Take a look at
    the Benchmarker's Best score over time statistic (graph and CSV).
    The Benchmarker should satisfy all your researcher's needs :)

    ReplyDelete