VRP with clustered routes using optaplanner

Question

I am using optaplaner to solve a vehicle routing problem, I apply different constraint providers to enforce weight and volume capacities, time windows, etc.

I am getting routes, which as shown in the image are elongated in direction.

And my question is: How to obtain clustered routes as shown in the following image, what constraint could I implement or what algorithm should I activate in obtaplanner to obtain a similar behavior?

I value very much any idea or input. Thanks!

Answer 1

You have to answer a question which I can not answer for you. Why are clustered routes preferrable? Are they shorter in driving distance? Are there legal requirements for maximum distance driven from a depot? Something else?

Once you have an answer to that, write a constraint for that criteria.

You may possibly find some inspiration in the facility location quickstart.

Answer 2

This is an active area of reserach.

Some ideas as how you may be able to achieve this:

• Add metrics to the optimization target if minimized the routes are more clustered (e.g. bounding box, area of a route, cross-overs between routes, average squared distance to the route's center). The con to this approach is that often these metrics slow the solver down rather significantly.
• Cluster first, route second algorithms. You can create cluster first and set a hard constraint that these clusters are not to be broken. The con to this approach is that you may not use the "optimal" amount of resources.
• Cluster first, route second algorithms, but with an objective to not break up the clusters. The con to this approach is that the clusters may not be respected if there are better solutions where the cluster needs to be broken up.

That's all I have for now. In my experience the time window constraint is often the most constraining factor, and having narrow time windows often contribute to what is perceived as "messy" routes. See if you can relax one or more constraints if you can.