Exploration of heuristic and metaheuristic algorithms used to solve CVRP
I plan on adding structure whenever I have the opportunity! It's a nice ongoing project to have, because the vastness of the CVRP literature means that there is always something to add.
I'd also like to increase specificity a little bit : after all, the nodes of the graph are likely to be clustered in cities and so on - so perhaps can think of some nice clustering methods to deal with this.
Some To-Dos:
- Pre-filtering of routes for inter-route optimisation. This could be by feasibility, or we could only compare nearby routes (eg. by centre of mass, the angle of the route from the depot etc.)
- When doing route split - fix number of vehicles in the fleet. cf Vidal: Technical note: Split algorithm in O(n) for the capacitated vehicle routing problem §4
- Allow exploration of infeasible solution space in genetic algorithm
- Hyper-parameter optimisation - opportunity to practise some ML
- Implement Time Windows
Folium is used for map visualisation - Below is an example of a solution produced by using Parallel insert, then applying 2-opt intra-route (ie. TSP) improvement to essentailly remove crossing overs.
The original distance score was 2068468.987861114, whereas after 2-opt this was reduced to 1939871.3691548237
Snippet of the PNN-solution with no opt:
Snipped of the solution after opt:
There is much to do. I've implemented a genetic search method, but would like to build on this by allowing exploration into the space of infeasible solutions. Also, I would like to do some hyperparamter tuning. Notebooks include my rough notes on the CVRP from reading through papers, inc some explainations of k opt operations:
There are many - need to compile a list