The capacitated vehicle routing problem is a well-studied combinatorial computing problem. There are many ways to solve the problem like evolutionary computing, reinforcement learning and exact methods. A genetic algorithm was implemented to solve a given CVRP instance with 250 customers. An evolutionary computing approach was chosen because of the following reasons:
-
The exact methods like branch and cut explore the entire search space which is most of the time unfeasible given the computation time. A genetic algorithm can be fine tuned to explore the search space in a specific way.
-
In this case, the constraints are very simple; maximum vehicle capacity of 500 and a vehicle can visit a customer only once. A real world CVRP can have multiple objectives and constraints like traffic conditions, number of turns, multiple depots etc. A genetic algorithm can adapt to these constraints without the need to change the entire programmatic structure by simply formulating the fitness function again.
bash start-cvrp
- Navigate to Plot_tools
- Place your solution file there – best-solution.txt. (if you want to plot the entire search process, add the intermediate routes as-well).
- Run ./animate.sh
- Output: animate.gif
Note: The vrp data is already present in animate.cc. So if you need to use this with other vrp data, it should be changed there.
Best so far
Animated gif
