This article gives an idea of how the vehicle routing problem can scale for many vehicles and many stops. During solving of a problem, OptaPlanner tries to find better and better solutions by creating (random) moves to exchange the sequence of the locations in the vehicle routes.
One of the major bottlenecks is the calculation of the distance between two points – which is not a part of OptaPlanner. When there are a few hundred workloads, thousands of distances need to be computed so that the optimizer can score new moves.
This article does not cover the details of caching and performance optimization for the computation of distances based on geo-data. While this is important, of course, this article points to other strategies to enable planning, not for hundreds, but thousands of workloads.
Organizational Partitioning
Some customers have distinct areas for which they need a schedule for the vehicle routes. Thus the total number of workloads need not be optimized as a single problem with OptaPlanner, but should be partitioned into distinct problems per area.
Currently (Release 6.0.0.Final of OptaPlanner) the optimizer algorithm only uses a single thread to find a better solution. Partitioning allows to do parallel optimization, each problem using a single thread / CPU core.
The business logic must use indication fields on the input data to determine to which of the areas the workload belongs.
Geo-Fences
To split the problem into separate areas is not always possible when the customer expects a single, dynamic schedule. Geofencing is a technique to limit the number of distances to be calculated, e.g. when workloads in a specific range (a polygon on a map or intervals of postal codes) belong to the same routes. It requires some knowledge about the incoming data but with experience in planning, this helps to make optimization of big data sets scale nearly linear instead of exponential.
OptaPlanner does not support Geofencing out-of-the-box. But as an open-source framework, it let us implement the relevant interfaces accordingly.
Planning with geo-fences means, that only one or a few vehicles are possible candidates to carry a workload. Some criteria of the workload, e.g. the postal code, could lead to a fixed assignment to a specific vehicle.
This reduces the number of combinations because the optimizer does not need to compute the distance between workloads of different vehicles/routes.
Geo-Fencing with Score-Constraints
One solution to implement this using OptaPlanner could be to punish invalid moves of workloads to false vehicles with a hard-constraint violation. While the optimizer will find better and better solutions with this strategy, it is nevertheless suboptimal. The reason is, that much of the computation time would be spent on scoring moves, that are unwanted/illegal and would never bring a better result.
Implementing Geo-Fencing with OptaPlanner
OptaPlanner’s MoveIteratorFactory interface allows to customize the move candidates, and this is the interface to implement if you need to create specific moves only.
We created an implementation class called “GeoFencedMoveIteratorFactory” that provides a “RandomGeofencedMoveIterator” to create random moves between workloads, but only those that are valid according to the vehicles allowed by the geo-fences.
You need to know, that OptaPlanner starts to create random moves (if configured to do so) in the “local search” phase of optimization. The “local search” requires a fully initialized planning problem to start with. Thus, the first phase is the so-called “construction phase”, normally implemented by a default strategy of OptaPlanner.
The construction phase must assign each workload of the problem to one of the vehicles/tours before the “local search” phase starts to move the workloads around.
To ensure that the construction phase creates a valid schedule, that already conforms to the geo-fences, we need to replace the default strategy with a custom implementation.
We did our implementation of OptaPlanner’s interface “SolverPhase” called “GeoFencedConstructionPhase”.
To perform a move that modifies the current schedule under planning, OptaPlanner creates instances of the “Move” interface. The default implementation is using Java reflection to access the underlying model (workloads and vehicles).
To speed up the moves, we implemented a ChangeMove directly, that does not use reflection. This was quite easy because we already had the implementation of the MoveFactories and ConstructionPhases, where moves are being created.
To activate the custom implementations, OptaPlanner requires a solver configuration, a XML file that is parsed by the XML framework XStream (http://xstream.codehaus.org/).
We can use our custom implementations here. The configuration would look like this:
<solver> <environmentMode>PRODUCTION</environmentMode> <solutionClass>de.viaboxx.Schedule</solutionClass> <planningEntityClass>de.viaboxx.Workload</planningEntityClass> <scoreDirectorFactory> <scoreDefinitionType>HARD_SOFT </scoreDefinitionType> <scoreDrl>scoreRules.drl</scoreDrl> </scoreDirectorFactory> <de.viaboxx.GeoFencedConstructionPhase/> <localSearch> <moveIteratorFactory> <moveIteratorFactoryClass> de.viaboxx.GeoFencedMoveIteratorFactory </moveIteratorFactoryClass> </moveIteratorFactory> <acceptor> <entityTabuSize>9</entityTabuSize> </acceptor> <forager> <acceptedCountLimit>2000</acceptedCountLimit> </forager> </localSearch> </solver>
This demonstrates:
- how the score rule file is configured (scoreRules.drl).
- how the construction phase can be configured using a custom SolverPhase.
- how the local search phase can be configured using a custom MoveIteratorFactory.
Please contact us, if you are interested in more details, techniques or if you want to help us prove the solution in practice to solve your vehicle routing problem.
Image credits go to: http://www.optaplanner.org/
This article is the 2nd about OptaPlanner/Routing. See our 1st blog entry: https://www.viaboxx.com/route-optimization/vehicle-routing-optaplanner/