Determination of optimal distribution route is one of the keys to increase supply chain efficiency. Looking for an optimal distribution route that belongs to the type of vehicle routing problem (VRP) can be solved by modeling the entire boundary of the problem as the constraints and finding the solution with the objective of minimizing the total distance. The problem is the complexity of solving the model will be increased in line with a number of constraints that exist. In addition, some dynamic constraints and unidentifiable boundaries can make the optimal route obtained is not suitable with the actual current condition. In this study, historical-based VRP (HbVRP) method which consists of graph partitioning and graph optimization is used to solve the problem. In the case study, the HbVRP method can build optimal route with 97.98% similarity level to the actual route and reduce the total distance from 572.217 to 120.913 which is better than existed method.