If you are aware of the Vehicle Routing Problem (VRP), you will know that it is quite an easy problem to state, although it has many variations which make it one of the more complex standard models.
Here is a fairly standard description (model):
You are given:
- a set of customers (each one having a demand);
- the location for each customer (perhaps as x,y coordinates or, perhaps, as a distance matrix between each customer);
- a set vehicles, each with a given capacity (usually identical for all vehicles);
- a depot; where each vehicle must start and end.
Then the problem is to come up with a number of routes (the number of routes is usually the same as the number of vehicles) that
a) minimises the distance travelled and
b) ensures that a vehicle does not exceed its capacity taking into account the customers it visits and their demand.
And that is all well and good and a lot of excellent research has been carried out using this relatively simple model.
Of course, there are many variations. For example, trying to minimise the number of vehicles (routes), introducing the concept of backhauls (i.e. doing all the deliveries and then going back to each customer and picking things up) and having time windows (i.e. a customer has to be visited at a certain time).
However, even these variations (and there are many others) do not capture many real world issues that often need to be addressed. Take, for example, supermarkets that deliver to your door. It is usually a Vehicle Routing Problem with Time Windows (the supermarkets often give you a two hour slot when they will deliver). But what about other factors that might have to be considered? How about:
- Time might be an issue with respect to how long perishable goods can be in the delivery van.
- Perhaps the vehicle has to be packed in such a way that the deliveries which are delivered first have to be loaded last.
- Perhaps the vehicle can only carry a certain weight, in addition to a certain volume.
- Perhaps the weight has to be evenly distributed over the vehicle.
- What happens if there is a breakdown.
- When do you "pick" the goods from the shelves and when do you "dispatch" the vehicles.
Some of these may not actually be problems for the supermarket delivery problem but you can imagine these factors coming into play for other types of delivery problems.
And trying to take a standard vehicle routing model and developing it to model a real world problem is often far from easy.
LP in statistics: The Dantzig Selector
1 week ago
2 comments:
To go from a standard vehicle routing model to a real-world solution, you need to be able to add problem facts and problem constraints easily in your
planning framework to accommodate for those extra constraints.
Drools-solver can do such things easily.
Let's take the "the vehicle can only carry a certain weight" constraint for example:
First you add a new property on the Vehicle class:
public class Vehicle {
private Volume supportedVolume; // existing
private int supportedWeight; // new line
// ...
}
Then you add in an extra constraint rule:
rule "weightTotalLowerThenVehicleCanTransport"
when
$v : Vehicle($sw : supportedWeight);
$t : Trip(vehicle == $v);
$total : Number() from accumulate(PackageInTrip(trip == $t, $pw : packageWeight),
sum($pw)
);
eval($sw < $total);
then
insertLogical(...);
end
And you're done.
It's simple, isn't it? :)
Post a Comment