The vehicle routing problem (http://en.wikipedia.org/wiki/Vehicle_routing_problem) is an optimization problem to find good routes for many vehicles to serve workloads / visit multiple locations (customers) with a given set of constraints.
The goal of the optimization is generally the minimization of costs, which could mean the minimization of fuel used or vehicles needed to satisfy the requirements.
The constraints depend on the business case and many different constraints imaginable, e.g. the given number of vehicles, the maximum working time, start/stop time, maximum load capacity etc.
OptaPlanner
The open-source framework OptaPlanner (http://www.optaplanner.org/) is completely implemented in Java and provides examples how to solve the vehicle routing problem (among other problems) using configurable heuristics and flexible constraint definitions. The current version is 6.0.0.Final with an active community.
Flexible Scoring
It is based on jboss-drools (http://www.jboss.org/drools/) to provide incremental score calculation. A numeric “score” is used to model “costs” or “reliability” or whatever is required to compare if a possible solution is valid or better than another one.
“Incremental calculation” is important, because it can be an expensive job to calculate the score from scratch after each move for the whole solution. So only affected parts should be re-calculated after each move.
The concrete score value is not important, but the goal is to optimize the (multi-level) score that is influenced by the constraints defined in rule files for score calculation. So the scoring could be even configurable during runtime. (In real projects the scoring is probably company-specific and varies from customer to customer.)
This article describes some of the requirements and constraints that a software must fulfill to compute feasible solution for the vehicle routing problem. Before going into details, you should have a look at the examples, that OptaPlanner provide.
YouTube Videos:
- Vehicle Routing with OptaPlanner
http://www.youtube.com/watch?v=GybpV0uLrxc - Vehicle Routing Score Flexibility
http://www.youtube.com/watch?v=4hp_Qg1hFgE - Vehicle Routing with Time Windows
http://www.youtube.com/watch?v=BxO3UFmtAPg
Documentation:
- Vehicle routing
http://docs.jboss.org/drools/release/6.0.0.Final/optaplanner-docs/html_single/index.html#vehicleRouting
Distance Calculation
In real projects, the distance calculation is a bottle neck. Distances are not calculated with the euclidian algorithm (like in the OptaPlanner examples) but require geo-data (routing data) to be realistic. The distance can either be the length (meters) that a vehicle needs to drive from one location to the next or the amount of time (seconds) required to travel between the locations. Normally the duration is what matters for planning. This value can even be different according to the direction of travel between two locations or vary during the day (rush hours, traffic awareness).
The quality of the underlying geographical data is mission-critical for the quality of the solutions found. There is much room for optimization to quickly compute the distance matrix that is required by OptaPlanner to find better solutions while trying different moves on a problem setup.
Without going into details here, we just point to some techniques we are using to solve this:
- batch geo-coding of addresses (because in real projects the input data does not contain latitude and longitude but postal addresses)
- pre-calculation of the distance matrix
- multi-level caching using memory and a NoSQL database
- geo-fencing based on postal codes or customer names (described later)
Problem extensions
Time Windows (Opening Hours)
Some use-cases offer delivery within a specific time-interval, e.g. a parcel that must arrive before 9 o’clock or within opening-hours to deliver products to a location.
The time windows per workload affect scoring, so that waiting times must be considered and the sequence of stops of the vehicle route changes.
OptaPlanner supports such additional constraints as a new feature in its latest release with the concept of so called “Shadow Variables” and “Planning Variable Listeners”. See the documentation for details.
Relations between Visits (Pickups and Deliveries)
Some use-cases restrict the sequence of stops per route (or even between different routes) according to the kind of service that is provided to the customer.
Example 1:
The vehicle may arrive at a stop to pick up a good that needs to be delivered to another destination. (The pickup must happen with the same vehicle that delivers it later to the destination.)
Example 2:
The vehicle may deliver a spare part to a location that is required when the technician arrives later with another vehicle. (The delivery must happen before the technician arrives at the location with another vehicle.)
In such cases, it must never happen, that a vehicle arrives on a stop without the requirement fulfilled.
Both problem extensions should be modeled with hard-constraint violations that make a solution non-feasible.
Soft constraints
Other problem constraints are typically modeled with soft-constraints, e.g. the distance between stops, the number of vehicles used, the risk of arriving within the time-window etc.
Manually Overrule the Schedule
If the software computes a good solution, it must enable an experienced user to overrule it manually with a tool that visualizes the schedule. The software must allow to modify the sequence of stops, put a workload fixed on a vehicle, change vehicle settings or give the workloads different priorities on their routes. All those constraints should happen during optimization, not only afterwards, so that the user immediately sees the impact to the resulting schedule.
Round-trip and One-way
Different kind of routes could be required (Some of the vehicles may start each day in a specified location and the route needs to return to this start: a round-trip. Other tours are just a one-way sequence ending on the last location.)
Scalability with Geo-Fences
The calculation costs increase exponential with the number of locations and vehicles. To split the problem into separate schedules 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 extend the relevant modules accordingly. We will describe the implementation details in another article.
Real-time planning
Once a solution has been found, the vehicles may start to carry out the schedule. In some scenarios the customer expects the plan to dynamically adopt to incoming events:
- New stops may be created that vehicles should reach during they already drive.
- Address and time changes come in for workloads that are already planned on vehicles.
- Workloads get cancelled.
This demands that the software knows more about the current situation (current position of vehicles etc). OptaPlanner supports real-time planning by providing so called FactChanges, that allow to modify the problem facts during optimization.
A Tool for Planning
Viaboxx is developing a solution for those scenarios. The tool has a modern HTML5 frontend and a scalable, distributed optimizer. The optimizer engine is implemented using the latest version of OptaPlanner.
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.
Read our 2nd article about OptaPlanner/Routing: https://www.viaboxx.de/route-optimization/scaling-the-vehicle-routing-problem/