Objective
In this project, I try to implement:
- nearest neighbor
- genetic algorithm
- simulated annealing
to find the solution for Capacitated Vehicle Routing Problem (CVRP). I using shiny to visualize the algorithm result on several benchmark data set. You can find all my code of shiny app on github. Or visit my app here
The picture below is a screenshot from the app:
Approach
Overview
CVRP is a famous problem in optimization fields. The problem ask for an optimal set of routes for a fleet to visit and serves all customer demand with limited vehicles capacity. There is a single depot that has to start and end its tour in there. Every time vehicles back to the depot, its capacity restore.
The following graph is the example of CVRP
This problem is an extend of traveling salesmen problem (TSP) and vehicles routing problem (VRP).
Some of CVRP application in the real world:
- Product delivery system
- Distribution of goods to the stores
- Waste collection
Determining optimal CVRP solution is extremely compute expensive when the number of customers grow up. Therefore, using heuristic and meta heuristic are often more suitable to find near optimal solution compare with using exact algorithm.
TLDR;
What is heuristic and meta heuristic?
1. Heuristic
Heuristic is an algorithm to find approximate solution to a problem. For example: In nearest neighbor heuristic, we continuously go to the nearest customer until we visit all of them. It is not optimal but in several case, could bring an acceptable result.
2. Meta heuristic
Meta heuristic is a procedure to search for optimal solution. It treat an objective function as a black box, giving it input and observe output. Depend on the output, it will trying to modify the input to make improvement.
While heuristic is problem-dependent algorithm. Meta heuristic normally don’t and can apply to multiple problem.
“Random” Nearest neighbor algorithm
This algorithm work as follows:
Figure 1: Nearest neighbor algorithm
Genetic algorithm
Genetic algorithm (GA) is a kind of meta-heuristic. It base on concept of natural evolution by selection.
The implement of GA is show as below:
Figure 2: Genetic algorithm
In my shiny App, I using the {GA} package to run generic permutation search.
Simulated annealing
Simulated annealing (SA) is also a meta-heuristic. The idea is borrow from annealing in metallurgy. In short, when heating to a certain temperature and slowly cooling the material, one can alter its physic properties. In context of mathematics problem, the algorithm is implement as below:
Figure 3: Simulated annealing algorithm
The key point of SA is that, it move search focus to a worse solution in order to find the better one. This properties help algorithm to escape local optima.
In the shiny app, my strategies is to generate first solution by nearest neighbor and run SA on all sub-route. The neighbor solution are generated by choose two random point and reverse the path. For example:
Figure 4: Original solution
Figure 5: Neighbor solution