K – Means Clustering and Hill Climbing Algorithm to vehicle routing problem on Excel VBA

Abstract

The purpose of this study is to present the transport routing using the hill climbing algorithm (HCA), compared with the simulated annealing algorithm (SA) by stratifying the customers by K-Means clustering to group the transport coordinates of customers. The cost of fuel is calculated by distance-based transportation costs; so, the transportation route with the shortest distance is needed for the calculation. As the experimental result, it was found that customers should be grouped into six groups. This transport routing cost is compared to the previous routing's cost, and it showed that the transportation distance was reduced from 6,144 kilometers to 5,928 kilometers, reducing the distance by 216 kilometers. This reduced the transportation costs from 5,805,888 baht per year to 5,510,016 baht per year, which was calculated to be 295,872 baht reduction per year, or 5.10 percent of cost reduction per year.