[rules-users] [Optaplanner] Scheduling + VRP

[Geoffrey De Smet]

On 30-11-13 15:02, Mats Norén wrote:
> Hi,
> I'm looking for an example that does both scheduling and vrp.
No example of that combination yet.
> I have workers with certain skills and I have goods (which require a particular skill set) to be delivered or picked up within certain time windows.
> Each worker work in a team.
> The team should if possible be assigned to the same delivery/pickup.
> The workers work in shifts and by law has to have breaks etc.
> I want to create a schedule that assigns workers/teams to deliveries/pickups and stay within the time windows as well as optimizing the distance travelled.
> I thought about the nurse rostering example together with cvrptw but the nurse rostering uses shifts (day, night).
>
> Do I have to do it in two steps? First VRP and then try to assign the workers?
In practice, I often see this happening in 2 separate, sequential 
planning problems (or phases),
but that's just because of Conway's law:
   "organizations which design systems ... are constrained to produce 
designs which are copies of the communication structures of these 
organizations"

2 phases is probably suboptimal, because the limitations on the second 
phase influence the planning of the first phase.
There are 3 ways to handle that:

1) Ignore it that 2 phases is suboptimal. You 'll have better results 
that the old system already. You can tweak it by adding some constraints 
in phase 1 that make it easier for phase 2.

2) Bender's decomposition. Basically ping-pong between phase 1 and phase 
2 (where the result of phase 2 adds constraints in phase 1). Not yet 
supported out-of-the-box by OptaPlanner, but probably a domain specific 
pita to implement.

3) Do it all in 1 phase. OptaPlanner 6 has been written to handle 
multiple planning entity classes and multiple planning variables, so 
it's definitely possible. You 'll like need to add course grained moves 
to get things to change for phase 1 in a way that works for phase 2, to 
avoid getting stuck in a "score trap" (see docs).

I am a strong believer in approach 3). If you go that way, let me know 
how it works out: I need cases to prove that the human planners that 
follow Conway's law should not limit our potential when automating this.
But the conservative choice is 1).

In any case, I recommend to prototype phase 1 first.

>
> The only hard facts are the workers worktime and the goods delivery/pickup time.
>
> Any suggestions?
>
> Best regards,
> Mats
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>