Vehicle Routing Problem (VRP) is a famous tool in solving a logistic management problem. A lot of efforts are being made to research it so that VRP can be implemented effectively and efficiently. The goal is that the costs incurred on the VRP can be achieved as least as possible and the company has good competitiveness by using any methods to achieve optimum solution. In this research a new problem of VRP in bulk cement delivery is provided to be solved by a metaheuristic method. A hybrid metaheuristic is developed to solve the problem by combining two metaheuristic methods namely Nawaz-Enscore-Ham (NEH) and Particle Swarm Optimization (PSO), called NEH-PSO. By conducting several experiments, NEH-PSO provides better solution compared with its building methods. It gives 3.66% effectiveness of the average of total distance compared with NEH and PSO as well as 3.68% effectiveness if it is compared with Tabu Search (TS) and Genetic Algorithm (GA).