Mixed Pickups and DropOffs VRP With Planning List Variable

[Mathias Are]

Hi!

My team and I are currently implementing a  time-windowed VRP solver with mixed pickups and drop-offs. We also use the overconstrained variant with dummy vehicles.

Recently, we decided to try the @PlanningListVariable variant of the VRP as in your examples GitHub repository (repo). We were really impressed how the update made it much easier to understand the solver logic (none of us really have previous experience with Optaplanner) and frankly, it made our solver more reliable in terms of solving larger problems (so kudos for that to the Optaplanner team!).

However, the performance of our solver is still lacking as we use hard constraints to assure everything. Also, it sometimes assigns too many visits to dummy vehicles. 

Generally, what would be the best way to approach optimizing the current model in your opinion?

(we have no weight factories or custom moves implemented yet).

I found this old ticket with a few possible suggestions (PLANNER-833). Would it be possible to implement something similar to the custom move approach with the @PlanningListVariable VRP version?

Best regards!

Mathias Are

[Lukáš Petrovický]

On Wed, Oct 19, 2022 at 1:27 PM Mathias Are <are.m...@gmail.com> wrote:

Generally, what would be the best way to approach optimizing the current model in your opinion?

Speaking in general terms, it is always best to model your problem in such a way that the true "hard constraints" are built-in. If your data model makes certain situations impossible, the solver will not have to waste time working around them when they happen. If you've already exhausted that well, then custom moves are your next best bet. 

Let's take a hypothetical example where two vehicles must always move together. The generic moves are going to cause problems here. They may move one vehicle, which breaks a hard constraint for the other vehicle, and the only way to fix it is for the solver to randomly stumble upon another generic move that moves the other vehicle as well. The likelihood of that happening is not good, and solution quality will suffer for it.

The solution to this hypothetical is to replace the generic moves with custom moves - in this case, a custom move that always moves the two vehicles together, never breaking the hard constraint in the first place. But the best approach would be to design the model in such a way that the planning entity always has a pair of the vehicles as planning facts, and a planning variable is the destination - when the variable changes on the entity, both vehicles change automatically, without any need for custom moves.

 

I found this old ticket with a few possible suggestions (PLANNER-833). Would it be possible to implement something similar to the custom move approach with the @PlanningListVariable VRP version?

Custom moves are orthogonal to the type of planning variable used. You can design custom moves for any problem.

 

--

Lukáš Petrovický

Principal Software Engineer

lukas.pe...@redhat.com

My work week is Monday to Thursday.
No need to respond outside of your working hours.

[Mathias Are]

Hi, Lukaš!

Thanks for the response and the detailed example!

We will try to implement a custom move for moving the PICKUP and DROPOFF together then when changing the vehicle or visit order on a vehicle.

BR

Mathias Are