Clustering for Vehicle Routing in Kenya

When attempting to solve the extensively researched vehicle routing problem (VRP) in a non-western context, literature may still be limited. The problem in this paper is presented by a Kenyan company, which copes with four issues regarding their daily VRP: they prefer fixed drivers to visit each demand location, demand is very infrequent and unknown until one day in advance and the set of demand locations is highly variable. As a solution, a two-phase approach to solve the problem was introduced, consisting of a clustering phase and a daily route optimization phase. Clusters should be formed for a longer period of time and such that daily routes are feasible. The K&P algorithm and the Districting algorithm are proposed for clustering, which have arisen from respectively the Capacitated Cluster Problem and the Districting Problem. Both are evaluated by means of transportation costs and the cluster stability, the percentage of demand locations served by the same driver after clustering, for the purpose of evaluating how and whether the two can be balanced. As a result, it was shown that especially the K&P algorithm leads to good results, with an average cluster stability of 70%. The cluster stability could be increased further by implementing a simple extension. In addition, a proper method for constraining the clusters was introduced. Finally, it is recommended to the company to neglect the distance to the depot in the clustering objective, rather than incorporating it, to enhance the compactness of the clusters. This was found to result in lower costs and an increased cluster stability. In addition, it is advised to adopt growth strategies such that new customers are found both within and outside of the current territory. This will lead to a decrease in costs by searching within the territory and an increase in cluster stability by searching outside the territory.