VRP - Automatic Zoning

[vroom-project]

VRP - Automatic Zoning

[PattyDePuh]

Hey sragneau,
i'm not @jcoupey , but if i understood correctly, then your suggestion
to predetermine which job point has to be visited by which vehicle is in the end just a set of TSP instances and not a true VRP with multiple vehicles. The assignment of vehicles to jobs is part of the optimization and shouldn't be treated on a cheap way.
Finding an approach for your 'point in polygon' problem to assign your points to a region can be found in Wikipedia. It will be unlikely, that this problem will be a part of this project, but i'm not the owner to put that on stone...

About the approach for further attributes for the VRP is still a discussion point with you @jcoupey.
I was thinking about a memetical algorithm (Vidal 2014) as the meta heuristic above the existing TSP solver to solve several VRP attributes like capacitated, intermediate facilities, multi-vehicle and periodic.

[jcoupey]

There is a (somewhat outdated) features discussion at #4 where I provided an informal roadmap a few months back. Some refactoring has been done in order to have an extensible model to be able to describe other problems, so it should be easier now. The CVRP is still on my mind, the question is to find time to address it properly!

Regarding the approach, a heuristic using some kind of clustering to split the problem and solve one TSP per vehicle might be a good starting point. It would not be sufficient though, as the solutions would probably still be "too sub-optimal".

[jcoupey]

@PattyDePuh do you have a link for the paper you mention?

[PattyDePuh]

Added Link to reference.

[sragneau]

@PattyDePuh you're right, my approach is not the best to optimize. @jcoupey glad to see that VRP is still on your plan

[jcoupey]

Closing in favour of #74 for multiple vehicles support based on capacity limitations.