OptaPlanner vehicle routing and relations between customer visits

Question

I am using OptaPlanner to optimize a vehicle routing problem very similar to the provided example.

I am faced with the following challenge and will appreciate some ideas.

Some of the visits to customers have relations to other visits, for example:

• A visit must start at the same time with another visit.
• A visit must start 2 hours after another visit finishes.
• A visit must be allocated to the same vehicle allocated to another visit.

The challenge is: How to allow moves of the visits without resulting in lower score while moving one of them?

Each visit might be on a different chine (allocated to a different vehicle), so that all provided moves selectors will most likely provide moves that change only one visit. Such moves most probably result in lower score due to the dependency and will never be selects.

Same start scenario: any move that change the start time of one visit will result in lower score. Same vehicle scenario: any move that change one visit to a different vehicle will result in lower score.

Currently I am using Tabu Search with satisfying results. Late Acceptance might be the answer.

Thanks.

Answer 1

What you're describing is a form of a score trap. Although Late Acceptance is likely to produce better results than Tabu Search when the score trap is present (and it's just changes 2 lines to switch to it), it's still going to affect the results badly.

Those docs describe 2 answers to get rid of the score trap:

1) Improving the score function granularity won't work in this case.

2) Course grained moves will work in this case. For example you can add a custom move factory (but keep the original moveSelectors too - or better yet benchmark with and without the original moveSelectors). Let the custom move factory generate moves that are less likely to break those constraints. For example: if visit A and B need the same vehicle, move A inside another vehicle's chain and at the same time move B to somewhere else in the same vehicle's chain (reuse CompositeMove).

And there's a 3th way I 'll document soon (but I don't see it applying to this case easily):

3) In some cases, its possible to bake such hard constraints into the class diagram of the model (which makes them build-in hard constraints). For example in exam scheduling, if 2 ore more exams need to be at the same timeslot, only 1 exam is "the leader" and has a timeslot variable. The other exams are "herd", which means their timeslots get adjusted by a shadow variable when the leader changes.