The "Curly Problem": erroneous solution output in VRP

jsprit
1

Hi,

Me and my team have been using GraphHopper + Jsprit for almost 2 years now to solve VRPs. However, along all these years we have always dealt with a problem that happens on very specific situations when trying to solve certain points configurations. Specifically, this problem occurs when streets blocks are geographically arranged as a “square grid”, and the points are very close to each other. This problem causes the route solution to be not optimized. We have called it “the curly problem”. Since it makes vehicles to perform unnecessary “curls” or loops, before getting to the next point.

Example Configuration:

  • 1 COMMON PICKUP (grey) and 2 DELIVERIES (blue).

  • Just one vehicle. Homogeneous fleet. NO skills. Infinite capacity. Cost by meter: 1. Algorithm iterations: 200. Not using a fixed order. Not using hints. Not using delay times at stops. No time windows constraints.

  • Graphopper Version: ‘0.8.2’

  • Jsprit Version: ‘1.7’

  • Points configuration:

Computed solution: (green arrows are streets ways; number on points represent the order of the solution output; grey path is map matching based on the solution order)

https://i.stack.imgur.com/VTMqU.png

This is not an optimized solution. We would expect the following map matching (red arrows) solution, which is achieved when point 2 and 3 are swapped:

https://i.stack.imgur.com/yiLkR.png

Clearly this is a the optimal solution given the points configuration. And, as seen on figure 2, street ways (green arrows) perfectly allows this.

Is there any hint on how to solve this? Maybe some parameter of graphHopper or some parameter on the Vehicle or in the VRP?

Hypothesis we have theorized but not proved:

  1. Cost Matrix is not taking into account the direction the vehicle is going when arriving to a point. This is leading to an instant U-turn on arrival at any point. Which would make the outputted solution the optimal for the engine.

The curly problem can become very ugly on big routes with similar configuration on their points.

Thanks for reading. Me and my team are looking forward for your suggestions!
Btw, Thanks for all the support given to Jsprit.

1 Like