. .
March 2014
Roman Stumm, 05.03.2014

This article gives an idea 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 spend in 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.

 

This article is the 2nd about OptaPlanner/Routing. See our 1st blog entry: http://www.viaboxxsystems.de/vehicle-routing-optaplanner

Kommentare zu Scaling the Vehicle Routing Problem Kommentar hinzufügen

Ihr Kommentar







Bitte hier die Zahl 1 eintragen



 
Von Geoffrey De Smet

Great blog! :)

In OptaPlanner itself, I am working on out-of-the-box support for NearbySelection:
https://issues.jboss.org/browse/PLANNER-202
NearbySelection allows swapMoves to favor selecting 2 customer locations that are close to each other. The favoring would happen according to a beta distribution: so every combination of 2 customers is still possible, but the more nearby the customers are, the higher the probably they get selected together.

I have some questions:
1) How does Geofencing relate to NearbySelection? Is it the same, an alternative or a complement?
2) Geofencing limits the number of vehicles that an be assigned to a customer? Why does from entity value range (as opposed to the default of from solution value range) not suffice to do that?
3) Is the source of GeoFencedMoveIteratorFactory.java and GeoFencedConstructionPhase.java available? (under ASL license, but just those files not the entire project)? I would use it to improve and validate the design of NearbySelection :)
 
Von Roman

Geofencing limits the number of vehicles that an be assigned to a customer? Why does from entity value range (as opposed to the default of from solution value range) not suffice to do that?
You are right, maybe it does the same thing... We have to compare the solutions and read the optaplanner docu in more detail about from entity value range... I wonder if this is feasible at all, because the docu says: Entity value range is not compatible with a chained variable ...?