VRP variant, how to modify provided VRP example

Question

I'm new to optaplanner and im trying to tweak the VRP example to solve a "similar" problem... but with some differences:

We have a central depot, n customers and a fleet of one or more vehicles.

Each customer has a certain "maximum capacity" (not the same for all of them).

Same for each vehicle.

Initial conditions from the problem include: "actual capacity" and "desired capacity" for each customer, so that:

actual capacity is >=0 and <=max capacity
desired capacity is >=0 and <=max capacity

"actual depot capacity" is the amount of items available at the depot

We want to REDISTRIBUTE some items so that each customer gets his "desired capacity".

(Tipically most items will be redistributed from one customer to another)

Hard constraints are "maximum capacity"s cannot be excedeed Soft constraints are vehicle distance (minimize) and difference from "desired capacity" (minimize)

I started by generating a data file for the VRP example with negative customer demand (to simulate desired capacity < actual capacity) but quickly discover that constraint in drl that sums up all customers demands to satisfy vehicle capacity restriction is not what we need here.

¿Do you think that this problem is "similar enough" to worth modifying VRP example?

Answer 1

Yes, it's definitely worth taking the OptaPlanner VRP example (with or without the example GUI) and customizing it to these needs. Start from OptaPlanner 6.0.0.CR1 or better yet CR4 which will be released next week normally. Don't use CR3 because it might have a bug related to shadow variables in VRP.

A) Let's presume customerDemand = customerDesired - customerActual. This can be positive (need more items) and negative (need to get rid of items).

Question: How do we validate the Vehicle capacity? We can't just sum it, because it fluctuates from customer to customer. Answer: We use a shadow variable (let's call it freight) on Customer to calculate how many items the vehicle is transporting from the previous customer to the current. This is very similar to how arrivalTime works for the TimewindowedCustomer example. Then use a score constraint rule to verify freight on every customer is lower than the vehicle's maximum capacity. And also that freight is >= 0 at every customer.

Now, A) works well if there are plenty of vehicles. Even if there aren't enough items, checking the soft constraint is pointless because it's a fixed constant number (the number of items lacking). You could even decide to spread that shortage fairly over the customers and adjust their customerDesired accordingly, before scheduling.

B) However, if there aren't plenty of vehicles, relative to the number of customers, then A) might be insufficient. We 'll want to allow to deliver/pickup less than customerDemand, making it more flexible (and therefore complex :). In this case, a Customer has 2 genuine (=non-shadow) planning variables (instead of just 1): the previousStandstill (~ previous customer) and the deliveryPickup (<= demand * 2).