Algorithm solution is not good from a geographical point of view

Hi everyone,

I’m trying to use JSprit to solve VRP problem with FleetSize.FINITE on a predefined set of Services and Vehicles.

The algorithm is quite fast to execute, however the result is not good from a geographical point of view.
What I mean is that, after plotting result to a map, I see that routes for Vehicles frequently cross themselves.
If one looks at the results I’m getting may think that there is no or few logic behind the algorithm.

How can I achieve something that is clustered in a better way?
Also, there’s a way to get almost the same result (I know exactly the same is not possible, but at least comparable) when starting from the same set of Vehicles and Services?

I’m newbie of JSprit and I’m using the SimpleExample case to test the Service allocation on Vehicles.

Thank you.

Hi @LucioB,

Yes I have also noticed that the solution obtained for a multi-vehicle VRP is not in a clustered fashion. Stefan suggested increasing the probability of the cluster ruin strategies in this post, but it did not work for me.

So I still stick to the approach that I cluster the jobs first and then run jsprit for each individual cluster as a single-vehicle VRP.

Regarding reproducing the same result in different runs, I think it should have been fixed in #156.

Hopefully the above helps.

Best regards,
He

1 Like

Can you provide us your example and which algo configuration you use?

Result with low iterations, very confused (maybe random) as you can see from pin colors:

Result with high iterations, a little bit better but still overlaps between pin colors:

The code I use to run JSprit VRP is the following:

VehicleRoutingProblem problem = VehicleRoutingProblem
    .Builder.newInstance()
    .setRoutingCost(new GreatCircleCosts())
    .setFleetSize(FleetSize.FINITE)
    .addAllVehicles(vehicles)
    .addAllJobs(services)
    .build();

VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
VehicleRoutingProblemSolution best = Solutions.bestOf(solutions);
SolutionPrinter.print(problem, best, Print.VERBOSE);
return best;
1 Like

Interesting, I might go for the same solution using a DBScan or KMeans before passing data to JSprit.

Just one consideration: how do you handle the fact that doing N runs of JSprit (one for single user, instead that 1 for N users) may generate unbalanced itineraries?

Do you have size/capacity restrictions?

Not in the original form of the problem, the fact is that each vehicle has a limit of maximum services that can execute (usually 15 services for vehicle).

I’ve modelled that fixing:

  • Vehicle max capacity = 15
  • Each service dimension = 1

This part works well indeed.

From the image it is hard to judge whether it is a good or bad solution. It does not look that bad, and the solution depends on the underlying travel time data as well. If you just use Euclidean distance it should be more clustered.

I’m currently using GreatCircleCost as RoutingCost.
Which is the clustering algorithm behind the VRP solver? (I guess it’s a DBSCAN, right?)