The after-service of service parts in the automobile industry has to replenish about several ten's thousand types of service parts frequently to many service shops located in widely spread areas in Taiwan. This research investigated the cost optimization of the vehicle routing problem for a major distributor-X company in the automobile industry to achieve better service level of service parts distribution. In the first research phase, an on-site depth observation was conducted to collect relevant information of X company. Then, a business process analysis method was used to build a conceptual model for the active service parts delivery process of X company. This conceptual model helped to identify the problems existed in the service parts delivery process. In the second phase, the research applied a practical management science approach to construct Vehicle Routing Problem (VRP) model on the service parts delivery routes of the northern territory of X company. Due to the practical constraints, the res earch used a well-known heuristic approach to solve this VRP problem. This research had lasted for about seven months. The conceptual model built in the first phase assisted X company and researchers to better understand her existing service parts delivery process, and provided insights for further improvement. The service parts delivery route model of the northern territory constructed in the second phase suggested X company to relax the total time constraint on each route to 255 minutes (the initial constraint was 240 minutes) and this allowed X company to shorten the delivery routes from thirteen to twelve. It can save 1.5 million dollars (about 7 percent of the current delivery costs) per year on the delivery cost for the northern territory parts distribution.