OptaPlanner 6.2 released: giant leap for Vehicle Routing Problem
Join the DZone community and get the full member experience.Join For Free
We are happy to announce the 6.2 release of OptaPlanner.
OptaPlanner is a lightweight, embeddable planning engine written in Java™
to solve constraint satisfaction problems efficiently.
Together with the Drools rule engine and the jBPM workflow engine, it is a strong and flexible foundation for knowledge management.
Each of these videos demonstrates an example and/or a special feature:
Exam timetabling: User defined score parametrization
Dinner party scheduling: Decision tables
Cloud optimization: Decision tables
Cloud optimization: Real time planning
Course scheduling: Immovable planning entities
Project job scheduling: Build-in hard constraints
Tennis club scheduling: Fairness and load balancing constraints
Vehicle routing with time windows: Shadow variables and real-time planning
Vehicle routing scoring: Score function flexibility
Employee rostering: Continuous planning
Stable: Heavily tested with unit, integration and stress tests.
Reliable: Used across the world. See case studies.
Scalable: One of the examples handles
50 000entities with
5 000variables each, multiple constraint types and billions of possible constraint matches.
Documented: Read the detailed reference manual or one of the many examples.
Open source: Released under the Apache Software License.
New and noteworthy
Scalable VRP with nearby selection
Nearby selection allows a vehicle routing problem to scale out gracefully beyond 1000 locations, without the need for partitioning. It works by focusing on move selections that modify locations that are near each other:
It results in much better scalability to larger datasets, for example a VRP with 2750 customers:
Several nearby selection probability distributions are supported: block distribution, linear distribution, parabolic distribution and beta distribution.
TailChainSwapMove (2-opt) for VRP
TailChainSwapMove is a new move type for chained variables. It’s a subset of SubchainChangeMove and SubchainSwapMove, but it’s generally more efficient, especially for time windowed cases.
In our benchmarks, a union of ChangeMove, SwapMove and TailChainSwapMove (using nearby selection on all 3) performed best.
Improved build-in variable listener efficiency
VRP with a
@InverseRelationShadowVariable is now more efficient. In some cases, it’s up to
Strategic Oscillation Tabu Search
Strategic Oscillation Tabu Search is often an improvement over normal Tabu Search. Instead of picking the accepted move with the highest score, it employs a different mechanism: If there’s an improving move, it picks it. If there’s no improving move however, it prefers moves which improve a softer score level, over moves which break a harder score level less.
To enable it, do this:
<localSearch> ... <acceptor> <entityTabuSize>7</entityTabuSize> </acceptor> <forager> <acceptedCountLimit>1000</acceptedCountLimit> <finalistPodiumType>STRATEGIC_OSCILLATION</finalistPodiumType> </forager> </localSearch>
New example: Cheap time scheduling
Schedule all tasks in time and on a machine to minimize the power cost. Each machine must have enough hardware to run all of its tasks. Each task and machine consumes power. The power price differs over time.
Based on contributions by Lukáš Petrovický.
New benchmarker statistics: Constraint Match Total Best/Step score
These new statistics visualize how the individual constraint types change over time.
This gives a better insight as to which constraints impact the score the most.
Construction Heuristics: new pick early type:
FIRST_FEASIBLE_SCOREwhich is useful for scaling.
Benchmarker: logarithmic scale for Problem scale axis when appropriate. Contributed by Ondrej Skopek.
BendableLongScore: Bendable score with long types. Contributed by Dieter De Paepe.
Opinions expressed by DZone contributors are their own.