Break always placed in first position

[braktar]

In some cases, the break is always placed in first position of the route.
It has for consequence to unassigned job, wheras it is possible to perform these job before the break.

Here are two JSON which illustrate this case :
https://gist.github.com/braktar/fe118d6abeaf72e9c004943eae52b096

[jcoupey]

I can reproduce this problem. It looks like a flaw in the validity checks that result in discarding the option of putting jobs before the break in that case. Then some jobs just get unassigned if there is not enough room for them after the break (all jobs unassigned in the second example).

[jcoupey]

Fun fact: this only happens with zero service. The expected solutions are reached when changing the service values to any non-zero value.

[braktar]

I've added a biggest instance with shipments where the rest is supposed to be placed in the middle of the day. As there is less jobs to perform at this moment, but the solution uses 5 vehicles with breaks and place them at the beginning of the day.

[jcoupey]

I've narrowed down the initial problem. The order_choice function is used to decide whenever we need to order a job and a break. The logic is:

• if doing job -> break results in arriving too late at the break, then we put the job first
• if doing break -> job results in arriving too late at the job, then we put the break first
• if both are OK in term of arrival time, then we first put the one that is the more time constrained here

When trying to insert a job in an empty route in the examples, both arrival times are OK whatever the order. But because the job service time is zero, the overall end time is the same (travel time to the job can be done before the break in the break -> job case). As a result we put the break first because it has a deadline.

Now the flaw for end_of_day.json for example is that for all jobs, we try break -> job with a valid arrival time to the job, but then this ordering ends up being invalid due to the return time after the job. On the other hand, the valid job -> break option has been discarded in the process.

[jcoupey]

I pushed a commit in #386 that does the job for the initial problems. It adds checks to avoid suggesting an ordering that turns out to be invalid while the other one is valid.

Solutions provided for both end_of_day and middle_of_day instances are as expected.

[jcoupey]

We have another problem with order_choice and shipments. Pretty much similar to the one described above with jobs but a bit trickier because the validity for including a shipment involves two steps (pickup and delivery). See instance every_vehicle_with_break.json in the linked gist.

Say we check validity for insertion of a shipment into an empty route with a break. At first, we have ordering options start -> break -> pickup -> end and start -> pickup -> break -> end. If both are valid and break deadline is more constrained than pickup deadline, then we'll go for the first option with break first. Then we check start -> break -> pickup -> delivery -> end which turns out to be invalid if the deadline for delivery is tight and the break service time is high.
On the other hand, start -> pickup -> delivery -> break -> end or even start -> pickup -> break -> delivery -> end may be valid, but we never see this.

What makes it even worse is we have a (usually clever) way of reducing local search checks by marking jobs/shipments as incompatible with a given vehicle as soon as insertion in an empty route is invalid. Thus such shipments are wrongly seen as totally not doable and are discarded throughout the search, ending up unassigned.

I think 809bd20 fixes this problem, we'll have to see whether it's enough in the general case.

[jcoupey]

Moving the internal implementation discussion to #386 (comment).

[jcoupey]

@braktar thanks for reporting, this should now be fixed in master.