Route puts next door houses as drops 5 and 10 in a loop

[jendrage]

We've had an issue crop up where 2 houses next door to each other are separated by a few drops when the vehicle is doing a loop and coming back down the same road. It's confusing for the driver to be going to the same building twice, and of course it would save time to do both drops at the same time.

I'm trying to work out if this is normal behaviour (ie. because the possibility of the driver doing both deliveries at the same time with one stop of the vehicle can't be taken in to account by Vroom?) or if there is anything we can do to avoid this.

Here is a screenshot to show this example, it was part of a much larger route (10 and 5 are overlapping in the same place, same side of the road)

In case it might be relevant, we are using ORS with Vroom - generating the travel-time matrix in batched chunks due to memory/size limits, then merging the returned durations into a single matrix, and then passing that full matrix into the VROOM optimization request with the jobs and vehicles payload.

Thank you for reading!

[jcoupey]

Thanks for sharing some context.

of course it would save time to do both drops at the same time.

That may be the actual problem: since your route seem to go by stop 10 on the way back anyway, it's possible that the cost we evaluate for this solution is actually the same as the (more natural) one where stops 5 and 10 would be done in a row.

In order to confirm this, I'd need to look at a reproducible instance that includes the matrices.

[las59]

I encounter the same issue as well. We had to proceed with a grouping of stops with the same GPS position before calling VROOM to work around the problem. Furthermore, in the same type of problem, we sometimes have stops to make in the "outbound" direction and another in the "return" direction, whereas we could make all the stops in the "outbound" direction. Similarly, we had to rework VROOM's output to re-sequence the stops using the returned polyline, so as to avoid this issue without changing the proposed route.

[jcoupey]

grouping of stops with the same GPS position before calling VROOM

This is a good practice. If you have several tasks at the exact same place that do not make sense to split in the route plan, then from the optimization point of view it should essentially be a single task.

[jendrage]

Thank you for your replies! I will try to sort out a reproducible instance.

I thought about grouping drops before passing to Vroom, but as we're talking about locations that are close but not identical, I wouldn't be able to tell, programmatically with only lag/lng, if nearby drops were neighbours, across the street or even on close by parallel road with a completely different access. Our drops also use service times and time windows, so grouping them would get complicated.

Re sequencing the stops is more appealing, @las59 do you do this manually after reviewing the routes?

[las59]

@jendrage
Grouping by exact GPS position is done before the VROOM call, and ordering within the same street is handled by a Python script after VROOM. We rely solely on the polyline returned by VROOM. If a customer appears in the polyline but could be served earlier, we reorder them in the correct direction. Basically, the polyline itself doesn't change — only the order of stops within it may.

[rubennaatje]

We fixed this by using a custom cost matrix and giving penalties for 'parking' (so when distance is further than X, add X to the costs)

[jendrage]

Thanks very much for the info @las59. Unfortunately I don't think the approach of re-ordering drops after optimising is going to work for us as we are using time windows in Vroom.

@rubennaatje this sounds great - are you basing the cost on distance between the drops somehow? I am trying to get my head around how this could be done before optimisation.

Thank you!