Saturday, January 15, 2011

Do you have a bin packing problem or vehicle routing problem?

I am looking for a good bin packing problem or a good vehicle routing problem to implement as an example in Drools Planner. So if your company has a situation similar to these, consider contacting me (or replying to this blog):
  • It has to fill containers with boxes. It wants to minimize the number of containers used.
  • It needs to service a number of customers with a fleet of vehicles. For example an airline, a train company or freight distributing company.
  • It has a paper mill and needs to cut fixed-sized paper rolls into various-sized paper widths (per customer order). It wants to minimize the waste.
A couple of people have already implemented such problems in Drools Planner, but there's no official open source example yet, to show some of the best practices and implementation details. Furthermore, many companies don't realize they can save a lot of money and severely lower their ecological footprint by optimizing their planning.

What's in it for you? You get a free (ASL licensed) prototype, tailored to your planning problem. It should be straightforward to copy that into your (proprietary) company code and integrate it with your live systems.

What do I need from you? A couple of things:
  • Real-world data sets
    • Preferably in XML or TXT format
    • Each data set should be a planning instance that occurred in the past.
    • Preferably at least 5 historical data sets
    • All data that is not relevant for the planning problem should be pruned.
    • If it contains sensitive data (such as employee names), that data should be obfuscated.
  • A clear data format description, except if it is readable XML.
  • A clear description of the hard and soft constraints. For example:
    • HARD: Each airplane cannot transport more passengers than its number of passenger seats.
    • SOFT: Each airplane has a fuel price per km (depending on it's size). Minimize the cost.
    • SOFT: Each airplane has an airport tax per landing. Minimize the cost.
  • It should be possible to calculate the entire cost of a solution in $ or €.
    • And preferably also in liters of fuel or CO² emission or any other ecological footprint.
    • If possible, each historical data set should contain the solution that was executed originally in the past, so we can calculate the original cost and footprint and compare it with the optimized solution, to clearly show the cost and ecological footprint reduction.
  • All this information must be made available under the ASL license because it will be added to the Drools Planner examples.

9 comments:

  1. Hi,
    we have a configuration problem with these players:
    - an apparate with some slots.
    - some hw, that must be plugged in the slots, has a cost and provides resources.
    - a set of constraits about minimum resources needed.

    We have to fulfill constraints minimizing cost.

    The solution has already been developed using Gomory's cut (so we can generate a lot of dataset )

    Let me know if you're interested.

    ReplyDelete
  2. @Luca

    Sounds like a good Drools Planner use case and a indeed form a bin packaging. It looks like it's very similar to the cloud balance example.

    I've been contacted for a couple of cases, and I am currently waiting for the data of 1 vehicle routing case, which seems to be a perfect fit to what I am looking for: complex, understandable and a direct score result in cost reduction and CO² reduction. So an example I can use to prove that the ROI on improving your planning with Drools Planner is high.

    ReplyDelete
  3. Short version of my problem, related to container ships instead of my industry descripion purposes.

    Bin Packing

    * Optimize across multiple container ships.
    * All containers must be placed
    * Each container can be a different size
    * Each container can be a different weight
    * Each container ship can be different size
    * Each container ship has minimum / maximum weight and volume constraints.
    * Each container has relational properties where it must be in a certain area of the ship, and also cannot be next to certain other containers based on its properies.
    * Sometimes containers need to go into the ship in a certain order.
    * Sometimes the container ships will be half way loaded when the optimization needs to be run again.

    ReplyDelete
  4. @Anonymous: Sounds like a classical 3D bin packing problem with extra hard constraints, perfect for Drools Planner.

    I 've already started doing the vehicle (truck/trailer) routing case as a public planner example in my weekends for free.
    That example should be closer than the current examples to your use case, making it easier to learn from.

    If you're interested in solving your bin packing case privately in production with Planner and you're also looking for paid support, contact us through Red Hat's amentra. If you're looking for free support, use our user mailing list.

    ReplyDelete
  5. Look here: http://pakowacz.net/html/simulator

    ReplyDelete
  6. Hi Geoffrey,

    Sorry to post on such a late date but I am not sure where else to ask this question:

    Did you ever manage to get this vehicle routing example up and running? If so where will I be able to find it?

    Thanks

    ReplyDelete
  7. @Anonymous

    I hope to have time to do a TSP example for 5.3 and later to implement the RAS 2011 competition as an example.

    ReplyDelete
  8. Hi Geoffrey,
    How's it going with the vehicle routing?
    I might have a real life business case, for a major cement producer that is interested in reduction of both $$$ and CO2.
    I think they are willing to support a nice reference story for Jboss in exchange for some help

    ReplyDelete
  9. I am working on some improvements for vehicle routing use cases, so they far easier to implement. Look for "multi TSP" on the master of drools-planner in a week or 2.

    ReplyDelete